[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: [pygame] Fastest (x,y) distance calculation
On Wednesday, Sep 10, 2003, at 17:26 America/New_York, Nicola Larosa
wrote:
###
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]
...
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.
Yeah, a better and more complex algorithm will surely help, however
doing the distance calculation and min in parallel should be measurably
faster (esp. in psyco or pyrex).. this also has the added benefit at
the super low level (from psyco or pyrex) that it does a little more
calculation between memory accesses, so it's probably less often
waiting due to access penalties.
import sys
class Game:
...
def get_nearest_temple(self, pos):
# assuming pos has two elements, this inline unpack should be faster
because I think it has its own bytecode
posx, posy = pos
temples = self.temples
mindistance = sys.maxint
mintemple = None
for temple in temples:
# the same inline unpack might help if temple.rect has a center
tuple..
# i.e. centerx, centery = temple.rect.center
# it would also save you 2 object attribute lookups
distx = posx - temple.rect.centerx
disty = posy - temple.rect.centery
dist = (distx * distx) + (disty * disty)
if dist < mindistance:
mindistance = dist
mintemple = temple
return mintemple
...
this code should surely be faster, _definitely_ will be under something
like pyrex or psyco. assuming N is len(temples), the additional work
done by the quoted code (compared to mine) is:
creation and garbage collection of 1 list and N tuples (at the
expensive of two local variable object references, which are
pathetically cheap)
N object attribute lookups of distances.append (could easily be
aliased as a local, though)
N calls to distances.append (calling stuff is particularly expensive
in python)
probably a few list resizes behind the scenes
an iteration over N distances (the min calculation, which is partially
in fast C code)
that has to rip open the first one or two elements of N tuples
-bob