Spatial Index

Speed searches by position in a Model Database.

(C) 2000 - Zachary Booth Simpson. Copied with permission from http://www.mine-control.com/zack. If you find any of this work useful, please sign Zack's guest book: http://www.mine-cont...i/gbook-zbs.cgi.

[size="5"]Intent

[bquote]Speed searches by position in a Model Database.[/bquote]

[size="5"]Problem

[bquote]Almost all games need to search a Model Database quickly by location or region.

A few examples of spatial searches:

The renderer needs to cull objects which cannot be seen.
A trigger needs to determine if the player has passed over it.
The UI needs to determine what object was clicked on by the mouse.
The physics needs to detect collisions.
A time bomb needs to determine what to damage.

[/bquote]

[size="5"]Solution

[bquote] A Spatial Index accelerates spatial queries. Given a spatial key, the Spatial Index allows quick access to the database''s associated values. The Spatial Index may cache information from the database to speed queries. It may refer directly into the database''s values, or it may return a key which can be used to attain the value from the database. There are many implementations of a Spatial Index, but most either spatially subdivide the world to reduce the search space, sort the objects spatially, or use time- or space-coherency between look-ups to speed spatial queries--or some combination of all these techniques.

Indices must remain synchronized with the associated Model Database. It is common to see the spatial index implemented within the framework of a Model Database.

Spatial indices are often considered a View pattern optimization and become strongly associated with View code. Because the index is usually read-only by the view, but read-write by the model, it should probably belong more to Model code than to View code.[/bquote]

[size="5"]Structure

[bquote]Not available at this time.[/bquote]

[size="5"]Examples

[bquote]Some common examples:

Binary Space Partition Trees
X and Y Hashes with threaded collision resolution
Portals which link isolated spatial indices
Octrees

[/bquote]

[size="5"]Issues and Risks

[bquote] Conceptual confusion: A database index is not a database and vice versa. A single database may have multiple indices or no indices at all. An index is conceptually distinct from the database itself, and is an additional datastructure used to speed up queries on the database. For example, a book may have a keyword index, a table of contents, and an index of figures, or it may have none of these. In each of those examples, the text of the book is the database. We use a different index depending on what type of key you want to use to look up a page in the book. For the table of contents, the key is a concept. For the keyword index, it''s a word, and for the figure index, well, it''s a figure. You get the idea. A game may have an object database with an associated Spatial Index for the renderer, a different Spatial Index for the collision detector, and a "type index" so AIs can query based on the different types of bad guys.

Coupling: Spatial indices have a tendency to become too tightly coupled with their associated database, which can reduce flexibility and reusability. The index can be overly optimized for a particular subsystem leaving it less useful for another subsystem. For example, if the Spatial Index is highly optimized for and coupled to the renderer, the AI subsystem might have trouble using it to find the nearest enemy units efficiently.

Synchronization and duplication: The keys in an index must remain synchronized with the values in the database. This can be difficult if the index is cached to improve performance. If a unit moves in the database, the cached data in the Spatial Index must either be updated or invalidated. Uncoupling an index from a database can create synchronization problems. Data is often duplicated from the database to the index, which consumes resources (both memory and overhead keeping the data synchronized).[/bquote]

[size="5"]Uses and References

[bquote] See The Design and Analysis of Spatial Data Structures, by Hanan Samet (Addison-Wesley, 1990).

Also, Mike Abrash describes Quake's Spatial Index, called the Potentially Visible Set, on Blue's News at www.bluesnews.com/abrash. The PVS is actually a Spatial Index that references a BSP, another Spatial Index.[/bquote]