gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

DS development > Pixel-Perfect collisions?

#58232 - Extreme Coder - Fri Oct 21, 2005 8:31 pm

I've been looking for a way to do pixel-perfect collisions on the ds(yeah I know, it wont be different from the pc), and this is what I've been able to get to:
Code:

short int Collide(object1,object2) {

    int left1, left2, over_left;
    int right1, right2, over_right;
    int top1, top2, over_top;
    int bottom1, bottom2, over_bottom;
    int over_width, over_height;
    int i, j;
    unsigned char *pixel1, *pixel2;

    left1 = object1->x;
    left2 = object2->x;
    right1 = object1->x + object1->width;
    right2 = object2->x + object2->width;
    top1 = object1->y;
    top2 = object2->y;
    bottom1 = object1->y + object1->height;
    bottom2 = object2->y + object2->height;


    // Trivial rejections:
    if (bottom1 < top2) return(0);
    if (top1 > bottom2) return(0);
 
    if (right1 < left2) return(0);
    if (left1 > right2) return(0);


    // Ok, compute the rectangle of overlap:
    if (bottom1 > bottom2) over_bottom = bottom2;
    else over_bottom = bottom1;
 
    if (top1 < top2) over_top = top2;
    else over_top = top1;

    if (right1 > right2) over_right = right2;
    else over_right = right1;

    if (left1 < left2) over_left = left2;
    else over_left = left1;


    // Now compute starting offsets into both objects' bitmaps:
    i = ((over_top - object1\1->y) * object1->width) + over_left;
    pixel1 = object1->frames[object1->curr_frame] + i;

    j = ((over_top - object2->y) * object2->width) + over_left;
    pixel2 = object2->frames[object2->curr_frame] + j;

 
    // Now start scanning the whole rectangle of overlap,
    // checking the corresponding pixel of each object's
    // bitmap to see if they're both non-zero:

    for (i=0; i < over_height; I++) {
        for (j=0; j < over_width; j++) {
            if (*pixel1 != 0xFFFF) && (*pixel2 != 0xFFFF) return(1);
            pixel1++;
            pixel2++;
        }
        pixel1 += (object1->width - over_width);
        pixel2 += (object2->width - over_width);
    }

    return(0);

};



So basically this is a for loop checking on the gfx data of both objects, to see if any other color other than transparent is colliding.

But, this is VERY cpu extensive, and even once or twice in the game loop, it could slow down the game heavily.
Is there any other possible ways to detect collision detection? If not, how can this one be sped up?

Thanks in advance

#58235 - Mighty Max - Fri Oct 21, 2005 8:36 pm

You could make 1bit map of the objects (transparent or not) and then logical and their values (shifted to match their relations to each other)

As soon as you get a value other then zero, you have a collision. This way you can check several pixels in one step by a simple &.


:edit:
If you don't do it by pixel, i suggest defining surrounding lines, which you can then check to cross each other. Gauss made some nice n^3 complex algorithm for this :p

This howere does not detect objects that are complete covered by the second object.
_________________
GBAMP Multiboot

#58238 - tepples - Fri Oct 21, 2005 8:56 pm

Go with multiple hitboxes on each sprite cel. These can be rectangles or circles, as those are easy to test against each other. You might want to make one for the head, one for the torso, one for the legs, and one for the attacking arm or leg; that's what 2D fighters seem to do.

What specifically did you need pixel-perfect collisions for? In many cases, pixel-perfect collisions are a bad idea for game design because things get caught on walls too easily.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#58244 - alex - Fri Oct 21, 2005 9:15 pm

More often than not, and especially in a portable platform, a simple bounding sphere or bounding box will do the job for collision detection.

#58302 - Extreme Coder - Sat Oct 22, 2005 1:17 pm

tepples & alex:
Well, I need pixel-perfect collisions for a game that really needs them, and wont work without it coughsoniccough

Mighty Max:
Could you clarify a bit please?

#58305 - Mighty Max - Sat Oct 22, 2005 1:33 pm

yeah sure, (i think you mean the first one)

Lets say you got a 1bit map of the transparency. 0 for transparent, 1 for solid.

For each line you have to check the collision. Within one line you can simply

object1->line[#] & (object1->line[# + VerticalOffset] << HorizontalOffset)

If it results in anything other then 0, you have at least one pixel collision.

The ARM however does only 32Bit bool operations, so you have to scale it to your needs (objectWidth). As they are bitwise, it is a simple linear thing.

As an example:

Object1 line is 011000000100000011111010001
Object2 line is 000000000001111111100000000

Object1 is 3 pixels left to object 2, so you do

011000000100000011111010001 &
(000000000001111111100000000<< 3)

= 011000000100000011111010001
& 000000001111111100000000000

= 000000000100000000000000000

!=0 so there is a collision

In this example, we have checked 27 pixels in one iteration.
_________________
GBAMP Multiboot

#58321 - tepples - Sat Oct 22, 2005 5:28 pm

Extreme Coder wrote:
tepples & alex:
Well, I need pixel-perfect collisions for a game that really needs them, and wont work without it coughsoniccough

What kind of "sonic" are you talking about? Sonic the Hedgehog 2 for Genesis uses horizontal extents: each 16x16 pixel metatile has 16 rows, with a left side and a right side. But it could also have been easily done by treating each tile as a line segment and treating the Blue One as a circle.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#58547 - darkfader - Mon Oct 24, 2005 3:09 pm

What about sub-pixel-perfect collisions? The display is just an aliased view of your game. The accuracy depends on the amount of CPU time you want to spend. You might want trade-offs on the DS.
I once made a simple ballgame proto on GBC and had to make the ball bounce off square edges. This was fairly simple of course since the shapes were fixed.

#58564 - Extreme Coder - Mon Oct 24, 2005 5:01 pm

Mighty Max:
Ok thanks, I will try that:D

Tepples:
I am guessing the Blue one is Sonic,right?;)
The sonic one I'm planning would be a bit retro (genesis) style games (but 360 degree rotation, they didn't have enough hardware to do that in the Genesis in those days:-)) because the sonic games on them, IMO, were the best ones.

DarkFader:
I think we need to get this one done first, then we may think about sub-pixel perfect collisions. Anyway, I don't think that many games here actually use sub-pixels(but I could be wrong).

#58606 - tepples - Mon Oct 24, 2005 9:32 pm

Yes, when you press Down+C, the blue circle is Sonic.

In general, the experience from writing geometric collision code will be more useful than the experience from writing pixel-based collision code, especially when you move to a 3D environment.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#58618 - Extreme Coder - Mon Oct 24, 2005 10:22 pm

Geometric collisions? You mean circles and all that stuff? I don't even know how to do that. :-)
But, for the purpose of my game, circle collision routines, if faster than pixel-perfect ones, would be useful.

#58619 - Mighty Max - Mon Oct 24, 2005 10:30 pm

They are. a lot.

If you want to check for circle collisions, just test if

((opject1.centerx-object2.centerx)^2) + ((object1.centery-object2.centery)^2) is less or equal to (radius1+radius2)^2
_________________
GBAMP Multiboot

#58624 - tepples - Mon Oct 24, 2005 11:03 pm

Mighty Max's explanation of circle to circle overlap testing is correct, but make sure to use integer or fixed-point math rather than the pow() function.

Circle to line segment overlap testing goes roughly like the following steps. None of this requires any division or square roots if implemented correctly (all endpoints and normal vectors stored as fixed-point numbers).
  1. Trivial rejection: First check if the circle is anywhere near the line segment. In a Sonic 2 style engine, you'll typically have a line segment for each 16x16 pixel ground tile; only those segments that correspond to tiles that the player's bounding box is overlapping need to be tested.
  2. Normal line: Construct perpendicular lines to the segment through each endpoint. This divides the plane into three regions: points behind endpoint A's line, points behind endpoint B's line, and points between the lines.
  3. If the center of the circle is "behind" an endpoint, check that circle against that endpoint and stop.
  4. If the center of the circle is "between" the endpoints, calculate the distance from the line to the circle along the line segment's normal vector, which involves a dot product.

A diagram would help you understand this, but I'm busy helping other people right now.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#58746 - Extreme Coder - Tue Oct 25, 2005 7:13 pm

But then the circle won't collide with anything but a straight line,right?

#58748 - tepples - Tue Oct 25, 2005 7:43 pm

True, but if you build your map out of tiles and you associate a line segment with each tile...
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#58751 - DekuTree64 - Tue Oct 25, 2005 7:58 pm

Or use a circle-box check for the usually more common square tiles. Here's an easy one, which will also deal with a circle contained entirely by the box:

Code:
#define CLAMP(val, min, max) \
    ( ((val) < (min) ? (min)) : \
        ((val) > (max) ? (max) : (val)) )

#define SQUARED(val) ((val) * (val))
// mod note: calling it SQR will invite confusion between squared and square root

BOOL collideCircleBox(CIRCLE *circle, BOX *box)
{
    VECTOR2 closestPointOnBox;

    closestPointOnBox.x = CLAMP(circle->x, box->left, box->right);
    closestPointOnBox.y = CLAMP(circle->y, box->top, box->bottom);

    if (SQUARED(closestPointOnBox.x) + SQUARED(closestPointOnBox.y) <
        SQUARED(circle->radius))
    {
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku

#58806 - cybereality - Wed Oct 26, 2005 5:43 am

Pixel-perfect collision isn't necessary for games at all. The only place I can think of that they would need this is for industrial prototyping (like crashing a car in a 3d computer simulation). For games, all you have to do is make the world believable, not physically accurate. Even games that pride themselves on the physics like HalfLife2 don't use pixel perfect collisions. They use simple hit boxes to register collisions (i.e. a box for the head, chest, arm, etc.).

Most 2D games will suffice with simply a hit box around the character. An easy way to do this is the treat the player as a point along the floor with a range the extends above and behind that point. You would need to define a playerX and playerY position value and also a playerHeight and playerWidth (uses as bounds for the hit box). Do a simple check to see if the player is anywhere close to the other object (enemy, wall, powerup, etc.) and if so check to see if their hit boxes overlap. Then do whatever it is happens (player loses life, stop movement, trigger event, etc.). The same idea can be applied to circular collision instead you use the radius to check if the circles collide.
_________________
// cybereality

#58815 - Extreme Coder - Wed Oct 26, 2005 11:36 am

cybereality:
Well, you're almost correct. Most games do not need perfect-pixel collisions. But, there are a FEW cases in which they are needed. And sonic is one of those cases.

Tepples:
Tepples, I will try looking into that , even though I would need lots of lines for one tile(slopes & stuff).But won't that be CPU extensive?
You seem to know everything about Sonic the Hedgehog 2:D

DekuTree64:
I will try that today.

#58822 - tepples - Wed Oct 26, 2005 2:57 pm

Extreme Coder wrote:
Tepples, I will try looking into that , even though I would need lots of lines for one tile(slopes & stuff).But won't that be CPU extensive?

Do you need more than one slope for one 16x16 pixel tile? Or by "tile" do you mean the 128x128 pixel metatiles used in the compressed map?

Quote:
You seem to know everything about Sonic the Hedgehog 2:D

I learned everything I know from a Sonic hacking site that may have since disappeared from the internets.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#58842 - Extreme Coder - Wed Oct 26, 2005 6:04 pm

By tile, I mean a 16x16 pixel tile.In some sonic games,slopes are not made of straight lines, like this: [Images not permitted - Click here to view it]
Seems you are a sonic fan.[/img]

#58848 - M3d10n - Wed Oct 26, 2005 6:51 pm

You don't need per-pixel collision checks for that. That is a slope, but it's just not a line.

You can represent different tiles like that as functions, where the tile height (Y) varies along the X coordinate. A straight 45? slope is just a plain line function. Of course, the function results can be stored in lookup tables for faster access.

That way you can cast rays against the tiles, and by doing so, being able to make a moving object stop properly at a given tile no matter how fast it was traveling. It's also possible to figure out the normal at a given tile point, and bounce/slide the object along it.

Also, keep in mind that the Sonic games didn't quite have actual physics. Everything was mostly done by finite state machines, with state changes happenning when Sonic touches certain tiles.

#58894 - tepples - Thu Oct 27, 2005 12:27 am

Specifically, I was referring to a piecewise linear approximation of the curved surface you use as an example:

image: piecewise linear
Part 1 is the image you gave me, with a curved platform. Part 2 is the image with 16x16 tile boundaries marked. Part 3 is the image with tile boundaries, plus a linear approximation of the curve in each tile. Part 4 is just the tiles and line segments, as the collision engine would see them.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#65881 - Ultima2876 - Fri Jan 06, 2006 2:39 pm

Sonic 2 uses bounding boxes for object-object collisions. The floors don't use horizontal height-maps - they use vertical height maps (I wrote an editor for them a while back).

Sonic is treated as a geometric circle throughout the game, and to work out curves and resistance for his motion two points are stored for each tile which form a line - a vector.

If you're interested, they use perfect circles (and sinewaves) for the paths in Sonic 3K's Death Egg. They yellow "tracker" paths =P

And no physics? No, Sonic has a physics engine - they use "state machines" for the movement routines sonic should be executing (jump after spindash, jump, roll, normal), but they don't use state machines to hardcode every tile.

If you want an almost complete description of sonic's collision engine, see if you can find Dr Ivo's document on it. Last time I saw it was back at Area 51 last year sometime. Or of course you can dig around in a disassembly, but some stuff is pretty difficult to figure out (especially in Sonic 3/K).

And tepples; was that site Nemesis' one?

#65930 - Dwedit - Fri Jan 06, 2006 9:16 pm

Actually, pixel perfect collision is necessary if you are cloning an atari 2600 game which used that hardware feature.
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."

#65982 - tepples - Sat Jan 07, 2006 8:26 am

But then the Atari 2600 just had two sprites, two rectangular missiles, a background, and a background missile. Games built around those limitations are generally simple enough that you can do exhaustive pixel-perfect collision on all 15 pairs without slowdown.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.