Re: [pygame] Fastest (x,y) distance calculation

[Magnus Lie Hetland <magnus@hetland.org>]

Zak Arntson <zak@harlekin-maus.com>:
>
[snip]
> I investigated BSP trees, but it looks like it would be difficult to
> maintain them on the fly for a large number of moving objects. For the
> static Temples, it's no problem. But I eventually want to have up to 100
> (or more, if I can optimize properly) moving objects that each know who
> the nearest object is.
> 
> Or are BSP trees the way to go?

Here is a discussion of some other spatial structures:

  http://citeseer.nj.nec.com/rigaux99spatial.html

There are also lots of approximate methods for finding the nearest
neighbour efficiently.

-- 
Magnus Lie Hetland                "In this house we obey the laws of
http://hetland.org                 thermodynamics!"    Homer Simpson