Am Mittwoch 29 April 2009 17:00:22 schrieb Tristam MacDonald:
> 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.
If some of the sprites are close together, you can also create some kind of
bounding colliders which just have the attributes x, y, width and height.
The following is a simplified version. To make it really elegant, you can add
a collide function to the collider, which automatically recurses into its
contents (which can also be colliders in colliders) and at the end return
tuples of sprites which collide.
class Collider(object):
def __init__(self, *args):
self.sprites = args
self.x = min([i.x for i in args])
self.y = min([i.y for i in args])
right = max([i.x + i.width for i in args])
self.width = right - self.x
del right
top = max([i.y + i.height for i in args])
self.height = top - self.y
del top
When you have some connected objects, you first only compare bounding boxes
and when something collides with the bounding box, you do a collision test
against all included sprites.
coll = Collider(sprite1, sprite2, sprite3)
coll2 =Collider(sprite4, sprite5, sprite6)
colliders = [coll, coll2]
colliding = []
for i in collliders:
for j in colliders[i:]
if collide(i, j):
for a in i.sprites:
for b in j.sprites:
if collide(a, b):
colliding.append((a, b))
This still doesn't really scale linearly, but it scales far better than
quadratic.
I hope this helps you get going in optimizing collision performance,
Arne
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- ---
- singing a part of the history of free software -
http://infinite-hands.draketo.de
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
