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

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

A few examples of spatial searches:
[/bquote]

[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]

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

[bquote]Some common examples: [/bquote]

[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]

[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]