Ian Mallett wrote:
Yes, I've tried this, but there are issues with points being in two separate places. For example, if the collision radius is 5, and it is 3 away from the edge, then all the points in the neighboring trees must be tested.
Rather than a tree, you may be just as well off using a regular array of cells. That makes it much easier to find the neighbouring cells to test, and there's also less overhead from code to manage and traverse the data structure. The only time you would really need a tree is if the distribution of the objects can be very clumpy, so that you benefit from an adaptive subdivision of the space. Another possibility to consider is instead of testing neighbouring cells, insert each object into all cells that are within the collision radius of it. That might turn out to be faster if the objects don't move very frequently. -- Greg
