Best approach for checking a radius for objects

programming
1

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.

2

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.

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

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.


vector = new Point(stage.mouseX-clip.x,stage.mouseY-clip.y);
vector.length;
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 :smiley:

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

Demonstrates the concept
http://lab.polygonal.de/2007/09/09/quadtree-demonstration/

6

[quote=Fidodo;2347504]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.


vector = new Point(stage.mouseX-clip.x,stage.mouseY-clip.y);
vector.length;

[/quote]

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

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.

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

Here’s the link to the near finished Tower Defense game I was talking about:

http://www.dukesbox.com/games/game18.php?game=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

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

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.


distanceToCircle = getDistanceToPoint(x1,y1,x2,y2);
11

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

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


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

13

[quote=Fidodo;2348171]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.[/quote]

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


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):


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

14

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.

15

I think these are just different design philosophies. If you’re designing a cutting edge game that pushes the system to the limit, then yes, do everything you can. If you’re creating an database infrastructure that needs to handle thousands of requests at a time, absolutely take the time to cut corners. I’m not debating that using the Point class is fast, I’m just saying that in modern coding, speed is no longer the end all be all priority for casual applications like a small flash game. I mean some considerations aren’t even code related. How much time do you have to devote to optimization. How much will optimization help? Maybe the operation you are optimizing wont even be used that much. Maybe you will drop the project for a few months, and when you come back it would be nice to have easier to read code to return to. There are many variables to consider when designing. As for me, most of my projects don’t push the computer anywhere near it’s limits so I’m not concerned about optimizations, and more about extendability and readability for my own sake. The Point class just makes sense to me from an OO perspective.

Prioritization and hell, even maintaining your sanity are things to consider too. Take the easy way, or the quad tree way. Judge how important it is on a per item basis.

16

[quote=Fidodo;2349301]I think these are just different design philosophies. If you’re designing a cutting edge game that pushes the system to the limit, then yes, do everything you can. If you’re creating an database infrastructure that needs to handle thousands of requests at a time, absolutely take the time to cut corners. I’m not debating that using the Point class is fast, I’m just saying that in modern coding, speed is no longer the end all be all priority for casual applications like a small flash game. I mean some considerations aren’t even code related. How much time do you have to devote to optimization. How much will optimization help? Maybe the operation you are optimizing wont even be used that much. Maybe you will drop the project for a few months, and when you come back it would be nice to have easier to read code to return to. There are many variables to consider when designing. As for me, most of my projects don’t push the computer anywhere near it’s limits so I’m not concerned about optimizations, and more about extendability and readability for my own sake. The Point class just makes sense to me from an OO perspective.

Prioritization and hell, even maintaining your sanity are things to consider too. Take the easy way, or the quad tree way. Judge how important it is on a per item basis.[/quote]

True, but I always go for the best :slight_smile: