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.
Comments (16)
very cool! nice work...
Posted by: samBrown at November 17, 2009 02:23 PMURL: http://www.twitter.com/explrcre8
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!
Posted by: Jackson Dunstan at November 17, 2009 03:03 PMURL: http://www.jacksondunstan.com
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.
Posted by: Grant Skinner at November 17, 2009 03:07 PMURL: http://gskinner.com/blog/
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
Posted by: Jeff at November 17, 2009 04:11 PMURL:
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 //code code code
}
A faster way would be:
var i:int = items.length;
while( i-- ) {
//code code code
}
Posted by: Deniss Alimovs at November 17, 2009 04:16 PMI'm sure you can work out why :)
URL:
as always, nice stuff Grant! hope you talk about some of these ideas in Tokyo next wknd ;)
Posted by: erick at November 17, 2009 09:43 PMcheers
erick
URL:
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?
Posted by: Aaron at November 17, 2009 09:44 PMURL: http://abeall.com
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
Posted by: leef at November 17, 2009 10:42 PMURL:
@Deniss - The incrementing for loop is faster than the decrementing while loop, by about 45%.
Posted by: Shawn at November 18, 2009 09:24 AMURL: http://shawnblais.com
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. ;)
Posted by: Grant Skinner at November 18, 2009 10:02 AMURL: http://gskinner.com/blog/
Clever, thanks for the explanation.
Posted by: Aron at November 18, 2009 08:02 PMURL:
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.
Posted by: Steve Kelly at November 19, 2009 01:44 PMURL:
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.
Posted by: Grant Skinner at November 19, 2009 01:53 PMURL: http://gskinner.com/blog/
Thanks, Grant.
Posted by: Steve Kelly at November 20, 2009 06:44 AMURL:
Grant- Thanks for the explanation. That makes a lot of sense!
Posted by: Jackson Dunstan at November 20, 2009 01:23 PMURL: http://www.jacksondunstan.com
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?
Posted by: AdityaGameProgrammer at January 13, 2010 07:47 PMURL: http://www.adityagameprogrammer.com