On Thu, Apr 17, 2008 at 1:47 PM, Devon Scott-Tunkin <[EMAIL PROTECTED]> 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
