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

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

Zak Arntson <zak@harlekin-maus.com>:
>
[snip]
> I can't think of a better algorithm for getting the nearest object
> than this.

There are several, actually. Some are based on spatial indexing and
the like, and you might find some standard ones in computational
geometry (at least there is a very common one for finding the two
closest points in a set). The simplest thing to do is probably to
divide your are into cells (spatial hashing, more or less) and to
search them outwards for candidates. That way you can quickly prune
away lots of candidates, and won't need to do any distance
calculations on the objects that are far away. The advantages of
fiddling with the distance calculation itself will be dwarfed by the
speedup you might get by the use of a proper searching algorithm.

For a survey of lots of relevant methods, see
http://citeseer.nj.nec.com/167339.html

(I've posted some stuff about this on the list before; then it was
about spatial (hash) join, for finding possible collisions.)

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