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.
UPDATE: The source code is now available here.