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