gSkinner - Home

ProximityManager updated for AS3

Posted on January 4, 2008 by Grant Skinner

A few years ago, I released an AS2 version of ProximityManager class, which allows you to efficiently track the proximity of large numbers of sprites. You can read a full description of the approach and uses here.

In the last month a couple of people have left comments indicating that they were having difficulty porting it to AS3. This prompted me to port it and do some significant optimizations. The new class runs a lot faster than the original, and is worth taking a quick look at in comparison with the AS2 version even if you don’t use it in a project.

Optimizations:

  1. removed two-dimensional arrays (which are very inefficient, especially in AS3) in favor of using a single array using an aggregate x/y index. The aggregate index is assembled with bit operators to make it even more efficient.

  2. added a simple caching mechanism, so that subsequent calls to getNeighbor for the same grid position do not need to recalculate the results

  3. used a Dictionary instance to hold managed items, which makes it much more efficient to remove objects on the fly.

  4. took full advantage of types and casting

  5. other minor tweaks

Note that these optimizations impose a limit of +/- 1024 rows and columns on the ProximityManager. This shouldn’t be an issue though: even with a gridSize of only 25 pixels, you would still have an area of 51200 pixels wide and high to work with.

I thought I would recreate the same demo as in my original post to see how it performed. It has five times as many sprites (600 vs 120), and ten times as many connections (~2800 vs ~280), despite the main bottleneck in this demo being the graphics performance. I benchmarked it without graphics, and it seems handle a couple thousand sprites quite easily.

You can grab the source code for the demo and the ProximityManager class here.

Follow @gskinner on Twitter for more news and views on interactive media.
23 Comments

The second link isn't working. misspelled href!

Posted by: Tim on Jan 4, 2008 2:54pm

Very cool though

Posted by: Tim on Jan 4, 2008 2:58pm

Fixed. Thanks for the heads up Tim!

Posted by: Grant Skinner on Jan 4, 2008 3:08pm URL: http://gskinner.com/blog/

Great work Grant. I just ported over your AS2 version to AS3 only a couple days ago. I'm glad to see the update and that this new class is more optimized than the previous version.

Thanks again for the release!

Posted by: Seth on Jan 4, 2008 8:38pm

[quote]Fixed. Thanks for the heads up Tim![/quote]

um... not quite!

Posted by: dAN on Jan 5, 2008 2:04am

You absolute legend! I've been waiting for an upgrade to this class for ages. This class is going to be so useful! Thanks!

Posted by: Vyper on Jan 5, 2008 5:30am URL: http://www.fatal-exception.co.uk

Thank you! Thank you! Thank you!

-t.

Posted by: Timbot on Jan 5, 2008 8:54am

dAN / Tim - fixed for sure this time. Not sure why Moveable Type didn't publish the change the first time. *shrug*

All - glad people are finding this useful. I'd love to see what it gets used for. Cheers.

Posted by: Grant Skinner on Jan 5, 2008 2:51pm URL: http://gskinner.com/blog/

I was looking for something like that. Thanks.

Posted by: Simon on Jan 24, 2008 5:05pm

It would be nice to see an example that combines this and hittesting. For example, when in proximity, hittest between neighbors to see if they're touching (for odd shapes sprites/movieclips). I tried something like:

if (neighbor.y > sprite.y) {

if (sprite.hitTestPoint(neighbor.x, neighbor.y, true)){ }

}

But this didn't seem to work correctly.

Posted by: Seth on Feb 1, 2008 12:37pm URL: http://ssandler.wordpress.com

Great job. In the sample you could add some alpha channel when the sprites are farer away and the alpha gets smaller when they are closer. This would give a nice effect. And gravity or springing between the sprites would be great too. I think it is calld "i don't know more who's" garden

Posted by: Pedro on Mar 5, 2008 7:51am

If this is as useful as it appears then: THANK YOU VERY MUCH :D

I was just grimacing at the idea of tracking collisions for all these items but convinced myself it was worth looking for ideas online. I don't usually use other peoples' code outright, fear of not knowing what's going on I suppose, but I think this warrants it.

If you're ever in Sheffield, UK and feel thirsty, give me a shout :)

Posted by: Martin Lyne on Aug 10, 2008 3:56pm

Hi Grant, and congratulatiion for your whole work wish is a real source of knowledge for me !

I'm currently workin on a flocking (like birds) manager for 3D as3 renderer (away3D, papervision). exemple:

http://www;agence-anonyme.com/lab/treeflocking.html

And the proximity manager can be a great help when you have to deal with 500 object3D interactions + the whole renderer pipeline...

If I understand this method,in order to create a 3D proximity manager, I would only have to cast mc as Object3D instead of DisplayObject and set a z parameter in the array.

Am I wrong ???

Could I do this that way by changin this only line ??I don't see other way...

var index:uint = ((mc.x+off)/gridSize)

Posted by: Ben on Jan 9, 2009 8:37am

AAARRGHHH!

My last comment had a bug when published,

it deleted most of my code...

well, it was about adding a z parameter the same way as the y in the line begining with var index:uint=mc.x+off)/gridSize)....

thanks.

Posted by: Ben on Jan 9, 2009 8:41am

I fixed the ProximityManager 3D for away3D, and I'm gonna make it for Papervision.

I just would like to know if I could release it and share it with the community ????

Waiting for your agreement...

thanks.

Posted by: Ben on Jan 10, 2009 9:15am

please release the PV3D flock manager. I don't see why you can't release it, his code has been released to the public so as long as you post in your code a comment showing where the original code was taken from I don't see how its any different? Your demo is cool. thx.

Posted by: zurie on Mar 25, 2009 3:25pm

In .fla file you have:

if (neighbor.y > sprite.y)

{ g.moveTo(sprite.x,sprite.y); g.lineTo(neighbor.x,neighbor.y);

}

but, it can be avoided (and make further optimization) if in getNeighbors() avoid querying for Array for cells with smaller indexes.

In other hand, this would make ProximityManager non-universal.

Posted by: krdr on May 14, 2009 5:00am

I just found one more optimization. Effectively, you connect sprites that can be 2,8*grid size distant from target sprite. By checking distance, number of connections will be reduced, and drawing will be faster.

Posted by: krdr on May 14, 2009 6:08am

very nice. can i ask what your reason for scaling down the objects?

sprite.scaleX = sprite.scaleY = 0.5 + l * 0.05;

Posted by: Aaron on Nov 18, 2009 8:31am

if you want to modify it to use the mouse position all you need to do is alter the getNeighbours function to pass a dynamic variable instead of display object and then pass a Point object: new Point(mouseX, mouseY);

Posted by: Dan on Jan 27, 2010 10:31pm URL: http://visualjazz.com.au

This class looks really useful!

Could you explain how to use the Proximity Manager? If I have 10 random sprites on the stage, how can I check their proximities using this class? The example seems to focus on animation effects but doesn't really explain how to use it :-)

Posted by: Henk Duivendrecht on Mar 2, 2010 2:04pm URL: http://www.prut.nl

Hey, thanks very much for releasing this class, its a life saver!

I'm having a strange problem though, I have implemented it fine into a project and it runs without error. But for some reason some sprites are given connections at distances longer than other sprites. see (http://img231.imageshack.us/img231/4363/connectionsn.jpg) for an example of what I mean. The only code I have changed is the length of distance to check for(75). And have commented out "if (neighbor.y > sprite.y) {" as for some reason it wont draw half of the connections with it in.

Any help is much appreciated.

Posted by: Adam J on Apr 30, 2010 4:39am

Could this be done like a hierachical hash grid that allows you to insert objects at differnet sizes and levels?

Posted by: Glidias on Jun 3, 2010 10:54pm URL: http://awr

Leave a Reply

Your email is never published nor shared.




You may use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre lang="" line="" escaped="" highlight="">