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

[Pete Shinners <pete@shinners.org>]

Zak Arntson wrote:
> 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)
the algorithm is pretty sound, the big problem is how often this 
function is probably being called. the best bet is to think of the 
common cases where this test will fail. i'm not sure of your gameplay 
but i'd pick some of these from the list and try to apply them.


* at a close distance is "any" temple close enough?
  stop the search once you find a temple within range.

* is there often only one temple?
  no need to search, special case len(self.temples) == 1

* do the movers not need this info every frame?
  they can calculate it once every second or so and hang onto it.
  if there are many movers, stagger there calculations so they
  don't all do the calculation on the same frame.

* is map extra wide?
  keep temples sorted by x and pick a spot to start searching
  or do the opposite if map is tall and skinny. do more of a
  1 dimensional search with this.

* do temples rarely move/change?
  keep a low resolution grid over the map, find the closest
  temple to all grid coordinates. then pick the closest
  coordinate for each mover.

* are there many temples on a huge map?
  cut the map into sections and start with the closest sections.
  you could use a BSP, or something less fancy.


nitpick python optmizations

* match integer/float types
  since you are using rects this is integer, make sure 'pos' is ints

* no globals or attribute lookups in tight loop code
  this is the last thing to do, but will speed you up. especially
  as your loop goes through different test cases.