About a year ago I released this demo of grid based proximity management, which was loosely based on some work I had done in Flash 5 (at that time I was calling it zone interaction). Briefly, it allows you to determine which sprites on a 2d plane are near to one another. It is very efficient, and can deal with literally hundreds of sprites (the main limitation is usually the sprites motion and graphics, not the proximity management). For instance, with 350 sprites grid based proximity uses about 700 operations whereas normal iterative proximity testing would use about 61000 operations. For a description of the concept, see my original post on the subject.
When I made the original post, I said I would "be releasing the ProximityManager class in the next few weeks, once I have a chance to play with it further." Well, I played with it a lot, have used it commercially a few times, and mentioned it in a number of conferences, and still neglected to release it (I'm a naughty boy). Fast-forward to last week, when:
- We rolled it into 2 more projects.
- I received a bunch of emails asking when I would release it.
- Keith (bit-101) released a few experiments based on the concept.
- Brandon (waxpraxis) released a demo using the concept.
And I finally thought I had procrastinated long enough. I have whipped up a simple demo, and made the full class available for download below.
The ProximityManager class is pretty easy to use. There's only 4 public methods, and a single public property.
myProxMgr.gridSize - property indicating the granularity of the grid.
myProxMgr.addItem(mc) - adds a movieclip to be tracked by the manager.
myProxMgr.removeItem(mc) - removes a movieclip from the manager.
myProxMgr.getNeighbours(mc) - returns an array of movieclips that are neighbours of the specified clip.
myProxMgr.refresh() - recalculates the grid registration of all of the tracked movieclips.
You can download the demo and AS2 class by clicking here.
If you use the ProximityManager, or have ideas on how to improve/optimize it, let me know in the comments. This class could be extremely useful to the whole community, so it would be great to see it continue to improve.
UPDATE: An optimized AS3 version of the source code is now available here.
Comments (24)
I remember someone did something similar 2 or 3 years on www.were-here.com. I never tried it out, but the idea was always in the back of my head. Your earlier post bumped it a little closer to the front of my head, where it finally found its way out. Nice idea to make a class out of it. Might be worth mentioning that if you are using this type of system for collision detection, the grid size should be the width/height of the largest object. I'm pretty sure that'll get you the best efficiency without missing any hits.
Posted by: Keith Peters at February 2, 2005 09:59 AMURL: http://www.bit-101.com
That's correct. Your grid size for collision detection should be the same as your largest sprite width or height.
Also worth noting - you can set up multiple instances of the proximity manager to track different types of sprite. For instance, my eco experiment at:
http://www.gskinner.com/blog/archives/2004/04/experiment_6kb.html
Uses 3 proximity managers, one for prey, predators and food.
It's also fairly easy to avoid redundant checking within the same group of sprites - the simplest solution is to just assign a numeric id to each sprite in the group and only test siblings against sprites with higher id numbers. I didn't want to make this an inherent part of the ProximityManager class, because I usually use it to compare different types of sprites (ex. "bullets" against "enemies"), but maybe I'll update the demo to reflect this and re-upload.
Posted by: Grant Skinner at February 2, 2005 10:09 AMURL: http://gskinner.com/
The demo has now been updated to show how to remove redundant checks.
Posted by: Grant Skinner at February 2, 2005 10:22 AMURL: http://gskinner.com/
Grant,
This is a very cool class - however, I appreciate it more for it's cleverness and coding elegance than its usefulness.
Can you give us a few examples of how you've actually used it, in a real-world setting? What types of projects did you use it in?
Cheers!
Posted by: stuehler at February 2, 2005 01:22 PMURL:
stuehler,
The most obvious commercial applications are games to support collision detection. We also recently used it in a data visualization scenario where we needed to iterate through data points that were in close proximity to one another - it had the potential of up to 1000 points being tracked at a time, so the ProximityManager was a life-saver. It would have taken nearly half a MILLION calculations if we did it iteratively, but with this system it only carried out around 2000 operations, which didn't even cause a perceptible slow down.
Posted by: Grant Skinner at February 2, 2005 02:24 PMURL: http://gskinner.com/
It'd be cool to set this up to not only check against movie clip, but against arbitrary data-types that conform to an interface (eg: must have an _x and _y property, or the ProximityManager must have the properties to set what properties on the objects passed to use as the x/y co-ordinates). That way, you could build data visualizations based on raw data, without needing to create a movieclip for each piece of data.
Really cool, though, dude.
Posted by: Jason Nussbaum at February 2, 2005 04:27 PMURL: http://www.jasonnussbaum.com
Actually, I've done exactly that in a few implementations. You just have to switch the typing on addItem and removeItem to Object, and it will work with any object that has a _x and _y property.
Posted by: Grant Skinner at February 3, 2005 01:37 PMURL: http://gskinner.com/
Cool. You could go the extra step of allowing the consumer to set what properties of the objects get used as the x and y co-ordinates. you lose a bit on the type-safeness, though arguably you lose that by typing to Object, anyway...
Posted by: Jason Nussbaum at February 3, 2005 02:09 PMURL: http://www.jasonnussbaum.com
Sorry, no...you absolutely lose type safety/checking by typing to Object.
Posted by: Jason Nussbaum at February 3, 2005 03:10 PMGotta stop thinking with my fingers.
URL: http://www.jasonnussbaum.com
If you want to zoom in to a grid and efficiently decide which dots/sprites/whatever you want to render because they are still visible on screen, you can use a related algorithm that stores upper/lower/left/right bounds for a unique id in a given square.
In the one-dimensional case all you need to to is loop through from the left to right and for each grid section find out what the lowest value of sequential ids there is in the grid. Then you can do the same from right to left with the highest value. Then when you need to find out which items you need to render depending on zoom, you simply look at the left bound, the right bound, and select the value of the id from the left bounds array and the right border from the right bounds array.
Then when you do a zoom in/out, instead of naively checking whether a said item needs to be rendered, you just look at your array and decide to render everything inside of the bounds that you have set up. Thus there's no if AT ALL in your rendering loop, you simply abandon sprites that you guess don't need to be rendered. Since garbage tends to accumulate on the sides, you put all of the sprites inside a movie clip and mask it so the borders where garbage accumulates don't show.
I used this algorithm on http://www.moviestimeline.com, and squeezed 45-60 fps while moving about 150-200 sprites (in low quality mode, but with some PNG transparency).
Posted by: Patrick Mineault at February 4, 2005 06:02 PMURL: http://www.5etdemi.com/blog
Thank you for this. Very simple, yet ingenious class. This actually might help me with a project that I want to try out. I was thinking you can use this class to simulate gravity between objects. My idea involes using your Proximity code to for a perimeter ariund an object(like a planet) where gravity would be felt. The larger the mass(and therefore gravity field), the larger the perimeter. Anything outside would be considered too far for the gravity to have any impact. Anything inside would have the necessary gravity applied to it based on distance.
Not sure if I'd feel the same operation-reducing benefits of your original code(since this involves looking out for objects multiple tiles away). But once my inner programmer gets started...
Think it has a good chance of working?
Posted by: Manny Fleurmond at February 7, 2005 09:52 AMURL: http://www.isparkdesign.com
Something sort of like this, Manny:
http://www.professorfripples.com/mxlab/primordialUniverse.swf
This is a single alrgorithm I'm playing with that handles implosion, explosion, and gravity clustering with 100 objects. It's really system intense so it may take about a minute after the explosion to work itself into gravity wells. I wrote this long before seeing Grant's proximity class, so I haven't incorporated it yet. Given how well it runs without Grant's class, I figure the proximity grid will make it atleast fast enough to double the number of objects.
Posted by: Intoxo Pox at February 7, 2005 10:11 AMURL: http://www.professorfripples.com
Yeah, that looks cool. Do the objects effect each other no matter what the distance or is there a limit? And how many operations do you think it performs per second?
Posted by: Manny Fleurmond at February 7, 2005 10:35 AMURL: http://www.isparkdesign.com
There is a minimum distance before gravity effects are felt by neighbors. As far as how many operations.... too many. Atleast 105,000 per second. Grant's class should help take care of that, though.
Posted by: Intoxo Pox at February 7, 2005 01:16 PMURL: http://www.professorfripples.com
Hi Grant
I saw your talk at MXDU and have to say I was very impressed. One of the best sessions I went to in the whole conference.
One of the examples you showed when talking about proximity was a firefly's clip... one with lightning that shoots between them when they get excited. I've been looking for that on here so I could show some friends but haven't been able to find it. Found the proximity firefly experiment but that is missing the cool lightning effect.
Just wondering if you have this available to view anywhere online? I'd love to see it again.
Thanks!
Posted by: Sam at February 28, 2005 03:38 PMSam
URL:
Sam,
That project can be found along with some other very cool pieces on the online iamstatic gallery space at http://www.iamstatic.com/
Glad you enjoyed the session.
Posted by: Grant Skinner at February 28, 2005 04:30 PMURL: http://gskinner.com/
Nice work, as usual grant.
Hows about setting the grid size dynamically through the addItem method, to ensure that the largest object it is looking after?
could also look at dynamically changing the grid size based on the number of items in the grid, to improve performance if necessary.
Posted by: Keith Salisbury at March 8, 2005 10:27 AMURL: http://www.nakedpenguinboy.com
I saw you commented that the grid size for collision detection would be the size of the largest sprite width or height, but if I understand the math correctly, the proximity manager reports neighbours up to (gridSize * 3) distance apart (due to rounding approximations) - so the optimal gridSize would then be:
largest dimension * (2/3)
Am I right?
Posted by: Scott at March 29, 2005 04:51 PMURL:
Is it true that your grid approach can be slower than the regular iterative approach when the number of sprites is not big enough and the operations on each sprite are simple?
Posted by: Douglas Chen at April 26, 2005 09:33 PMURL:
Im currently trying to get to grips with some OOP principles for use with AS2.0 and it helps to see other developers approaches. The biggest surprise I got was how concise it was. On a sidenote, I also found you eventHandler entry very informative. Great stuff, thank you.
Posted by: Taff at June 9, 2005 01:44 AMTaff
URL: http://www.flash-genie.de
would it be possible to use this class to detect how close the mouse is to a given mc?
Posted by: jed hurt at October 19, 2005 08:04 PMURL:
Jed: The proximity manager is built to check a given mc's grid position compared to a bunch of other mcs. You could modify the ProximityManager class to accept an object in the getNeighbours() method, instead of a movie clip, and pass it an object as such:
var p = new ProximityManager();
onEnterFrame = function() {
p.update();
trace(p.getNeighbours({_x:_xmouse, _y:_ymouse}));
}
I didn't test it, but you get the idea.
Posted by: Lanny at October 20, 2005 01:20 PMURL: http://gskinner.com
For fun I tried to convert this to AS3 and its not working for some reason. Anyone else try?
Posted by: Layne at December 10, 2007 08:07 PMURL:
Yeah, I'm having trouble porting it to AS3 as well.
Posted by: Demise at January 1, 2008 07:36 AMURL: