Often, in games or visual experiments, you have to track the proximity of a large number of MCs relative to one another, and carry out actions when they are within a certain distance of one another.
Consider, for example, a side-scrolling shooting game where you might have 20 shot sprites from the player that need to check their proximity to 50 enemy sprites. The usual solution is to loop through every single sprite, and do a hit test or distance calculation against every single other sprite. In the previous example, each shot would check against each enemy, which would result in 1000 calculations each frame. Add another shot, and you will carry out 50 additional calculations per frame.
With grid-based proximity management, the screen is broken into a grid, and every sprite is registered to a tile on that grid each frame. You can then generate a list of sprites that are in the same tile, or an adjacent tile to any other sprite. This way, you are only carrying out calculations on the sprites that are within the nearby area – this is vastly more efficient as you increase the screen size and the number of sprites. Rather than CPU usage scaling in a largely exponential fashion (as in the iterative approach), the grid approach scales in a nearly linear manner
I’ve been playing with the idea of grid-based proximity management for awhile now (a couple of years actually), but just recently got around to building out a proper class to handle it cleanly and effectively. I’m not going to release ProximityManager just yet, because I want to play with some ideas I have for using in simulations, but I did want to show a simple example of it’s power.
In the following example, 120 sprites move randomly on-screen. Each frame, the proximity of every sprite is checked in relation to every other sprite, and those within adjacent tiles (25x25px square) are linked with lines. The more links a sprite has, the brighter and larger it appears, and the brighter it’s links are drawn. I tested this same scenario with iterative distance checking, and it slowed to a crawl (about 1 fps on my 12″ powerbook). You can see the results using the grid-based ProximityManager below (about 10fps on my 12″).
The number in the bottom right shows the number of links being drawn each frame.
I should be releasing the ProximityManager class in the next few weeks, once I have a chance to play with it further.
Cheers.
UPDATE: The source code is now available here.
You’re a madman!
Nice work!
Nice! (I get between 250 and 300fps on an AMD64-3000+).
In games, the precision has to be higher than the one given by those squares. What happens when you use 2×2 squares per example?
Awesome man.
Very nice!!!!
Looks familiar! Nice work. I’ve played around with similar grid based proximity stuff but never wound up implementing it in anything. Maybe I’ll give it another look now!
Thanks for the feedback. I’m going to be combining it with some neural tolerance concepts I’ve been toying with to build out a (hopefully) really cool ecosystem experiment.
iS – it’s actually 250-300 links, not fps, but you should be getting the full 30fps w/o any slowdowns on that system. ProximityManager allows you to set a gridSize property so you can scale the range for different scenarios. Contrary to what you might think, it actually runs much faster with a smaller grid, because there are less relationships to manage.
Keith – I originally played with it about 2 years ago… you can still see an example of it on http://zeroera.com/ in the lab. I just never did anything with it, and I never worked out the kinks.
Cheers.
Good stuff. I use something similar in this platform game.
http://www.yo-yo.com/sweepstakes/
It works great for both sprite/sprite and sprite/platform checking. If I remember correctly, mine just uses columns because of the way the platform engine works.
As for size of grid, I’ve found that it depends on the size of your sprites and how fast they move. The grid can be fairly coarse since its purpose is simply to limit the number of fine grained comparisons you have to do.
I have observed that sprites are moving from one edge to the other in a linear fashion. However, when they are raised to be a strong large square, they should have some sort of gravitational force to effect the other sprites directions. It should even alter its own direction due to the connections made. I know you are just displaying proximity tracking capibility, but since you added extra shining lines and scaling up sprites, you might wanna add this as well to make it more ecologic.
Very nice work! I’ll be looking forward for your further release.
If anyone is interested in the actual numbers involved:
Number of calculations per frame for this demo using the iterative method: 120 sprites x 60 (avg # of comparisons per sprite) = 7200
Number of calculations per frame using the grid-based method:240 (1 calculation to register each point, plus one lookup call to find neighbours).
With 200 sprites: 20000 versus ~400
With 350 (as in the proximity fireflies demo): >61000 versus ~700 (fireflies actually does ~1050 calculations).
This doesn’t tell the whole story, as the lookup call is somewhat more CPU intensive than the proximity calculation in the iterative method, but it will give you an idea of the CPU savings, nonetheless. With my new version, it caches lookup results, which results in better savings with large numbers of sprites, or coarser grids.
The concept is called “Nearest Neighbor.”
Using binary or octree data formats are the preferred (and much much more robust and powerful) methods of manipulating geometric proximity based information. Very very common technique in gaming.
Nice to see you are playin around with the idea. I’d check into the mathematics a bit more though. I’ve got a full implementation of the nearest neighbor approach for a 3d game engine I’ve been working on for as 2.0 if you want.
The concept is simple:
Each node or object stores it’s location on the large grid (quadrant-based pointer). Each object then broadcasts to local cells, based on the nearest neighbor tolerance.
With this method, there’s no iterative calls really, and you have much better opportunities to optimize than the approach above.
That gives you maybe 2 calls per run, per object. It’s 0(n) in computational scale if I recall correctly.
best.
Helps to actually read everything.
You did implement a variety of nearest neighbor. But, from what I can gather, it seems drastically more complicated than it really needs to be.
Do a google on nearest neighbor optimizations. that’ll push ya in the right direction … 🙂
Jon,
Thanks for the comments. While similar to Nearest Neighbour, this concept is not the same. Nearest Neighbour is used to find the nearest neighbour(s), not just the those within a specific proximity, and involves slicing space into a “grid” such that each object is within it’s own region.
Octree calculations are specifically for use in 3d space, though I suppose you could adapt them for use with 2 dimensions (Quadtree?). It also serves a purpose more similar to Nearest Neighbour, than the class in this experiment.
For the simple requirement of retrieving a single listing of all objects within ~n pixels in 2d space, this solution is simpler, and faster (I believe) than the solutions you proposed. It is also easier to optimize, as all logic/code resides in a single cohesive class.
Looks like we were both typing at the same time.
The ProximityManager is probably the simplest solution to this requirement. Nearest Neighbour is definitely a more complex algorithm.
Cheers,
Grant.
Yea, I hear what you are saying. I was looking into it more a while back when doing a grid based game, and needed to program nearest neighbor ai into the enemies.
I came across this interesting piece discussing the problem in relation to cellphone air traffic. Crazy.
http://citeseer.ist.psu.edu/saltenis00indexing.html
An interesting read nonetheless.
can’t wait to see what you did with the ProximityManager, does look sweet. 🙂
this is like an octree type system. When landscapes are static you can cut static scenery up based on a grid. Then for collisions just test against the part of the scene in your grid area. In a 3d scene the amount of gridsquares can get large: if you have a 10x10x10 grid then have 1000 cells. to cut down on cells an octree recursively cuts up the environment. In 2d this would be done by cutting the map in forths then dumping items into their quadrants. If a quadrant has > certain number of items then you recursively subdivide that quadrant. You can do this until you have a certain number of items in each quadrant or you have divided to a certain depth. This works for large static maps not for dynamic scenes where you have 1000s of objects moving around.