Re: [pygame] Python and Speed

[Casey Duncan <casey@xxxxxxxxxxx>]

On Apr 17, 2008, at 12:26 PM, Ian Mallett wrote:
> On Thu, Apr 17, 2008 at 12:15 PM, Casey Duncan <casey@xxxxxxxxxxx>  
> wrote:Note this is not the most efficient way to do this, using a  
> partitioned space you may be able to avoid comparing most points  
> with one another most of the time. To do this in 2D you could use  
> quad-trees, in 3D you could use oct-trees. See: http://en.wikipedia.org/wiki/Octree
> 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.

Partitioned space is certainly a more complex algorithm, but so long  
as all of your "points" (spheres?) are not close together, it is  
usually vastly more efficient. If the partition size is optimal, than  
the vast majority of particles will not be hitting the edge of a  
partition, that will be an edge-case (pun intended). Even for those  
that are it's usually still faster than the naive O(N^2) method that  
compares every point with every other.

This algorithm is only effective if the space is large relative to the  
collision geometries and they tend not to be clumped very close  
together.

-Casey