Mike Chambers recently hosted a contest to write a faster version of my AS3 ProximityManager class (which was a lazy port of my AS2 version). Many of the results were blazing fast, but not really suited to or optimized for real-world use (including my entry, that took 2nd place).
I thought it would be good to release a more optimized version of my library that was designed for real use. This version is significantly slower in Mike’s benchmarks (about 2-3X slower), but that’s because it is tuned for real use cases, concerns itself more with memory use, and includes features like list management, non-zero origins, and variable radii.
It provides a good lesson – optimization is great, but it’s necessity in context always has to be weighed against API, feature, and readability concerns.
Here’s quick demo of it in action, showing 5000 items being updated and compared to the 4 bases every frame:
You can grab the code, docs, and demo here.
Feel free to provide any ideas on speeding it up further in the comments.
very cool! nice work…
I ran it for a few minutes (4?) and eventually the particles formed a diamond with its points on the top-center, left-center, right-center, and bottom-center edges of the stage. Is this intentional? Perhaps you have some sort of accumulated error… Still, it’s really cool!
Jackson – not intentional, but not an error. What’s happening is that items that are shot out of the side emitters at a 45 degree angle never come close enough to a “base” to be collected. Every other path does get collected, so you see a slow accumulation of items along that path. Given enough time, eventually all of the items would follow that diamond path.
It’s a bit of an emergent pattern.
If you leave it for a lot longer even more lines will appear: a sunburst from the center and then some diagonal lines from the corners, and some weird looking distribution holes in the open areas the possibly have some unholy explanation.
i like it: test artifacts for extra insight yes plz
I think one way (to speed it up) would be to rewrite your loops.
You have a rather slow approach like so:
var l:uint = items.length;
for (var i:uint=0; i
as always, nice stuff Grant! hope you talk about some of these ideas in Tokyo next wknd 😉
cheers
erick
This is really great. I’ve tried to make a grid based proximity system but it ended up being pretty slow. I’d love to hear an explanation of the two lines that do the storage:
var pos:uint = ((item.x+offX)*m|0)*h+(item.y+offY)*m;
grid[pos][lengths[pos]++] = item;
In particular what is m? And how come the y part doesn’t need to be rounded?
This is amazing, if you let it run for 6 hours, 6 minutes, and 6 seconds a shimmering eruption of orgasmic chaos bursts to form the pixelated face of man which last for 6 milliseconds. I was completely taken by surprise. Thanks Dr Skinner
@Deniss – The incrementing for loop is faster than the decrementing while loop, by about 45%.
Aaron – m is calculated in init() as 1/gridSize. Because multiplication is faster than division it is used instead of dividing by gridSize to calculate the grid position. The y value is floored when it is assigned to the uint pos variable.
leef – so you found the super secret easter egg, eh? I had hoped to use it to take over the world with subliminal messaging. 😉
Clever, thanks for the explanation.
Were any of these methods used in the lights demo you posted a few months ago? Speaking of which, have you come closer to releasing any source for those projects?
Very cool stuff, Grant.
Steve – I’m assuming you’re talking about these demos:
http://www.gskinner.com/blog/assets/circles/LightTest2.html
Those demos don’t use these methods. It could probably have sped up the collision detection a bit, but there aren’t that many items on screen at a time, so it wouldn’t have been a dramatic difference.
You’re right though… I should release those experiments. I’ll put that on my to-do list.
Thanks, Grant.
Grant- Thanks for the explanation. That makes a lot of sense!
That is pretty cool. its more interesting than the first versions of the proximity manager.i guess handling proximity is less costing than handling movement and angle reaction between each those particles?
I dont understand what the purpose of gridSize is? I am trying to use this for a pacman like project and wanted to use it to know where the player can move on the screen. I am placing 89×86 blocks on the screen and want to check to see if the player is going to run into a wall or not. Im told that hitTest() is slow so I was looking for another solution and this seemed to be one. Am I wrong in that assumption?
Hey, I think I found a small bug. I kept running into Vector “index is out of range” errors when my getNeighbor origin was the right edge of the screen, and I think it’s because the maxX and maxY are one index off:
var maxX:uint = itemX+radius;
if (maxX > w) { maxX = w; }
var maxY:uint = itemY+radius;
if (maxY > h) { maxY = h; }
Should be:
var maxX:uint = itemX+radius;
if (maxX >= w) { maxX = w-1; }
var maxY:uint = itemY+radius;
if (maxY >= h) { maxY = h-1; }
Since w and h are lengths, max index is length – 1.
Making the bounds of the ProximityManager larger than the bounds of your simulation also avoids out or range errors, but then those lines clamping min/max could just be removed anyway. 🙂
Used this for a quick prototype I was writing for FlashPunk.
After some trivial changes to fit it in and ensuring to use proper ‘bounds’, it worked wonders.
One more word: thanks!