[Tutor] Fastest (x,y) distance calculation

Zak Arntson zak at harlekin-maus.com
Wed Sep 10 13:56:21 EDT 2003


I'm using pygame, but the algorithm is basic enough to be cross-posted.

I have two classes, a Temple and a Mover class. Each have the a rect
attribute (which for non-pygamers, is an object represented by an
(x,y,width,height) tuple). Each Mover analyzes the list of Temples to find
the nearest one.

My Game class has the following method, called by each Mover during its
thinking phase. (non-pygamers: centerx and centery are the x & y values at
the center of the rect)

###
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]
    ...

###

It's basically taking advantage of the fact that:
    distance = sqrt((x2 - x1)^2 + (y2 - y1)^2)
And for integer x & y values, I can square the right side of the equation
for purposes of distance comoparison.

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?

---
Zak Arntson
www.harlekin-maus.com - Games - Lots of 'em



More information about the Tutor mailing list