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

[Nicola Larosa <nico@tekNico.net>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

> ###
> class Game:
>     ...
>     def get_nearest_temple(self, pos):
>         distances = [((pos[0] - tmp.rect.centerx) ** 2 +
>                       (pos[1] - tmp.rect.centery) ** 2,
>                       tmp) for tmp in self.temples]
>
>         return min(distances)[1]
>     ...
>
> ###
>
> ...
>
> I can't think of a better algorithm for getting the nearest object than
> this. Profile tells me this is one of the slower parts of my code. Any
> thoughts/suggestions?

Probably Alex Martelli doesn't follow this list, so I will play one of his
standard pieces in his stead. ;^)

You don't want to square those values, it's slow, better multiply them by
themselves.

You also don't want to dereference those pos indexes, and find the
self.temples attribute, at each iteration. So you may rewrite the above as
follows (sorry for the loss of the fancy list comprehension ;^) ):

###
class Game:
    ...
    def get_nearest_temple(self, pos):
        posx = pos[0]
        posy = pos[1]
        temples = self.temples
        distances = []
        for temple in temples:
            distx = posx - temple.rect.centerx
            disty = posy - temple.rect.centery
            distances.append((distx * distx + disty * disty, temple))
        return min(distances)[1]
    ...

###


Another thing would be to compute those tmp.rect.center{x|y} ahead of time,
if possible, and mutate them into local variables, too. Don't know whether
this is possible, though.

Of course the best optimization would be a better algorithm. If you have a
really huge number of "temples", you may want to feed and care for more
complex data structures, like BSP (Binary Space Partition) trees, or something.


- --
"Python is not "pure" as languages like Lisp and Java attempt to be -
it abandons individual ideological standpoints (Object-Oriented! (Java)
Functional! (Lisp) Procedural! (Pascal) Efficient! (C) Expressive!
(Perl)) to produce a synthesis of all of the above that makes for
appropriate syntax for appropriate structures." -- Glyph Lefkowitz

Nicola Larosa - nico@tekNico.net


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.2 (GNU/Linux)

iD8DBQE/X5cWXv0hgDImBm4RApH6AJ9SSGtfMckN6FZK1AAyyGHH1pHZQgCfX1en
lWGA4YwyoXD5p1CI0q8XBio=
=8qPh
-----END PGP SIGNATURE-----