On Tue, Apr 28, 2009 at 8:08 PM, Ryan <[email protected]> wrote: > > As an example, I wrote a program that creates 100 sprites, and draws > them with batch.draw() during on_draw(). And I scheduled an update > that, 60 times a second, randomly changes the sprites's x or y > position a few pixels each loop. This runs great, very fast. > > Then, I compare each sprite to each other with this code I found on > someone's blog: > > def collide(a, b): > if a.y + a.height < b.y: > return False > if a.y > b.y + b.height: > return False > if a.x + a.width < b.x: > return False > if a.x > b.x + b.width: > return False > return True > > It works, but it's really, really slow (on a modern E8400 CPU). It > may be that this is a perfectly good technique, but I'm not using it > correctly...
The problem here is that you are comparing every sprite to every other sprite - with 100 sprites, that is 10,000 comparisons... You can cut this number in half fairly simply, by exploiting the fact that you if you have compared a with b, you don't need to compare b with a, something like this: for i in range(0, 100): for j in range(i, 100): collide(sprites[i], sprites[j]) However, this is still an O(n^2) operation. You can save much more time if you use some sort of partitioning structure to only test nearby sprites. Quad-trees and kd-trees are both popular (and simple) data structures for this sort of thing, or with a little greater complexity, you could try spatial-hashing. Also, this treats all sprites like boxes, and wouldn't work well if > the sprite is supposed to be a circle, a ball, etc. > > Does anyone have any code that handles this? I have some code that does per-pixel collision detection on sprites, I will clean it up and post it to my blog, hopefully by the weekend, as several people have requested it. Of course, per-pixel comparisons are far more expensive, so you probably want to implement spatial partitioning first. -- Tristam MacDonald http://swiftcoder.wordpress.com/ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "pyglet-users" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/pyglet-users?hl=en -~----------~----~----~----~------~----~------~--~---
