[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 18:53 America/New_York, Pete Shinners wrote:

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.
I was thinking about mentioning that one myself

* is there often only one temple?
  no need to search, special case len(self.temples) == 1
You'd have to call this function *a lot* in order for that to make a real difference.. And if you need that difference, it probably won't scale to more than a handful of temples anyway, so I wouldn't even bother with this.

* 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.
If you have an event-driven sort of API to your application, this kind of programming pattern can be a lot easier. Twisted's reactor is easy to mix in with pygame code for this purpose. You could write a more minimal one if you wanted, but it's probably not worth the effort).

* 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.
These three are pretty much the same problem. I'd personally just go for the BSP (maybe something more hash-like might be more appropriate in pure python?) at this point, because the other two have some fringe cases that probably aren't worth dealing with.

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.
* function calls are also pretty painful in a tight loop, setting up and tearing down frame objects hurts. consider using psyco at this point (when you're not spending most of your time debugging), because it can make x86 python kick some ass (you can JIT certain kinds of python code, inline functions, etc). The latest psyco I looked at has a platform-independent VM (without JIT) that you can use on other platforms, although I'm not sure what it does (I didn't poke at it for very long).

-bob