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?

Laissezfaire

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.

Zenas

Thanks Kylotan - this seems like the most "comprehensive" approach to guarantee fast access. I think I may end up doing something like this but using a quadtree type approach for the per-tile storage, and maybe some type of clever cache for the per-tile lists to avoid lots of list duplication – Laissezfaire

I don't understand what benefit you get from the quad-tree: a tile map is typically (by definition) a 2D hash from position to tiles. You normally only need a quad-tree when you don't already have such a quick look-up system (eg. for continuous worlds, not tiled ones). – Zenas

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.

Ossiferous

Good thoughts - I guess the map is probably about 10-20% covered with area effects so a spatial index type approach is probably better – Laissezfaire

A spatial index allows you not wasting memory for unused tiles. But note that most of such indexes are designed to store static data. As I understand in you case all "affects areas" can move along the map, so you will need to rebuild/update spatial index all the time. This may cause significant overhead. – Ossiferous

Answer 3

Usually BSP-Trees (or quadtrees or octrees).

Bowens

What would you then put in the nodes to represent the area effects in a way that supports efficient query and update? – Laissezfaire

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!

Quadruplicate

There will be a large number of effect types so it'll probably have to be some kind of list. but then there is the potential issue that a single "up to 10 squares away" effect might require generating or updating 441 different lists....? – Laissezfaire

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.

Penal