sprite collisions
Ryan
trying to figure out how to check if sprites overlap.
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...
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?
Thanks!
Tristam MacDonald
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...
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?
--
Tristam MacDonald
http://swiftcoder.wordpress.com/
rollbak
> 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?
Below is some code to take as reference:
def collide(a, b):
dist_x = a.x - b.x
dist_y = a.y - b.y
dist = math.sqrt(math.pow(dist_x, 2) + math.pow(dist_y, 2))
if dist <= a.radius + b.radius:
return True
else:
return False
All optimizations that Tristam said, apply to this also.
Note that this method uses "sqrt", so it is not good at performance,
but there are ways to improve it, this is just an example code so you
can understand the basic idea.
On Apr 29, 12:00 pm, Tristam MacDonald <swiftco...@gmail.com> wrote:
Trixie
> 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 MacDonaldhttp://swiftcoder.wordpress.com/
I had asked a similar question about per-pixel collision over on the
Rabbyt group. The video demos on your site were excellent! I really
would be grateful for a tutorial!
Thank you!
Trixie
Arne Babenhauserheide
> 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
Ryan
> 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.
>
Tristam MacDonald
Ryan
>
> Anyway, take a look at my latest blog posting:http://tr.im/lwHR
>
> --
> Tristam MacDonaldhttp://swiftcoder.wordpress.com/
Ryan
Thanks to everyone who posted. I was able to get a huge speed
increase by implementing some of these suggestions.
I have run into a couple of new problems that I'm having trouble
solving. These are not pyglet issues, so I apologize if this is too
off-topic.
My game is a Super Mario style scrolling platformer. Sprites have an
additional "moving" flag, plus xv and yv.
First, I check for key presses - a jump sets the player's sprite.yv to
20, and left/right sets xv -2 or +2.
Then, I loop through all sprites flagged as "moving":
First, I decrease yv and xv by 1 (for gravity and wind/air
resistance).
Next, I do "sprite.y += sprite.yv" (and the same for x).
Finally, I check for collisions. Depending on where I hit the other
sprite (top, bottom, left or right), I correct the sprite's x/y, and
zero out the yv/xv. This is the first part I am having trouble with -
how do you know what side of the other sprite you touched?
If you were moving diagonally, and you had been both above and to the
left of the other sprite, you could have either collided with the
other sprite's top, or its left side.
I have figured out how to catch the majority of collisions - if you
were directly above it, or directly to the left of it, etc. But if
you were moving diagonally from the upper/bottom + left/right, I am
lost.
The second issue is, what if your yv or xv is so great that you pass
through objects? If the player fires a shot (a 2x2 pixel sprite), and
it has a xv of 20, it will not be collision checked against things in
between it and it's next due x/y. Or, if the player is falling for a
long time, his yv could become so great, he falls right through
things.
One idea would be to move objects only as far as they are wide/tall,
then do collision checking, then move them again, looping until they
reach their destination. But that would make "fast moving" objects
really expensive. Also, I do not know how to calculate something step-
by-step that is moving diagonally (ie yv=7, xv=19).
As an alternative, I figured I could calculate a box, with the
sprite's starting x/y and ending x/y, and check that box for
collisions first. But, if there is a hit, I don't know how to
calculate which specific other sprite I hit. Mainly because the moving
sprite could have been moving diagonaly.
Again, sorry if this is too off topic. I will say, for someone who has
never really written a game before, I am amazed at what I've slapped
together so far. Pyglet has made this really, really easy!
Niels Egberts
that my character can walk and jump on a straight line so the next
thing I have to do is also the collision detection. I once made a
mario-style flash game though.
Im interested in the answer of this problem but what I would do is if
the player is moving left and up, and its upper-left corner hits
another object. I would check if I bounced into the object to the
left, or that i am more to the right.
Another way of saying:
The points where 2 (1 standing still and 1 is moving left and up)
squares collide is an rectangle. If the rectangle is width>height then
It bounced onto the bottom. If the rengtangle is height>width it
bounced on the left.
I think that should suffice :-)
Tristam MacDonald
Im interested in the answer of this problem but what I would do is if
the player is moving left and up, and its upper-left corner hits
another object. I would check if I bounced into the object to the
left, or that i am more to the right.
Another way of saying:
The points where 2 (1 standing still and 1 is moving left and up)
squares collide is an rectangle. If the rectangle is width>height then
It bounced onto the bottom. If the rengtangle is height>width it
bounced on the left.
I think that should suffice :-)
Ryan
> move the sprite back towards the original position (in a loop,
> pixel-by-pixel) until no collision occurs.
line.
I stumbled on to this today: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
I have not had a chance to really grok it yet, but it looks like a
step in the right direction. Has anyone done anything like this in
Python? Are there other ways to accomplish this?
Right now, I am thinking this: Instead of changing a moving sprite's
X/Y, then doing collision checking, I should loop forward from its
starting point, 1 "step" at a time using an algorithm like the one I
listed above, until I collide with something. That would solve the
"moving through objects because I was going fast" problem. I think
that would also solve the "what side did I hit?" issue. But it seems
like this would be very slow...
Greg Ewing
> Right now, I am thinking this: Instead of changing a moving sprite's
> X/Y, then doing collision checking, I should loop forward from its
> starting point, 1 "step" at a time
If the collision shapes are assumed to be rectangles,
and the objects are moving in a straight line with
constant speed, then you don't need to move it a
step at a time -- you can directly calculate the
time at which the two rectangles begin to touch.
Do this twice, once for the x direction and once
for the y direction. Whichever of these gives you
the earliest collision time tells you which side
they collided on.
This technique can also help you deal with the
problem of objects passing through each other due
to large time steps. Find all the objects that the
sprite could possibly collide with (perhaps using
a bounding rectangle) and calculate the collision
time with each one. The object having the earliest
collision time is the one that gets hit.
--
Greg