ProximityManager updated for AS3

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.

Grant Skinner

The "g" in gskinner. Also the "skinner".

@gskinner

23 Comments

  1. The second link isn’t working. misspelled href!

  2. Very cool though

  3. Fixed. Thanks for the heads up Tim!

  4. 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!

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

    um… not quite!

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

  7. Thank you! Thank you! Thank you!

    -t.

  8. 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.

  9. I was looking for something like that. Thanks.

  10. 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.

  11. 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

  12. If this is as useful as it appears then: THANK YOU VERY MUCH 😀

    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 🙂

  13. 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)

  14. 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.

  15. 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.

  16. 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.

  17. 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.

  18. 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.

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

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

  20. 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);

  21. 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 🙂

  22. 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.

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

Leave a Reply

Your email address will not be published. Required fields are marked *