Re: [pygame] Python and Speed

["Nathan Whitehead" <nwhitehe@xxxxxxxxx>]

On Thu, Apr 17, 2008 at 1:47 PM, Devon Scott-Tunkin
<djvonfunkin@xxxxxxxxx> wrote:
>  Just out of curiousity as a complete newbie
>  programmer, would you set out 2d partitioning the
>  screen in pygame by making say 4 invisible sprites
>  with rects like say:

The way I do binning is to keep track of the bin for each sprite.  I
have a little function like:

def binnum(x, y):
  return ((x % BINSIZE) * 1000 + (y % BINSIZE))

When each sprite moves, the binnum for the sprite gets updated.  To
detect whether two sprites are colliding, first check the binnums.  If
they are in the same bin, start calculating distances.  Otherwise just
return NO.  This isn't 100% accurate since sprites might straddle a
bin division line, but that's the general idea.  To get full 100%
accuracy I do some stuff with keeping lists of bins that need to be
checked for each sprite.  So the function binnum returns a list
instead of just a number.

That gives you answers like "did sprite x collide with sprite y?", but
the full power of binning is answering questions like "which sprites
are colliding with which other sprites?"  To answer that question
quickly you also need to keep track of which sprites are in which bins
from the bin perspective, i.e. given any particular bin you get a list
of sprites in that bin.

I make "bins" a dictionary with the key being the bin number and the
value being the list of sprites that are in the bin.  When sprites
move, they first remove themselves from their existing bin, update
positions, then add themselves to the new bin.  I also removed the key
in the dictionary for empty bins.

To determine which sprites are colliding, you iterate over all the
nonempty bins.  For each bin, you do the obvious collision test for
all possible sprites in the bin.  Put all the collisions together for
each bin and you get all the collisions.

Why is this a speedup?  Every time a sprite moves the program now does
a little more work, but not much.  With the naive algorithm, checking
collisions for 100 sprites takes 100*99=9900 collision tests.  With
binning where you have 9 bins (3x3 grid on screen), you might only
have about 11 sprites per bin.  That is 11*10 tests per bin, or
9*11*10=990 tests total, a good speedup over 9900 tests!  If all 100
sprites huddle together in one spot, the binning won't help and you'll
still have 9900 tests plus a small overhead for keeping track of the
bins.

Binning will be in Chapter 20: "Optimization Techniques" of my
forthcoming book "Adventures in Game Programming: Creating innovative
games quickly using Python and Pygame".
--
Nathan Whitehead