Effective data structure for overlapping spatial areas

Question

I'm writing a game where a large number of objects will have "area effects" over a region of a tiled 2D map.

Required features:

• Several of these area effects may overlap and affect the same tile
• It must be possible to very efficiently access the list of effects for any given tile
• The area effects can have arbitrary shapes but will usually be of the form "up to X tiles distance from the object causing the effect" where X is a small integer, typically 1-10
• The area effects will change frequently, e.g. as objects are moved to different locations on the map
• Maps could be potentially large (e.g. 1000*1000 tiles)

What data structure would work best for this?

Answer 1

Providing you really do have a lot of area effects happening simultaneously, and that they will have arbitrary shapes, I'd do it this way:

• when a new effect is created, it is stored in a global list of effects (not necessarily a global variable, just something that applies to the whole game or the current game-map)
• it calculates which tiles it affects, and stores a list of those tiles against the effect
• each of those tiles is notified of the new effect, and stores a reference back to it in a per-tile list (in C++ I'd use a std::vector for this, something with contiguous storage, not a linked list)
• ending an effect is handled by iterating through the interested tiles and removing references to it, before destroying it
• moving it, or changing its shape, is handled by removing the references as above, performing the change calculations, then re-attaching references in the tiles now affected
• you should also have a debug-only invariant check that iterates through your entire map and verifies that the list of tiles in the effect exactly matches the tiles in the map that reference it.

Answer 2

Usually it depends on density of your map.

If you know that every tile (or major part of tiles) contains at least one effect you should use regular grid – simple 2D array of tiles.

If your map is feebly filled and there are a lot of empty tiles it make sense to use some spatial indexes like quad-tree or R-tree or BSP-trees.

Answer 3

Usually BSP-Trees (or quadtrees or octrees).

Answer 4

Some brute force solutions that don't rely on fancy computer science:

1000 x 1000 isn't too large - just a meg. Computers have Gigs. You could have an 2d array. Each bit in the bytes could be a 'type of area'. The 'effected area' that's bigger could be another bit. If you have a reasonable amount of different types of areas you can still use a multi-byte bit mask. If that gets ridiculous you can make the array elements pointers to lists of overlapping area type objects. But then you lose efficiency.

You could also implement a sparse array - using a hashtable key'd off of the coords (e.g., key = 1000*x+y) - but this is many times slower.

If course if you don't mind coding the fancy computer science ways, they usually work much better!

Answer 5

If you have a known maximum range of each area effect, you could use a data structure of your choosing and store the actual sources, only, that's optimized for normal 2D Collision Testing.

Then, when checking for effects on a tile, simply check (collision detection style, optimized for your data structure) for all effect sources within the maximum range and then applying a defined test function (for example, if the area is a circle, check if the distance is less than a constant; if it's a square, check if the x and y distances are each within a constant).

If you have a small (<10) amount of effect "field" shapes, you can even do a unique collision detection for each effect field type, within their pre-computed maximum range.