StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>One interesting method for doing collision detection is to use axially aligned bounding boxes (AABB's) organised within a special octree structure. The AABB's help because they make the coarse collision computations very quick to do because you only need to perform up to 6 comparisons.</p> <p>There are a couple of tricks you should use with the octree structure:</p> <p>1) The bounding area which a node occupies should be twice as large as it would be for a normal octree (where the octree partitions the space without overlap). As each node should overlap half of the area of its adjacent nodes. Since the AABB can belong to only one node this extra size and overlap allows it to remain in the one node for a longer period of time.</p> <p>2) Also in each node - and probably in each level of the hierarchy - you keep links to the node's neighbours. This will involve a lot of extra code but it will allow you to move elements between nodes in close to O(1) time rather than O(2logn) time.</p> <p>If the octree is taking up too much memory you could change it to use a sparse octree structure, only keeping the tree for the parts of the game world that actually contained entities. However this would mean that you'd have to perform more computations for each frame when entities move through the world.</p> <p>Some other ideas you might want to try instead of an octree is to use a kd-tree (I believe that's the correct name), or use AABB's to build the structure from the bottom up.</p> <p>KD trees (from memory) partition the space using axially aligned planes, thus they are a good fit for use with AABB.</p> <p>The other idea is instead of forcing the octree generation from the top down (starting with a box envoloping the whole world), you build it up from the base entities and construct bigger AABB's that grow until the biggest one encompasses the whole world. Though I'm unsure of how it would work with many fast moving entities.</p> <p>(It's been a while since I've done this kind of spatial game development coding.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload