Best collision detection

ID:152502
 
Jul 31 2006, 8:15 am
Whats the best (or atleast, decent) way to detect collision in pixel based movement systems?

My way is extremely off and sometimes doesn't even work at all.
Jul 31 2006, 9:32 am
This isn't the best collision detection method, but it'd probably suit your game. http://en.wikipedia.org/wiki/Bounding_box
Jul 31 2006, 5:57 pm
Check out my unfinished library:
hub:iainperegrine.ip_px

In that I use the bounding box technique, as linked to by Crashed. Basically, I perform two tests:
Is the displacement in the x direction between the centers of the two objects less than half their combined widths?
Is the displacement in the y direction between the centers of the two objects less than half their combined heights?
If both of these tests return true, then a collision between their bounding boxes has occured. The entire thing looks something like this:
if(\
    (abs(M1.x - M2.x) < (M1.width + M2.width)/2)\
    && \
    (abs(M1.y - M2.y) < (M1.height + M2.height))\
    )
    collide()


The unrotatable bounding box is severely limited, and may not work very well in your space game. In your case, I would suggest the more rotation friendly "bounding circle" technique. What you'd do here is give each object a radius, and then test if the centers of the two objects are closer than their combined radius. Though this is only one test, it takes more cpu time because you have to take square roots to determine the displacement. It looks something like this:
var/a = abs(M1.x - M2.x)
var/b = abs(M1.y - M2.y)
var/c = sqrt(a*a + b*b)
if(c < M1.radius + M2.radius)
    collide()
Jul 31 2006, 6:10 pm
In response to IainPeregrine
IainPeregrine wrote:
Check out my unfinished library:
hub:iainperegrine.ip_px

In that I use the bounding box technique, as linked to by Crashed. Basically, I perform two tests:
Is the displacement in the x direction between the centers of the two objects less than half their combined widths?
Is the displacement in the y direction between the centers of the two objects less than half their combined heights?
If both of these tests return true, then a collision between their bounding boxes has occured. The entire thing looks something like this:
if(\
>     (abs(M1.x - M2.x) < (M1.width + M2.width)/2)\
>     && \
>     (abs(M1.y - M2.y) < (M1.height + M2.height))\
>     )
>     collide()

The unrotatable bounding box is severely limited, and may not work very well in your space game. In your case, I would suggest the more rotation friendly "bounding circle" technique. What you'd do here is give each object a radius, and then test if the centers of the two objects are closer than their combined radius. Though this is only one test, it takes more cpu time because you have to take square roots to determine the displacement. It looks something like this:
var/a = abs(M1.x - M2.x)
> var/b = abs(M1.y - M2.y)
> var/c = sqrt(a*a + b*b)
> if(c < M1.radius + M2.radius)
>     collide()


It's not for my space game. Its for the 360 degree Snake game I'm making. ;p

Does that change the way the pixel collision needs to be handled? I can't seem to make it work. :( Hmmm.
Jul 31 2006, 6:22 pm
In response to Koil
Blast!
            var/turf/t = src.loc
            if(t && t.density)
                if((abs(x - t.x) < (width + t.width)/2) && (abs(y - t.y) < (height + t.height)))
                    stop = 1
                    return

actually works pretty good... for the north and east walls.

It doesn't work quite so good for the west and south walls. I found that the collision occurs directly after the snake exits the icon, rather than before.
Jul 31 2006, 6:47 pm
In response to Koil
There are two things to keep in mind:
1. x and y are the coordinates of the center, not the lower left hand corner of the object.
2. You may need to use <= instead of <, depending on how your game works. The important part is to be consistant throughout your project. This consistancy is hard to define... it basically depends on how you think about collision detection. In one model, the bounding boxes much overlap; in the other, they only have to touch.

Problems with either of those can cause the effect you're describing (where certain edges work fine, but others don't). I do hope you're defining your own x and y variables instead of trying to use the atomic versions somehow.
Jul 31 2006, 6:50 pm
In response to IainPeregrine
IainPeregrine wrote:
I do hope you're defining your own x and y variables instead of trying to use the atomic versions somehow.
...what? :(
Jul 31 2006, 7:05 pm
In response to Koil
The atomic system is a movment and collision detection system. When defining your own movment and collision detection (to do things like pixelized movment) you need to abandon the atomic system (though you still need to use it to display the data, the data itself should be non-atomic).

In other words, things like "loc" and "x" have absolutely no meaning in a pixel based movment system. Instead, you'll need your own way of determining the position of your objects. I use a /coord object:
coord
    var
        x as num
        y as num
    New(var/X as num,var/Y as num)
        x = X
        y = Y
    proc
        copy()
            return new type(x,y)

I then assign each moving object a variable, c, of type /coord. This variable represents the center of the object. So I refer to object.c.x, not object.x.

The point in all this is to give you absolute control over how your objects move and behave. The more of the atomic system you use, the more limited you are.
Jul 31 2006, 8:03 pm
In response to IainPeregrine
I used the bounding sphere. I think it's better than the box somewhat, in my case at least. Since I have triangular ships mostly in Space Invasion, I used circles instead of squares. It works perfectly.

-Exophus
Jul 31 2006, 8:04 pm
In response to Exophus
Ah, that's right, the space game is yours; the Meteor game is Koils. My mistake.
Aug 1 2006, 7:05 am
In response to Exophus
Ummmm . . . why not use bounding triangles then? Maybe I missed something.
Aug 1 2006, 8:40 am
In response to PirateHead
Because I do have a few circular mobs and a few square-ish mobs in my game and triangular wouldn't fit them right. Bounding circles was the best was to go in my situation.