How would I do pixel perfect collision detection?
Example: I am making a Pac-Man clone as an exercise. The level is a
bitmap file which is loaded into a surface. I want to see if the
rectangle containing the player image has intersected the level by
checking if the rectangle touched any of the “on” pixels of the level.
Simpler version of the question: How do I check to see if a certain
pixel has a non-black color?
Example: I am making a Pac-Man clone as an exercise. The level is a bitmap
file which is loaded into a surface. I want to see if the rectangle
containing the player image has intersected the level by checking if
the rectangle touched any of the “on” pixels of the level.
Simpler version of the question: How do I check to see if a certain pixel
has a non-black color?
Use the GetPixel() function described in the SDL docs, check against a
SDL_Color built for the surface you’re checking. Although black is
almost guaranteed to be 0 everywhere.
However you shouldn’t need to do this - Pacman is almost certainly tile-
based, and as a first exercise you shouldn’t make it as complicated as
having pixel collisions…
--GabrielPixel perfect collision is (almost) never required in my experience.
Use bounding boxes (just rectangular area around your ‘sprites’) or
simple polygons if you need them. If you really need pixel perfect
I’d favour a separate array of bits determining collisions, since
pixel colour of the image may not represent exactly what you want to
collide.On 6/27/05, Gabriel wrote:
Example: I am making a Pac-Man clone as an exercise. The level is a bitmap
file which is loaded into a surface. I want to see if the rectangle
containing the player image has intersected the level by checking if
the rectangle touched any of the “on” pixels of the level.
Simpler version of the question: How do I check to see if a certain pixel
has a non-black color?Use the GetPixel() function described in the SDL docs, check against a
SDL_Color built for the surface you’re checking. Although black is
almost guaranteed to be 0 everywhere.However you shouldn’t need to do this - Pacman is almost certainly tile-
based, and as a first exercise you shouldn’t make it as complicated as
having pixel collisions…--Gabriel
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
–
Rob Sadedin
No Substance Software (www.nosubstancesoftware.com)
I have the same problem with one of my projects. I’m using a circular
player, and need a way to determine whether it’s blocked by other
objects. Pixel collision seems too fine, though, ideally I’d like an
approximation of a circle shape (hexagon) that I can comapre against
each object intersecting.
JoshOn 6/27/05, Gabriel wrote:
Example: I am making a Pac-Man clone as an exercise. The level is a bitmap
file which is loaded into a surface. I want to see if the rectangle
containing the player image has intersected the level by checking if
the rectangle touched any of the “on” pixels of the level.
Simpler version of the question: How do I check to see if a certain pixel
has a non-black color?Use the GetPixel() function described in the SDL docs, check against a
SDL_Color built for the surface you’re checking. Although black is
almost guaranteed to be 0 everywhere.However you shouldn’t need to do this - Pacman is almost certainly tile-
based, and as a first exercise you shouldn’t make it as complicated as
having pixel collisions…--Gabriel
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
Anthony Ardito wrote:
How would I do pixel perfect collision detection?
Example: I am making a Pac-Man clone as an exercise. The level is a
bitmap file which is loaded into a surface. I want to see if the
rectangle containing the player image has intersected the level by
checking if the rectangle touched any of the “on” pixels of the level.
I'd agree with others here that pixel-perfect collision detection is
not needed for a game this simple. But with your current approach, I can
see how it would be necessary. Might I suggest you break your level up
into more components. For instance, if the graphics are simple enough,
you might consider first drawing the background, and actually make the
solid parts of the level just solid colored surfaces on top of that.
This way it would be very simple to write a level editor (or even just
hand-edit level definition files) without having to worry about properly
scaling images so that the they don’t get distorted in game. You could
also go with a tile-based approach, as suggested earlier. My advice here
would be to establish some common unit (maybe 4x4 pixels) and make a
generic image of this size. Then to build your level, you’d just repeat
this texture on the level as needed (you’d have a bunch of surfaces
lined up next to each other). For performance, you might want to make up
several different tiles like this (so for long walls you’d only have
like one or two large tiles, instead of a dozen or so small ones).
Collision detection in a tile-based system like this would most likely
be based on rects. You’d want to keep your tile surfaces tied to rects,
for collision (something like Pygame’s sprite module). Ergo, the surface
would get rendered at the rect’s coords. Also, this will make it much
easier if you decide to go to OpenGL at some point down the road. 
-Matt BaileyLike already mentioned, for a game like Pac-Man, you dont really need
collision detection on pixel level. If you really want to do this I
would use a collision map to make it really simple. This is black and
white pixelmap where black is the area you can move, and white means you
have a collision.
approach when making a Pac-Man game. I have already tried this, and it
just introduced too many problems for such a simple game. If you want
your Pacman to move freely in any direction (not just
up,down,left,right), be aware that you will get challenge in other
dimensions. Just imagine trying to take a left turn around a sharp
corner or just trying to move in a tight spot. You will get stuck all
the time, and that will eventually introduce a new extremesport
involving talking turns at the right pixel.
If you want to make a classic Pac-Man clone, just restrict the movement
to up, down, reft and right. Devide the screen into eg. 16 x 16 squares
and make a map editor or just use an ascii file to define what each of
the squares should be.
To make the movement much easier, imagine a Pacman as a 14x14 image in
the middle of one of the 16x16 squares. Moving to another square in any
of the four directions would mean moving 16 pixels. While our Pacman
move between two squares the only thing that should interrupt the
movement is if you want to go the oposite direction. For each frame,
check the key events and store the last direction input from the user.
Every time you reach a square, check what direction the used wanted to
go and check in your levelmap if this is a valid move. If not, just
continue moving to the next square. If you hit a wall, just stop there
intil the used give a valid direction.
The collision between enemies can be the distace between them. eg. 1/2 a
square = 8 pixels.
Good luck with the game
Anthony Ardito wrote:From my personal experience I would strongly advise you to avoid this
How would I do pixel perfect collision detection?
Example: I am making a Pac-Man clone as an exercise. The level is a
bitmap file which is loaded into a surface. I want to see if the
rectangle containing the player image has intersected the level by
checking if the rectangle touched any of the “on” pixels of the level.Simpler version of the question: How do I check to see if a certain
pixel has a non-black color?
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
Just use a distance algorithm. The points on the outside of a circle are
pretty easy to calculate.
-bill!On Mon, Jun 27, 2005 at 11:47:34AM +1000, Josh Matthews wrote:
I have the same problem with one of my projects. I’m using a circular
player, and need a way to determine whether it’s blocked by other
objects. Pixel collision seems too fine, though, ideally I’d like an
approximation of a circle shape (hexagon) that I can comapre against
each object intersecting.
Ok, I am with another question on the same line.
I wanted a ball to move in a maze, controled my mouse scrolling speed.
I let the ball collide and then find how the ball should react to collison.
( It has to bounce back once it hits a wall or other balls)
When the ball moves so fast, (on a system with lower frame rates)
the ball moves past the walls, before I get a chance to check collision.
What is the standard practice in these situation?
Do i need a Physics engine? Is there any simple 2d physics engine?
All available Physics engines seems to be 3d.
Thanks.
Tony.> ----- Original Message -----
From: sdl-bounces+admin=windows-games.com@libsdl.org
[mailto:sdl-bounces+admin=windows-games.com at libsdl.org]On Behalf Of
Einar Forselv
Sent: Monday, June 27, 2005 10:09 AM
To: Anthony Ardito; A list for developers using the SDL library.
(includes SDL-announce)
Subject: Re: [SDL] Pixel perfect collision detectionLike already mentioned, for a game like Pac-Man, you dont really need
collision detection on pixel level. If you really want to do this I
would use a collision map to make it really simple. This is black and
white pixelmap where black is the area you can move, and white means you
have a collision.From my personal experience I would strongly advise you to avoid this
approach when making a Pac-Man game. I have already tried this, and it
just introduced too many problems for such a simple game. If you want
your Pacman to move freely in any direction (not just
up,down,left,right), be aware that you will get challenge in other
dimensions. Just imagine trying to take a left turn around a sharp
corner or just trying to move in a tight spot. You will get stuck all
the time, and that will eventually introduce a new extremesport
involving talking turns at the right pixel.If you want to make a classic Pac-Man clone, just restrict the movement
to up, down, reft and right. Devide the screen into eg. 16 x 16 squares
and make a map editor or just use an ascii file to define what each of
the squares should be.To make the movement much easier, imagine a Pacman as a 14x14 image in
the middle of one of the 16x16 squares. Moving to another square in any
of the four directions would mean moving 16 pixels. While our Pacman
move between two squares the only thing that should interrupt the
movement is if you want to go the oposite direction. For each frame,
check the key events and store the last direction input from the user.
Every time you reach a square, check what direction the used wanted to
go and check in your levelmap if this is a valid move. If not, just
continue moving to the next square. If you hit a wall, just stop there
intil the used give a valid direction.The collision between enemies can be the distace between them. eg. 1/2 a
square = 8 pixels.Good luck with the game
Anthony Ardito wrote:
How would I do pixel perfect collision detection?
Example: I am making a Pac-Man clone as an exercise. The level is a
bitmap file which is loaded into a surface. I want to see if the
rectangle containing the player image has intersected the level by
checking if the rectangle touched any of the “on” pixels of the level.Simpler version of the question: How do I check to see if a certain
pixel has a non-black color?
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
Check for collision at every (reasonable, at least) point between where it
is in frame N and where it is in frame N + 1.
In other words, if you can only draw it at 10fps, but in doing so that
causes the ball to go through the wall, move the ball incrementally a
number of times BETWEEN frames.
Remember, if you’re doing something insanely complicated (like I’m guessing
Liquid War does, since it’s so free-form), you can do bounding box checks
as an optimization. Then, if there’s a CHANCE that there might be
a pixel collision, do the more CPU-intensive pixel-perfect test.
Otherwise… nothin’ to see here. Keep moving.
-bill!On Mon, Jun 27, 2005 at 11:21:43AM +0530, Windows-Games wrote:
Ok, I am with another question on the same line.
I wanted a ball to move in a maze, controled my mouse scrolling speed.
I let the ball collide and then find how the ball should react to collison.
( It has to bounce back once it hits a wall or other balls)When the ball moves so fast, (on a system with lower frame rates)
the ball moves past the walls, before I get a chance to check collision.What is the standard practice in these situation?
move the ball incrementally a
number of times BETWEEN frames.
that is the trick I was looking far. thanks.
I am not using pixel collison. Radius and rectangle maths only. not very
complicated.> ----- Original Message -----
From: sdl-bounces+admin=windows-games.com@libsdl.org
[mailto:sdl-bounces+admin=windows-games.com at libsdl.org]On Behalf Of Bill
Kendrick
Sent: Monday, June 27, 2005 12:21 PM
To: A list for developers using the SDL library. (includes SDL-announce)
Subject: Re: [SDL] Pixel perfect collision detectionOn Mon, Jun 27, 2005 at 11:21:43AM +0530, Windows-Games wrote:
Ok, I am with another question on the same line.
I wanted a ball to move in a maze, controled my mouse scrolling speed.
I let the ball collide and then find how the ball should react to
collison.
( It has to bounce back once it hits a wall or other balls)When the ball moves so fast, (on a system with lower frame rates)
the ball moves past the walls, before I get a chance to check collision.What is the standard practice in these situation?
Check for collision at every (reasonable, at least) point between where it
is in frame N and where it is in frame N + 1.In other words, if you can only draw it at 10fps, but in doing so that
causes the ball to go through the wall, move the ball incrementally a
number of times BETWEEN frames.Remember, if you’re doing something insanely complicated (like I’m guessing
Liquid War does, since it’s so free-form), you can do bounding box checks
as an optimization. Then, if there’s a CHANCE that there might be
a pixel collision, do the more CPU-intensive pixel-perfect test.
Otherwise… nothin’ to see here. Keep moving.-bill!
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
Just remember :
Lets say the ball in posision A use 100ms to reach C, and 100ms from C
to B.
If you draw a frame at A and this takes 200ms, your ball should be at B
in the next frame. I guess this is common sense, but I have seen so many
people insisting that it should be in C because they want the used to
"see the bounce".
A O B O
\ /
\ /
\ /
--------x---------- Wall
C
Windows-Games wrote:>>>move the ball incrementally a
number of times BETWEEN frames.
that is the trick I was looking far. thanks.
I am not using pixel collison. Radius and rectangle maths only. not very
complicated.
How would I do pixel perfect collision detection?
As already said numerous times inside this thread - in most cases -
don’t.
But - however - I did some thoughts on that, too, also I never
implemented the following Idea:
Basically you can use 2color-masks (1 and 0) for your objects.
The first thing you do is checking wether those two mask overlap
(bounding box intersection).
If they do, blit one inside another using AND (I guess you will have
to write that yourself - don’t know if SDL provides this). Now check
your newly created Mask if any Pixel is !=0. If there is -> collision.
A z-Pyramid like aproach might speed this up - you can create mipmap
like “level of detail masks”, meaning you put together blocks of 4
pixels in each step until you end up with a required number of pixels
width/height in your image (e.g. 8x8 or sth. similar that’s fast
enough with brute force). Now you test the smallest map first as
described above.
On collision go one level deeper but only at the area where the
intersection took place(!). If you still have collision at the lowest
mask-level -> collision. otherwise - stop where you are.
That could speed up things a bit (common hierarchical grid method),
although I’m not totally sure about this - depends on the number of
operations you do.
However - this method has some downsizes, like speed and the fact,
that you can’t so easily calculate an accurate penetration depth, but
If you have to use it, the above approach might(!) be faster than
brute force testing.
The best way doing collision detection (IMHO) is using polygons /
circles and some kind of hierarchy, like uniform/hierarchical grid or
kd-Trees. There are numerous papers on the web about this. The most
are 3D, but can be easily derived for 2D-cases (most use 2D examples).
Arne
If you just want to check if a “circular” PacMan collides with a
"circular" foe, you might wanna use the distance formula:
distance = sqrt( (px-fx)(px-fx) + (py-fy)(py-fy) );
… where (px,py) is the screen location of PacMans center pixel and
(fx,fy) is the screen location of the foe’s center pixel.
For example, if pacman is 15 pixels wide and the foe 15 too, then they
collide if their centers are less than or equal 15 pixels away from
each other:
if(distance <= 15) {
// collision…
}
good luck,
/OlofOn 6/28/05, Arne Claus wrote:
How would I do pixel perfect collision detection?
As already said numerous times inside this thread - in most cases - don’t.
But - however - I did some thoughts on that, too, also I never implemented
the following Idea:Basically you can use 2color-masks (1 and 0) for your objects.
The first thing you do is checking wether those two mask overlap (bounding
box intersection).
If they do, blit one inside another using AND (I guess you will have to
write that yourself - don’t know if SDL provides this). Now check your newly
created Mask if any Pixel is !=0. If there is -> collision.A z-Pyramid like aproach might speed this up - you can create mipmap like
"level of detail masks", meaning you put together blocks of 4 pixels in each
step until you end up with a required number of pixels width/height in your
image (e.g. 8x8 or sth. similar that’s fast enough with brute force). Now
you test the smallest map first as described above.
On collision go one level deeper but only at the area where the intersection
took place(!). If you still have collision at the lowest mask-level ->
collision. otherwise - stop where you are.
That could speed up things a bit (common hierarchical grid method), although
I’m not totally sure about this - depends on the number of operations you
do.However - this method has some downsizes, like speed and the fact, that you
can’t so easily calculate an accurate penetration depth, but If you have to
use it, the above approach might(!) be faster than brute force testing.The best way doing collision detection (IMHO) is using polygons / circles
and some kind of hierarchy, like uniform/hierarchical grid or kd-Trees.
There are numerous papers on the web about this. The most are 3D, but can be
easily derived for 2D-cases (most use 2D examples).Arne
SDL mailing list
SDL at libsdl.org
http://www.libsdl.org/mailman/listinfo/sdl
/Anders
Olof Bjarnason wrote:> If you just want to check if a “circular” PacMan collides with a
“circular” foe, you might wanna use the distance formula:
distance = sqrt( (px-fx)(px-fx) + (py-fy)(py-fy) );
… where (px,py) is the screen location of PacMans center pixel and
(fx,fy) is the screen location of the foe’s center pixel.For example, if pacman is 15 pixels wide and the foe 15 too, then they
collide if their centers are less than or equal 15 pixels away from
each other:if(distance <= 15) {
// collision…
}good luck,
/Olof
On 6/28/05, Arne Claus wrote:
How would I do pixel perfect collision detection?
As already said numerous times inside this thread - in most cases - don’t.
But - however - I did some thoughts on that, too, also I never implemented
the following Idea:Basically you can use 2color-masks (1 and 0) for your objects.
The first thing you do is checking wether those two mask overlap (bounding
box intersection).
If they do, blit one inside another using AND (I guess you will have to
write that yourself - don’t know if SDL provides this). Now check your newly
created Mask if any Pixel is !=0. If there is -> collision.A z-Pyramid like aproach might speed this up - you can create mipmap like
"level of detail masks", meaning you put together blocks of 4 pixels in each
step until you end up with a required number of pixels width/height in your
image (e.g. 8x8 or sth. similar that’s fast enough with brute force). Now
you test the smallest map first as described above.
On collision go one level deeper but only at the area where the intersection
took place(!). If you still have collision at the lowest mask-level ->
collision. otherwise - stop where you are.
That could speed up things a bit (common hierarchical grid method), although
I’m not totally sure about this - depends on the number of operations you
do.However - this method has some downsizes, like speed and the fact, that you
can’t so easily calculate an accurate penetration depth, but If you have to
use it, the above approach might(!) be faster than brute force testing.The best way doing collision detection (IMHO) is using polygons / circles
and some kind of hierarchy, like uniform/hierarchical grid or kd-Trees.
There are numerous papers on the web about this. The most are 3D, but can be
easily derived for 2D-cases (most use 2D examples).Arne
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