Re: [pygame] Python and Speed

[Greg Ewing <greg.ewing@xxxxxxxxxxxxxxxx>]

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