The forums have permanently moved to forum.kirupa.com. This forum will be kept around in read-only mode for archival purposes. To learn how to continue using your existing account on the new forums, check out this thread.


Page 1 of 2 12 LastLast
Results 1 to 15 of 17

Thread: Best approach for checking a radius for objects

  1. #1

    Best approach for checking a radius for objects

    Hi there,

    I am just creating a small game and i am wondering if anyone has any pointers on how to best approach this problem.

    Image attached.

    Basically if i have 20 random circles on the screen. The mouse has a radius area defined and every second i check to see if the mouse is close enough to any circle on screen.

    so

    circle1 calculate distance between circle1 and mouse... if the distance is less than the radius then happy days.

    However, i can see this being a problem, what if i have 400 circles? Each second id need to do the above for each of them.... thats alot of CPU.

    Is there a better approach to this problem?

    Thanks.
    Attached Images Attached Images  
    jings

  2. #2
    1,627
    posts
    hugeExplosions = true;
    You could always use partitioning to seperate the screen into discreet areas. Then you'd only need to test the circles in the immediate area - when a circle moves you can update it's current area

    Look into quadtrees

    Also note that you don't need to square root the distances of the mouse/circles - you can keep the values squared as this will still tell you if the mouse is inside/outside the radius. You only need the root when you need the actual distance.
    MS Paint FTW!


  3. #3
    I would have thought your way was the closest way. It's pretty much exactly how I deal out splash damage to creeps in my Tower Defence game.

    If you can't keep a sorted list of circles ordered in distance away from the mouse and then just break out of the loop when you evaluate a circle thats out of the mouses range then I don't know how I would go forward. I'm thinking something using hitTest() could be used... I'll have a think how exactly and post again if I think of anything.

  4. #4
    209
    posts
    Registered User
    Wait. Every second? Or every frame? Anyways, the distance calculation is very simple and should be a drop in the bucket for efficiency. I wouldn't worry about it. I threw together a test script and it ran at 60fps with 400 dots. With 1000 dots it still ran at 30fps. I think any kind of efficiency algorithm you could try would actually use up about as much cpu power as the brute force technique. Basically, 400 calculations is barely anything. The only reason my script ran as slow as it did at 1000 objects was because of the rendering. If anything look for efficiency problems in rendering because that's where the big processing sucks come from.

    The only thing I would recommend is to use the class flash.geom.Point instead of writing your own Pythagorean theorem function. It wouldn't be any faster but it's a lot cleaner and easier to read the code.

    Code:
    vector = new Point(stage.mouseX-clip.x,stage.mouseY-clip.y);
    vector.length;
    Last edited by Fidodo; June 23rd, 2008 at 05:40 AM.

  5. #5
    Hey thanks for all the replies lads.

    It takes me a while to get my brain warmed up on a Monday.

    Charleh, i pretty much liked the idea of checking portions of the screen. Ill be doing a search for quadtrees after this post as no idea what they are of yet. It makes sense that splitting my screen into 2 parts for example and only running the calculations on the active part would half the calculations... more if i split the screen into quarters... and so on.

    Andrew, the funny thing is that a tower defence type game is actually what made me think of this to begin with. I was playing a game of my brothers which was like the traditional defence games and wondered if i could do something similar in AS3 as a hobbiest. Could you post a link to your completed work?

    Also Fidodo, you reminded me that the Point class has a Point.distance(p1, p2) method

    Thanks guys ill let you know what i come up with.

    Demonstrates the concept
    http://lab.polygonal.de/2007/09/09/q...demonstration/
    Last edited by grandpaw broon; June 23rd, 2008 at 06:25 AM.
    jings

  6. Quote Originally Posted by Fidodo View Post
    Wait. Every second? Or every frame? Anyways, the distance calculation is very simple and should be a drop in the bucket for efficiency. I wouldn't worry about it. I threw together a test script and it ran at 60fps with 400 dots. With 1000 dots it still ran at 30fps. I think any kind of efficiency algorithm you could try would actually use up about as much cpu power as the brute force technique. Basically, 400 calculations is barely anything. The only reason my script ran as slow as it did at 1000 objects was because of the rendering. If anything look for efficiency problems in rendering because that's where the big processing sucks come from.

    The only thing I would recommend is to use the class flash.geom.Point instead of writing your own Pythagorean theorem function. It wouldn't be any faster but it's a lot cleaner and easier to read the code.

    Code:
    vector = new Point(stage.mouseX-clip.x,stage.mouseY-clip.y);
    vector.length;
    Definitely don't use the Geom class, it's to slow. You can way better write your own, or, what I would do, simply write a method. Charleh's way is obviously the fastest, but the hardest.

  7. #7
    207
    posts
    Registered User
    Well, this isn't so bad since it's still O(n) not O(n^2) or anything. (I mean, if you have 400 circles, you only need to loop 400 times, because you are comparing them all to one thing. But if you were comparing all the circles to each other, for example, you'd have to loop 400*400 times.)

    But since most of the circles won't be in range at any point, you could try testing if it's within a square bounding box instead of inside the radius, and then test the radius only if that's true. There's slightly less math for each false, but slightly more for each true, so this helps as long as there's more false than true.

    Code:
    if ((x1-radius*2<x2)&&(x1+radius*2>x2)&&(y1-radius*2< .... ) {
         //you know it's inside the bounding box, which is necessary but not sufficient
         //so then test using actual radius math
    }

  8. #8
    Here's the link to the near finished Tower Defense game I was talking about:

    http://www.dukesbox.com/games/game18...e=14256&type=1

    I use the brute force approach of just going through the list checking which ones are in range and which ones are out of range. If you wanted any code from this let me know and I'll be happy to give it to you.

  9. #9
    209
    posts
    Registered User
    Quote Originally Posted by ArmoredSandwich View Post
    Definitely don't use the Geom class, it's to slow. You can way better write your own, or, what I would do, simply write a method. Charleh's way is obviously the fastest, but the hardest.
    It is slower but readability is important too. Basically, the task at hand is soo simple that losing a couple hundred processing cycles wont really effect performance.

  10. #10
    If we're worried about readability and speed, then just out of interest would using the geom class be faster than doing an extra function call?

    i.e.

    Code:
    distanceToCircle = getDistanceToPoint(x1,y1,x2,y2);

  11. #11
    209
    posts
    Registered User
    No geom is going to be slower. I like to use it because it's a bit cleaner to pass a Point around as a vector than to pass around 2 coordinates all the time. In my example I'm creating a vector from a dot to the mouse and getting the magnitude. To me that seems more readable but that's just my style of programming. Geom is definitely going to be slower but not by more than a couple extra instructions, and with processors doing millions of instructions per second that's not going to effect anything.

    I mean a 1.6 GHz processor does 1.6 billion calculations a second. Getting the distance from 2 points is absolutely nothing to the computer. The thing that is causing slowdown if there is any would be the rendering and other things the flash player does that you can't really control as easily. Putting together a complex algorithm to save a couple thousand calculations is not worth it and kinda a waste of time. If you were doing something complex like hit detection then it would be worth optimizing it, but implementing the Pythagorean theorem is so simple that I'd just brute force it.

  12. #12
    1,627
    posts
    hugeExplosions = true;
    Getting the distance between 2 points is quite processor intensive as simple instructions go - with a radius check there's always a square root involved if you want the actual distance. We all know square roots are the enemy, you can avoid it by checking the squares of the two distances against each other instead of rooting them - but this doesn't give you the distance, just a value which can tell you if the circles overlapped.

    I don't know if the Point class does a lot of stuff that you don't need it to, but I can't imagine it being much slower than a custom class. I'm not sure if the Point class stores the vector length as a property or calculates it via a method when you call 'length'. I'm sure if you wrote your own little vector class which did these bits and pieces you could cut down on the unnecessary stuff (if there is any).

    I'd imagine the quickest setup would be something like

    Code:
    Class Vector {
      var x:Number;
      var y:Number;
      var dirty:Boolean;
      var len:Number;
     
      function Vector(_x:Number, _y:Number) {
        SetVector(_x, _y); // or just assign it, not sure which is quicker in flash but probably the assignment
        dirty = false; // Vector can be dirty (length has changed since last query)
      }
     
      function SetVector(_x:Number, _y:Number) {
        x = _x;
        y = _y;
        dirty = true; // This vector has changed so make it dirty
      }
     
      function Length():Number {
        // return length - but if the vector is dirty recalculate the length
        if (dirty) {
          dirty = false;
          len = Math.sqrt(x * x + y * y);
        }
        return len;
      }
    }
    That skips any unneccessary square roots... don't know if it will be any quicker than point, but test it out!

    I'm not sure if your app will see a performance boost though - if any it will be with 2 squillion circles testing brute force style
    MS Paint FTW!


  13. Quote Originally Posted by Fidodo View Post
    No geom is going to be slower. I like to use it because it's a bit cleaner to pass a Point around as a vector than to pass around 2 coordinates all the time. In my example I'm creating a vector from a dot to the mouse and getting the magnitude. To me that seems more readable but that's just my style of programming. Geom is definitely going to be slower but not by more than a couple extra instructions, and with processors doing millions of instructions per second that's not going to effect anything.

    I mean a 1.6 GHz processor does 1.6 billion calculations a second. Getting the distance from 2 points is absolutely nothing to the computer. The thing that is causing slowdown if there is any would be the rendering and other things the flash player does that you can't really control as easily. Putting together a complex algorithm to save a couple thousand calculations is not worth it and kinda a waste of time. If you were doing something complex like hit detection then it would be worth optimizing it, but implementing the Pythagorean theorem is so simple that I'd just brute force it.
    This like that do matter, a lot. If you want to use a class instead of 2 variables at least write your own. Let me do a benchmark test right now to see the difference. And talking about stuff to increase speed, you should talk to jerryscript ( http://www.kirupa.com/forum/showthread.php?t=294827 ), things he does to increase speed is amazing xD

    At least you are right about one thing, this isn't the way to increase speed when you're working with for example movielclips. However, not the fastest result equals bad coding.


    EDIT: So I did the benchmark test. I made 3 methods, each method calculates the distance between 2 random chosen points for a selected number of times, for example 10000 times. Every method is as identical as possible, since length of variables matter (crazy AS2.0: http://www.kirupa.com/forum/showthread.php?t=292307 ) :S . Also note the absence of Math.sqrt!

    Here are the results:
    Using the Geom.Point class 10000 calculations took: 326 seconds
    Using a custom made class 10000 calculations took: 251 seconds
    Using a method 10000 calculations took: 221 seconds


    As you can see there is quite a lot of difference. Using The Geom.Point class it almost takes 1.5 times as long. The custom class is a lot faster so if one doesn't want to change the way one's coding, advisable would be to recreate the Point class, it's a one time job and saves time. Obviously this is still mostly irrelevant when stuff such as movieclips are being used.

    Just a small note, flash is quite slow referencing to objects, so if one were to have one Math class containing methods to calculate things such as distance (I know I have one) it might take a little longer, it would still be a lot faster than the custom made class though.

    For those interested the code (AS2.0, flashDevelop):

    Main
    Code:
    import flash.geom.Point;
    
    class Main
    {
        private static var numberOfTimes:Number = 10000;
        
        static function main()
        {        
            doUsingGeom();
            doUsingClass();
            doUsingMethod();        
        }
        
        private static function doUsingGeom():Void
        {
            var startTime:Number = getTimer();
            for (var i = 0; i < numberOfTimes; i ++)
            {
            var pnt:Point = new Point (rnm() - rnm(), rnm() - rnm());
            var distance:Number = pnt.length;
            }            
            var duration:Number = getTimer() - startTime;
            trace ("Using the Geom.Point class " + numberOfTimes + " calculations took: " + duration + " seconds");
        }
        
        private static function doUsingClass():Void
        {
            var startTime:Number = getTimer();
            for (var i = 0; i < numberOfTimes; i ++)
            {
            var loc:Location = new Location (rnm() - rnm(), rnm() - rnm());
            var distance:Number = loc.Length();
            }    
            var duration:Number = getTimer() - startTime;
            trace ("Using a custom made class " + numberOfTimes + " calculations took: " + duration + " seconds");
        }
        
        private static function doUsingMethod():Void
        {
            var startTime:Number = getTimer();
            for (var i = 0; i < numberOfTimes; i ++)
            {
            var distance:Number = getDistance(rnm(), rnm(), rnm(), rnm());
            }    
            var duration:Number = getTimer() - startTime;
            trace ("Using a method " + numberOfTimes + " calculations took: " + duration + " seconds");
        }    
        
        private static function getDistance (x1:Number, y1:Number, x2:Number, y2:Number)
        {
            var xd:Number = x1 - x2;
            var yd:Number = y1 - y2;
            return ((xd*xd)+(yd*yd))^0.5;
        }
        
        private static function rnm ():Number
        {
            return Math.floor(Math.random()*(500));
        }
    }
    And the custom made class (Location):

    Code:
    class Location
    {
        public var x:Number;
        public var y:Number;
        
        function Location(x:Number, y:Number)
        {
            this.x = x;
            this.y = y;
        }
    
        public function Length ():Number
        {
            return ((x*x)+(y*y))^0.5;
        }
    }
    Also some more usable threads on the subject of speed:
    http://www.kirupa.com/forum/showthread.php?t=285243 (and the 2 links I apparently posted)
    http://www.kirupa.com/forum/showthread.php?t=281686
    http://www.kirupa.com/forum/showthread.php?t=276114 (and the 2 links already listed in this very post)
    http://www.kirupa.com/forum/showthread.php?t=292307
    http://www.kirupa.com/forum/showthread.php?t=294827
    Last edited by ArmoredSandwich; June 24th, 2008 at 06:07 PM. Reason: Benchmark done!

  14. #14
    Quote Originally Posted by ArmoredSandwich View Post
    And talking about stuff to increase speed, you should talk to TheRobot, things he does to increase speed is amazing xD
    I think you're joking
    you = function(){
    setEnabled( true );
    live();
    setEnabled( false );
    }

  15. Quote Originally Posted by therobot View Post
    I think you're joking
    I was mistaking you with jerryscript, didn't I correct it?

    EDIT: Yea, I did. As you can see now xD Sometimes all these names just get confusing , I hope you don't mind.
    Last edited by ArmoredSandwich; June 25th, 2008 at 06:38 AM.

Page 1 of 2 12 LastLast

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  

Home About kirupa.com Meet the Moderators Advertise

 Link to Us

 Credits

Copyright 1999 - 2012