Improve collision detection using spatial indexing
Closed this issue · 2 comments
The current collision implementation doesn’t have a broad phase, and has n^2 complexity, because every two bodies are tested against each other.
The idea of the broad phase is to reduce potential number of collisions by building a tree that segments the space and indexes bodies inside the branches. Then this tree can be used to lookup bodies that exist within certain bounds. This lets us reduce the number of possible collision pairs.
I don’t have enough knowledge on this topic, but AABB tree seems to be what we need.
I don't have a lot of experience here, either, and very close to zero in doing this with functional programming, but it's interesting. As I understand the theory, there are two basic approaches:
One approach uses "relative indexing" to dynamically structure and re-balance your index based on the actual (relative position) values of your objects as your data evolves. The idea is to systematically divide clusters of localized objects into roughly-equal-sized sub-clusters of even-more localized objects using whatever criteria (cutoff values) best suit the current data.
The other approach uses "absolute indexing" to divide your 3-space before-hand into fixed nested sectors with some "reasonable" min (resolution) and max (range) dimensions. The cutoff values suit the space rather than the data. You map each object to the smallest indexed sector (typically an AABB) that completely contains it. Each AABB maps to a fixed linear code that represents a position on a fractal path through 3-space. These codes can then be used as keys to vicinity maps. The maps allow iteration over ranges of locations to find their contained objects. I have slightly more experience with this approach.
After a thorough investigation, it looks that the broad phase is not the performance bottleneck, but the solver is. Closing this for now.