[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