What is the best way to test if two sprites collide with each other? It’s a bit too rough to just check where their
bounding boxes are (i.e. if they overlap). Should I try to test the colors on the overlapping regions (so that if
the pixels are not the transparent , “do a collision”)?
– Ville Koskinen
@Ville_Koskinen
What is the best way to test if two sprites collide with each other? It’s a bit too rough to just check where their
bounding boxes are (i.e. if they overlap). Should I try to test the colors on the overlapping regions (so that if
the pixels are not the transparent , “do a collision”)?
Don’t quote me on this, but I believe you use a sprite mask to check
against…
Yours,
Andy GordonOn Thu, 17 Jan 2002, Ville Koskinen wrote:
QueriX UK
36A London Road http://www.querix.co.uk
Southampton
Tel: +44 23 8023 2345 andy at querix.co.uk
Fax: +44 23 8039 9685
It all depends on the shape of the sprites. The bounding box test is
perfect for rectangular sprites and is a good approximation for most any
shape of sprite. If the sprites are essentially round, then after doing
a bounding box test you can do a sprite center to center distance test.
Just test to see if the distance between the sprites is less than the
radius of either sprite. (If you are worried about it you can avoid the
square root by just testing the square of the distance.) You can build
versions of the distance test that use the angle of the line to
determine the contact distance. A table of distances indexed by the
angle of the line will let you approximate almost any shape of sprite.
If you need absolute pixel accurate hit testing, and you aren’t worried
about the time it takes to read pixels, then you can use Bresenham’s
line algorithm to find just the pixels between the centers of the two
sprites and look for a background color pixel along the line. This
technique works well for convex sprites.
to do pixel perfect hit testing for concave sprites you need to have a
record of the boundary of the sprite. The boundary table is usually just
a list of the (x,y) offsets from a corner of the bounding box of all the
pixels in the bounding box that are in contact with pixels in the sprite
but are not themselves part of the sprite. This can also be stored as a
sprite mask. You just check the pixels that are both in the intersection
of the two bounding boxes and in the table to see if any of them have a
non-background color.
In any case you want to use the bounding box test first because it is
cheap and then do a more costly test.
Hope that Helps
Bob Pendleton
Ville Koskinen wrote:>
What is the best way to test if two sprites collide with each other? It’s a bit too rough to just check where their
bounding boxes are (i.e. if they overlap). Should I try to test the colors on the overlapping regions (so that if
the pixels are not the transparent , “do a collision”)?– Ville Koskinen
viller.koskinen at iobox.com
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
–
±-----------------------------------+
Forgot to include a simple way to do the boundary pixel test.
A simple way to implement the boundary test is to keep around a bit mask
for each sprite. The bit mask for a sprite has one bit for each pixel of
the sprite. There is a 0 bit in the mask for each transparent pixel and
a 1 bit for each opaque pixel. Determine which bits from each sprite
mask are in the intersection of the bounding boxes. The bites and of the
bits in the intersecting part of the two sprite masks will contain a 1
bit for each pixel of the sprites that overlap. You can use shifts to
align the words from the two mask so that you can test all or most of a
word from each mask at a time which can make this a very fast test.
Be careful with the bounding box test, it only works if you always move
your sprites in small steps. It is pretty easy for the bounding box test
to let fast sprites pass right through other sprites and walls.
Collision detection based on line segment intersection tests are much
safer.> Hope that Helps
Bob PendletonVille Koskinen wrote:
What is the best way to test if two sprites collide with each other? It’s a bit too rough to just check where their
bounding boxes are (i.e. if they overlap). Should I try to test the colors on the overlapping regions (so that if
the pixels are not the transparent , “do a collision”)?– Ville Koskinen
viller.koskinen at iobox.com
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl–
±-----------------------------------+
- Bob Pendleton is seeking contract +
- and consulting work. Find out more +
- at http://www.jump.net/~bobp +
±-----------------------------------+
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
–
±-----------------------------------+
The technique you use depends on the game. For some games, bounding boxes
are enough. For wireframe games there are algorythms to check whether lines
cross (which can in some cases give you better-than-pixel collision
detection). In sprite-based games, a pixel-by pixel check is the ultimate
collision test, although it’s very expensive.
The best way to resolve collisions IMHO is to use three stages - first, only
check collisions among those sprite whose collision has a game effect (e.g.
in a platform game enemies don’t usually affect each other, so just test
whether they collide with the player, not with each other). Second, use a
cheap, rough test - like checking bounding boxes or assigning a series of
zones to the map area - sprites in different zones aren’t tested for
collisions. Finally, when the simple methods all indicate a collision, use a
pixel-perfect method.
I’ve attached a C++ class file and source for the CollisionMask class I use.
There are two important functions - one, the creator, makes a collision mask
from an SDL_Surface with an alpha channel. I create the sprites I use as
PNG’s with alpha data, and this function creates a pixel mask where 0
represents a pixel in the orignal image with alpha <= 128, 1 where alpha >
128. (Note - send SDL_Surfaces to this routine before you convert them to
the display format).
The other routine does stages 2 and 3 of my above list - given another mask
and the x,y coordinates of both mask’s top left corners, it checks the
bounding boxes of the collision masks and does a pixel-perfect test in the
event that it needs to.
Feel free to use, share, modify the code - if you make any great
improvements or find any serious bugs I’d like to hear about them. There is
one bug outstanding (too minor to make the top of my todo list, although I
will hunt it down soon), whereby the create routine fails for some images
which are opaque in the top left corner. But the other routine works 100%,
as far as I can tell, and the create routine works 95% of the time, and
always fails reliably. (i.e. no random fails), so it’s safe to use.
Keith Lawrence
@Keith_Lawrence> ----- Original Message -----
From: viller.koskinen@iobox.com (Ville Koskinen)
To:
Sent: Thursday, January 17, 2002 10:00 AM
Subject: [SDL] Sprite collisionsWhat is the best way to test if two sprites collide with each other? It’s
a bit too rough to just check where their
bounding boxes are (i.e. if they overlap). Should I try to test the colors
on the overlapping regions (so that if
the pixels are not the transparent , “do a collision”)?– Ville Koskinen
viller.koskinen at iobox.com
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl-------------- next part --------------
A non-text attachment was scrubbed…
Name: CollisionMask.h
Type: application/octet-stream
Size: 822 bytes
Desc: not available
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20020118/05e6b36a/attachment.obj
-------------- next part --------------
A non-text attachment was scrubbed…
Name: CollisionMask.cpp
Type: application/octet-stream
Size: 4546 bytes
Desc: not available
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20020118/05e6b36a/attachment-0001.obj
Wow, this’ll really help. But there’s one thing more: how can I easily test if a bullet hits a player if the bullets velocity is like 100 pix/frame (FPS = 30)? If I start using vector mathematics, I’ll have to use sqrt() and such. Will it slow down the game too much? Is there another ways for doing this?
Anyway, thanks for all the help!–
– Ville Koskinen
@Ville_Koskinen
Finland
Probably you don’t have to use sqrt() because u can use the quadratic values
themselves. If one squared distance is smaller than the other squared
distance then the same is true for their sqrt’s.On Monday 21 January 2002 03:02 am, you wrote:
Wow, this’ll really help. But there’s one thing more: how can I easily test
if a bullet hits a player if the bullets velocity is like 100 pix/frame
(FPS = 30)? If I start using vector mathematics, I’ll have to use sqrt()
and such. Will it slow down the game too much? Is there another ways for
doing this?Anyway, thanks for all the help!
Someone else will probably have a better solution, but you could cut the
path of the bullet up and find just a few points on the line with some
simple integer math.
If you have an idea of the smallest possible sprite and the max velocity
of your bullets you could pretty easily find out how many chunks you
need to cut your line into. After you get your points just spot check
them against any thing that falls within the rectangle of your bullets
motion.
Course, that doesn’t take into account the motion of your ‘target’.On Mon, 2002-01-21 at 03:02, Ville Koskinen wrote:
Wow, this’ll really help. But there’s one thing more: how can I easily test if a bullet hits a player if the bullets velocity is like 100 pix/frame (FPS = 30)? If I start using vector mathematics, I’ll have to use sqrt() and such. Will it slow down the game too much? Is there another ways for doing this?
Anyway, thanks for all the help!
–
– Ville Koskinen
viller.koskinen at iobox.com
Finland
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
–
End of Rant.
Jimmy
JimmysWorld.org
-------------- next part --------------
A non-text attachment was scrubbed…
Name: not available
Type: application/pgp-signature
Size: 232 bytes
Desc: This is a digitally signed message part
URL: http://lists.libsdl.org/pipermail/sdl-libsdl.org/attachments/20020121/27ea7369/attachment.pgp
Hello Ville,
Monday, January 21, 2002, 9:02:46 AM, you wrote:
VK> Wow, this’ll really help. But there’s one thing more: how can I easily test if a bullet hits a player if the bullets velocity is like 100 pix/frame (FPS = 30)? If I start using vector
VK> mathematics, I’ll have to use sqrt() and such. Will it slow down the game too much? Is there another ways for doing this?
VK> Anyway, thanks for all the help!
To speed up all mathematique functions like sqrt(), you’ll have to
pre-calculate as much values as possible.
Try to find which values and how much you will need to pre-calculate.–
Best regards,
SixK mailto:SixK at maniasys.com
Ville Koskinen <viller.koskinen at iobox.com> wrote:
Wow, this’ll really help. But there’s one thing more: how can I
easily test if a bullet hits a player if the bullets velocity is like
100 pix/frame (FPS = 30)? If I start using vector mathematics, I’ll
have to use sqrt() and such. Will it slow down the game too much? Is
there another ways for doing this?
Please, this is offtopic for the list — SDL does not have any sprite
facilities or collision detection.
The only and best advice I can give you is to learn how to use
profiling. If someone tells you things like “sqrt is slow” or “table
lookups are fast”, don’t believe them. Measure instead.
I heard of people developing a game. They did like this:
Once a bullet (or whatever) was fired, they calculated the expected tile
until the bullet was supposed to hit its target. Then they just left it,
doing its thing, until the calculated amount of time had elapsed, then they
checked if it hit its target. Don’t know if this is supposed to be common
gamprograming-knowledge, but i found it quite clever.
(and sory for sending this off-topic replay to the list…jada jada jada)
–Anders Folkesson
m?ndagen den 21 januari 2002 09:02 skrev du:> Wow, this’ll really help. But there’s one thing more: how can I easily test
if a bullet hits a player if the bullets velocity is like 100 pix/frame
(FPS = 30)? If I start using vector mathematics, I’ll have to use sqrt()
and such. Will it slow down the game too much? Is there another ways for
doing this?Anyway, thanks for all the help!
Ville Koskinen wrote:
Wow, this’ll really help. But there’s one thing more: how can I easily test if a bullet hits a player if the bullets velocity is like 100 pix/frame (FPS = 30)? If I start using vector mathematics, I’ll have to use sqrt() and such. Will it slow down the game too much? Is there another ways for doing this?
Use vector math. It is easy to do, it works all the time, It will work
no matter what the frame rate is, and it is much faster than most other
ways of doing it.
In the bad old days, 5 maybe 6 years ago, you actually had to worry
about the time needed to run a sqrt() or a floating point multiply. That
was a real concern on 386s and 486s which had very very slow floating
point arithmetic. If you are working on anything as new as a Pentium,
then you don’t need to worry about the speed of things like floating
mul/div or sqrt unless you are doing many millions of them per second. I
tested sqrt on a 550 MHz K6-2 just for fun and I see that the following
code which was compiled -g just to make sure it was a slow as possible
and the compiler didn’t get to clever on me:
int main(int argc, char **argv)
{
// testOpenGLBlit();
int time = SDL_GetTicks();
int i = 0;
int lim = 1000000;
double f1, f2 = 1.0;
for (i = 0; i < lim; i++)
{
f2 = sqrt(f1);
f1 = f2 + 1.0;
}
printf("%d\n", SDL_GetTicks() - time);
}
runs in about a 276 milliseconds.
As Donald Knuth said, “premature optimization is the root of all evil.”
(If you don’t know who he is you need to find out.) Which I interpret to
mean, do it the easiest way you can and don’t worry about it unless it
turns out to be too slow. If you are abolutely convinced that you need
to worry about how fast it is, write a bit of test code and try it. It
took me a lot less time to write that code snippet above than it did to
write this email.
Bob P.Hiya,
I don’t like this approach… If the player or the enemy moves towars the
player, all the wile intersecting the trajectory of the bullet, the bulet
will never hit the target.
A much simpler approach is to define aech object with an enclosing sphere
or cube and then just check on each step if the bullet is in the
cube/sphere. Sure it’s more calculation intensive but the literature on
bouding spheres/cubes is quite substantial and u should be able to find a
nice fast algorithm.
I personally HATE weird effects due to ‘opimazation’, I’d rather change
the specifications … 
Just my thoughts … :)---------------------
Johan Jordaan
BB&D
----- Original Message -----
From: sdl-admin@libsdl.org [mailto:sdl-admin at libsdl.org]On Behalf Of
Anders Folkesson
Sent: 21 January 2002 08:14
To: sdl at libsdl.org
Subject: Re: [SDL] Sprite collisionsI heard of people developing a game. They did like this:
Once a bullet (or whatever) was fired, they calculated the expected tile
until the bullet was supposed to hit its target. Then they just left it,
doing its thing, until the calculated amount of time had elapsed, then they
checked if it hit its target. Don’t know if this is supposed to be common
gamprograming-knowledge, but i found it quite clever.(and sory for sending this off-topic replay to the list…jada jada jada)
–Anders Folkesson
m?ndagen den 21 januari 2002 09:02 skrev du:
Wow, this’ll really help. But there’s one thing more: how can I easily
test
if a bullet hits a player if the bullets velocity is like 100 pix/frame
(FPS = 30)? If I start using vector mathematics, I’ll have to use sqrt()
and such. Will it slow down the game too much? Is there another ways for
doing this?Anyway, thanks for all the help!
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
Hiya,
I don’t like this approach… If the player or the enemy moves
towars the player, all the wile intersecting the trajectory of the
bullet, the bulet will never hit the target.
Not that I’ve used that approach yet, but I don’t think it would happen
if you add some rules for “when to reconsider the next test time”.
(It’s quite similar to control of audio code through timestamped events -
a subject that I know pretty well by now, to say the least, after all
that messing with the MAIA event system.)
A much simpler approach is to define aech object with an enclosing
sphere or cube and then just check on each step if the bullet is in the
cube/sphere. Sure it’s more calculation intensive but the literature on
bouding spheres/cubes is quite substantial and u should be able to find
a nice fast algorithm.
Why not just use bounding rects and a pixel accurate “hit mask” test?
Either way, as we’re not dealing with hardware sprites (which can be
moved by changing a few control registers), whatever calculations we do
for collision detection will take a relatively small fraction of the time
it takes to render one frame. Sure, it does matter more if we run the
control system at a constant 1000 Hz, but even then, a sane design should
run with acceptable speed, I think.
Still, optimizing things is fun! 
//David Olofson — Programmer, Reologica Instruments AB
.- M A I A -------------------------------------------------.
| Multimedia Application Integration Architecture |
| A Free/Open Source Plugin API for Professional Multimedia |
----------------------------> http://www.linuxdj.com/maia -' .- David Olofson -------------------------------------------. | Audio Hacker - Open Source Advocate - Singer - Songwriter |-------------------------------------> http://olofson.net -'On Monday 21 January 2002 19:45, Johan Jordaan wrote:
Hi!
You definitely got a pont here…bounding boxes/spheres are probably better
in general, but for non-moving targets, say cannon turrets, walls etc, you
could definitely apply the algorithm described below…
–Anders Folkesson
m?ndagen den 21 januari 2002 19:45 skrev du:> Hiya,
I don’t like this approach… If the player or the enemy moves towars
the player, all the wile intersecting the trajectory of the bullet, the
bulet will never hit the target.A much simpler approach is to define aech object with an enclosing sphere
or cube and then just check on each step if the bullet is in the
cube/sphere. Sure it’s more calculation intensive but the literature on
bouding spheres/cubes is quite substantial and u should be able to find a
nice fast algorithm.I personally HATE weird effects due to ‘opimazation’, I’d rather change
the specifications …Just my thoughts …
Johan Jordaan
BB&D-----Original Message-----
From: sdl-admin at libsdl.org [mailto:sdl-admin at libsdl.org]On Behalf Of
Anders Folkesson
Sent: 21 January 2002 08:14
To: sdl at libsdl.org
Subject: Re: [SDL] Sprite collisionsI heard of people developing a game. They did like this:
Once a bullet (or whatever) was fired, they calculated the expected tile
until the bullet was supposed to hit its target. Then they just left it,
doing its thing, until the calculated amount of time had elapsed, then they
checked if it hit its target. Don’t know if this is supposed to be common
gamprograming-knowledge, but i found it quite clever.(and sory for sending this off-topic replay to the list…jada jada jada)
–Anders Folkesson
m?ndagen den 21 januari 2002 09:02 skrev du:
Wow, this’ll really help. But there’s one thing more: how can I easily
test
if a bullet hits a player if the bullets velocity is like 100 pix/frame
(FPS = 30)? If I start using vector mathematics, I’ll have to use sqrt()
and such. Will it slow down the game too much? Is there another ways for
doing this?Anyway, thanks for all the help!
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl