Box Collisions

ID:161286
 
May 25 2008, 8:00 am
I need the algorithm for pixel box collisions(For sizes over and under 32x32). So i've gotten that you need the exact location of the atom(x/y*32+pixel_x/y) the Width and Length, and I just now need the algorithm to see if it hits the obj.
May 25 2008, 12:37 pm
A collision occurs if the boxes intersect one another. This means checking the corners of each of the boxes to see if the corners are inside or touching the other boxes.

The algorithm is quite simple: for each corner of the smaller box, check to see if it is inside the bounds of the larger box. If both boxes are equal in size, you can choose whichever box you like.

This is, at its heart, solving a system of inequalities. The difference, of course, is that the computer solves the problem for you by determining whether all of the equations are satisfied with the given "x,y" values plugged in. In this case, you need to find the equations. For boxes that never rotate, this is extremely easy, since the equations are just constant values that you check against. For boxes that can rotate, you have to find the lines that intersect the corners -- the lines that make up the sides of the larger box -- which is much more math intensive.

Basically, the easy version (non-rotating boxes) works like this:

Determine the closest corner of the smaller box
Find the "bounds" of the larger box
If corner's x is greater than/equal to larger box's min x (x >= equation of left side)
And if corner's x is less than/equal to larger box's max x (x <= equation of right side)
And if corner's y is greater than/equal to larger box's min y (y >= equation of bottom side)
And if corner's y is less than/equal to larger box's max y (y <= equation of top side)
Collision has occurred
Else no collision

Usually you would then adjust the position of the smaller box so it was no longer penetrating the larger box. This is more difficult because it depends on which side of the larger box is closer to the offending corner -- compare the absolute value of corner x - large_min_x and corner x - large_max_x to know whether it's the left side or right side, and similarly for corner y and min/max y to determine whether it's the bottom or top. Once you know that, it's a matter of bumping the smaller box by the distance from that side.

The same applies for rotating boxes, but you have to bump perpendicularly to the equation for the side, which is of course very math intensive and takes a lot of working out on paper in order to solve for the general case.
May 25 2008, 10:25 pm
In response to Jtgibson
 
        var/X
        var/Y
        var/A=PixX-C.PixX
        var/B=PixY-C.PixY
        if(A>0)
            X=PixX+Width
        else
            X=PixX-Width
        if(B>0)
            Y=PixY+Length
        else
            Y=PixY-Length
        if(X+MovementX>=C.PixX-Width&&X+MovementX<=C.PixX+Width&&Y+MovementY>=C.PixY-Length&&Y+MovementY<=C.PixY+Length)
            return TRUE
        else return FALSE



Thats what I came up with, PixX means exact x location in pixels they are on the map, PixY means just the exact y location, Length and Width are how big the rectangle is, and MovementX/Y is how big the movement is towards that direction.

It only will bump around the icons head though :/ ...
May 27 2008, 9:14 pm
In response to Bakasensei
This is what I used in a recent platformer demo I was working on. Credit for the arctan2() proc goes to Lummox.

PixelStep

    proc
        arctan2(x,y) return (y>=0)?(arccos(x/sqrt(x**2+y**2))):(-arccos(x/sqrt(x**2+y**2)))

        get_pix_dir(X1, Y1, X2, Y2) // returns the direction from X1,Y1 to X2,Y2
            if(!X1 || !Y1 || !X2 || !Y2) return FALSE // if missing args, retrun
            if(!(X1-X2) || !(Y1-Y2)) return FALSE
            var/Dir = arctan2(X1-X2,Y1-Y2)
            //var/Dir=0 // if they occupy the same coords, the dir is 0
            //if(Y1<Y2) Dir|=NORTH; else if(Y1>Y2) Dir|=SOUTH // check the Y values
            //if(X1<X2) Dir|=EAST;  else if(X1>X2) Dir|=WEST  // check the X values
            return round(Dir) // send back the direction calculated

        get_pix_dist(X1,Y1,X2,Y2)
            if(!isnum(X1) || !isnum(Y1) || !isnum(X2) || !isnum(Y2)) return FALSE
            return max(abs(X1-X2),abs(Y1-Y2))

        // Check for collision between atom A and atom B if
        // atom A were to occupy the Xpos,Ypos pixel coordinates
        get_collision(atom/A, atom/B, Xpos, Ypos)
            // Check for insufficient arguments
            if(!A || !B || !isnum(Xpos) || !isnum(Ypos)) return FALSE

            // No collision if either is non-dense
            if(!A.density || !B.density) return FALSE

            var/Aleft, Aright, Atop, Abottom

            Aleft   = Xpos
            Aright  = Xpos + A.width-1
            Atop    = Ypos + A.height-1
            Abottom = Ypos

            if(Abottom > B.top)    return
            if(Atop    < B.bottom) return
            if(Aright  < B.left)   return
            if(Aleft   > B.right)  return

            var/Amidx = A.absx + round(A.width>>1)
            var/Amidy = A.absy + round(A.height>>1)

            return get_pix_dir(B.midx, B.midy, Amidx, Amidy)

atom
    var
        pixel_step // only effects objects that set pixel_step to 1
        absx // absolute global pixel x location
        absy // absolute global pixel y location

        width   // width of atom in pixels
        height  // height of atom in pixels

        iconx  // x pixel location of the bottom-left corner of the atom in its icon
        icony  // y pixel location of the bottom-left corner of the atom in its icon

        left
        right

        top
        bottom

        midx
        midy


    New()
        spawn()
            if(pixel_step)
                // We'll be animating our own movement, so set this to 0
                var/list/L = loc2pix()
                if(L&&L.len)
                    var/X = L["1"], Y = L["2"]
                    absx = X; absy = Y

                left   = absx
                right  = absx + width-1
                top    = absy + height-1
                bottom = absy
                midx   = absx + round(width>>1)
                midy   = absy + round(height>>1)

        ..() // Initialize and update the pixel position for new atoms.



    proc
        // convert a tile location and pixel offset to pixel coordinates
        loc2pix(mode) // mode 1 returns text, mode 0 for list
            if(!loc) return FALSE // does not work with areas
            var/ABSX = ((((x-1)<<5)+pixel_x+iconx) || ICON_MIN)
            var/ABSY = ((((y-1)<<5)+pixel_y+icony) || ICON_MIN)
            if(mode) return "[ABSX], [ABSY]"
            return list("1"=ABSX, "2"=ABSY)

        // convert pixel coordinates to a tile location and pixel offset
        pix2loc(PixX,PixY, mode) // mode 1 returns text, mode 0 for list
            if(!PixX || !PixY) return FALSE // does not work with areas
            var/X, Y, pixx, pixy
            X = round(PixX>>5)+1
            Y = round(PixY>>5)+1
            pixx = (PixX%ICON_WIDTH)-iconx
            pixy = (PixY%ICON_WIDTH)-icony
            if(mode) return "[X]:[pixx], [Y]:[pixy]"
            return list("1"=X,"2"=pixx,"3"=Y,"4"=pixy)

        PixBump(atom/movable/A, BumpDir) // Called when an atom is bumped
            return (BumpDir || TRUE) // default returns the direction of the Bump or TRUE
May 28 2008, 3:54 am
In response to Xooxer
Hmm, you didn't show the movement in there, but I could probably wing it xD
May 28 2008, 7:13 am
In response to Bakasensei
May 28 2008, 7:28 am
In response to Xooxer
Ick. I question the wisdom of returning the pixel-to-pixel direction on collision unless you really always need it. It's nastily expensive to calculate.

(Also, using x**2 (etc.) instead of x*x is bad bad bad.)

Edit: Also, your get_pix_dir() routine returns false if delta-x or delta-y is 0, and your get_collision() routine returns that value to indicate a collision. Thus you won't be able to collide in the cardinal directions. This is probably not what you intend.
May 28 2008, 8:17 am (Edited on May 28 2008, 11:14 am)
In response to Hobnob
Hobnob wrote:
Ick. I question the wisdom of returning the pixel-to-pixel direction on collision unless you really always need it. It's nastily expensive to calculate.

I always need it, so. Yeah. Always.

[edit]
To elaborate... Well, the object needs to know how to react to what it just bumped into, which depends mainly on the direction. I'd have to request the direction somehow else anyways, so I thought I might as well have it built right into the pixel bump system. If you can think of something superior, please do share.
[/edit]

(Also, using x**2 (etc.) instead of x*x is bad bad bad.)

Like I said, I didn't write the arctan2() proc. I'm just abusing it for my own fiendish desires.

Edit: Also, your get_pix_dir() routine returns false if delta-x or delta-y is 0, and your get_collision() routine returns that value to indicate a collision. Thus you won't be able to collide in the cardinal directions. This is probably not what you intend.

I see. That might explain some of the bugs I was having. Thanks for the info.