Spatial Partitioning. Part 1: Survey of spatial partitioning solutions
A quick note:
Being my second post here at #AltDevBlogADay, I was going to write about the commercial viability of XNA. However I'm just finishing up the architecture of our new spatial partitioning system, so I'll be doing this series first, while it's still in my head :)
Spatial Partitioning Series!
I'll be spending the next two (or more) posts on spatial partitioning. Starting this post is a quick survey of the spatial partitioning solutions I know most about. If you have a favorite that I don't mention, please do let me know in the comments!
What's spatial partitioning?
For those of you who are not familiar with the subject, you are forgiven. Spatial partitioning (quad trees and the such) are not really known for being the sexiest part of game development, that honor goes towards rendering or perhaps AI. However without a proper spatial partitioning choice, that awesome "moar bloom" being thrown at the screen runs into a brick wall trying to figure out what game objects are in the camera vs what is not. That's ultimately what spatial partitioning is all about: reducing the cost of finding objects you care about by storing objects in some sort of database that is easy to query by location. Instead of going on-and-on about it, I'd refer the beginners to wikipedia or perhaps the excellent "Real time collision detection" book on the market (chapter 2 and 7 specifically).
A Survey of the solutions
Here's a list of the various spatial partitioning systems that I happen to know about. I consider myself fairly well versed in the subject, so if some guru's happen to know of a gaping hole in my knowledge, please fill me in via the comments!
Perhaps the simplest solution, this is usually implemented via a 2 dimensional array. 3d grids are of course possible, but given that most 3d games have a generally 2d distribution, and the fact that 3d grids quickly eat your systems RAM, 2d is much, much more common.
There are generally 2 ways of using grids: Either each cell contains the objects who's bounding volumes (usually sphere or box) are center positions are located in the cell, or contain all objects that touch the cell. for the former case, the actual objects (and/or metadata) may be stored in the cell directly (allocated inline), or reference pointers are stored that point to the objects actual location. For the Later case of each cell storing all intersections, you are restricted to the reference pointer case.
Benefits / Drawbacks
The greatest benefit of grids is their simplicity, and virtually 1:1 mapping to simple 2d arrays. If you have a homogeneous or static world, grids may be a very excellent choice.
The greatest drawback is the inability to handle heterogeneous data: objects of various sizes and/or clumped distributions are huge problems that quickly ruin the elegance and performance of grids.
Benefits of cell inline allocation of objects is cache coherency, but since you have fixed cells allocated for the entire size of your world, you run the risk of each cell's allocations being both too big and too small if your world's objects are heterogeneously distributed.
A more exotic grid solutions include virtual grids, who's backing database is a hashtable. this reduces memory use but greatly increases the cost of queries, as multiple hash lookups need to made to find neighboring cells, plus memory fragmentation.
Grids also give good performance with dynamic objects, as due to it's fixed-space nature, there is no re-partitioning needed (which is not true with most other solutions!)
Quad trees are one of the most natural extensions of grids, and are primarily designed to overcome grid's biggest problems: heterogeneous sizes and distributions. In the classical case, cells are replaced with "Nodes" (cells, but reference based, not fixed allocations/alignments), and nodes with two or more objects are sub-divided until only 1 object is in each of the "leaf" nodes.
To enable elegant node sub-division, the center position of objects are used when determining ownership. The simple case keeps dividing down to 1 object per node, but this is not strictly necessary, and is easily customizable, though if it is more efficient for you to query against 1000 objects in 1 node or 1000 nodes, is an exercise for the reader or perhaps someone else's #AltDevBlogADay entry =D
Benefits / Drawbacks
Narrowly targeted queries are quite elegant, as walking from the root, you may reject large branches of the tree upon the parent failing to meet the query parameters. Broad queries however, offer fairly poor performance, of requiring deep traversals of nodes. For programming environments with a garbage collector like .NET or Java, the reference-class overhead of the nodes is substantial and can be problematic (gc stalls when running a game is not good!).
As mentioned, the nodes are partitioned based on object centers, which is quite a large problem due to "external" objects that may potentially overlap your node-of-interest when performing collision detection. Some exotic solutions such as storing pointers to neighboring nodes exist, but generally it's a pain in the ass and quite weak performance for dynamic objects. Another big weakness of trees are the need to repartition when dynamic objects move, the overhead of which can cripple highly dynamic simulations.
One potential benefit of trees is using the varied node sizes (nodes are cut in 4 each level) to bucket objects based on size. This also helps reduce the complexity of handling overlapping nodes, but it's still not a simple decision on how to handle this problem. some choices push the objects up to the first node that entirely contains them, but unfortunately this tends to push a large number of objects all the way up to the root, due to objects overlapping the partition boundaries (as an example, consider an object at (0,0) in the picture shown above)
Often cited as a solution are "loose" quad trees, but I dislike these for the same reason I dislike the seemingly coolsphere-tree: maintenance is a complicated mess and it's not so obvious how to customize the 'looseyness' to optimize performance in any given situation.
Another big caveat for quad trees is that they should not be used for heterogeneous distributions, as you will effectively have a cache-poor, pointer-based grid at the lowest level and a required tree-traversal on top. Generally for heterogeneous distributions, you are better served by a grid.
Though I mention many drawbacks, trees aren't that bad. their memory savings compared to grids under "clustered distribution" situations is considerable, while offering fast coarse-granularity partitioning, and it's darn simple to implement.
A cross between grids and a quad tree, think of it as pre-allocating all the nodes of a tree (whether they have objects in them or not). So with the respect of the two, they share the strengths and weaknesses of grids/trees based on these choices. I won't repeat them, you can simply read them above :)
Benefits / Drawbacks
Overall, I much prefer hierarchy grids over grids/trees, because the platforms I work on can afford the extra memory overhead, and it's actually quite advantageous to pre-allocate for my platform of choice (XNA/.NET) which reduces garbage collection pressure.
The biggest drawback to this is the expensive cost of querying empty cells.
kd-trees are kind of the uber-spatial-optimization of quad trees, where instead of sub-dividing the world into fixed sized cells, the spaces are sized based on the objects located inside (at least where they were at time 0).
Much the same as quad trees, except "faster" queries. However special care has to be made on modifications, as fragmentation occurs and the tree will need to be rebalanced to maintain high performance. Generally these are useful for offline pre-computation of static environments.
Benefits / Drawbacks
good for static environments (better than quad trees for localized, ray queries), but not the most trivial to implement, and is not a good choice for highly dynamic environments due to the additional costs of repartitioning.
Overall, the performance (and logic) is fairly close to quad trees. I dislike this choice because of the high repartitioning cost, and unlike a grid or quad tree, is a bit more difficult to debug.
Some-what a 'super partition' strategy is to subdivide the world by "room", often the dimensions of which are left up to content creators, and the connection of rooms performed by portals in addition to the potential for coordinate-system locality. A fairly well known example of this is the game dungeon siege.
While I have not personally experimented with this approach, it seems interesting. Perhaps not the way as described in dungeon siege, but I could say this approach being useful for "zones" in the world-of-warcraft sense of the word: allowing each zone to be subdivided by it's own partitioning system.
Also noted by the dungeon siege article is that there is a certain benefit to allowing artists to author the rooms, but also there is an incredible amount of complex infrastructure and toolsets that need to be developed to undertake their approach. I would consider this to be fairly risky, and costly, and puts an emphasis on hand-tailored content, which is a luxury none but the most AAA projects can afford.
Offset Hierarchy Grid (OHG)
The OHG is what I just finished architecting for Novaleaf's use. It's a hierarchy grid, with each level offset from the previous, to allow the benefits of "loosey" grids/trees without their unpredictable nature and maintenance overhead.
Usage-wise it's "just a grid", so gives the same benefits and tradeoffs. However obviously since I just architected Novaleaf's solution around the OHG, there must be some reason we went this approach, right? well if you are reading this far, I'm sorry to disappoint, but this will be the subject of my next blog post(s) Complain in the comments!!!
About the author:
Jason Swearingen is Technical Director at Novaleaf Game Studios.
You can reach Jason via email (jasons aat novaleaf doot coom), or twitter (@jasons_novaleaf).
PS: images courtesy of wikipedia
PPS: anything you want to know about in detail? again, let me know in the comments!!!