How to handle pixel based collision detection

ID:152005
 
Jun 2 2008, 8:36 pm
I'm trying to figure out what to do once my BYOND pixel-based collision detection lib detects collision.
Currently I have this crude proc that I call, that cause objects to bounce away from the object bounced:

Repulse(var/atom/A,var/BUMPED=FALSE)
            if(isturf(src))return

            //world<<"A=[A] src=[src]"
            //world<<"get_dir(A,src)=[get_dir(A,src)] A.dir=[A.dir] NORTH=[NORTH] SOUTH=[SOUTH] BUMPED=[BUMPED]"
            if(REPULSING) return


            switch(get_dir(src,A))
                if(NORTH)
                    if(src.dir==SOUTH) return
                if(SOUTH)
                    if(src.dir==NORTH) return
                if(WEST)
                    if(src.dir==EAST) return
                if(EAST)
                    if(src.dir==WEST) return
                if(NORTHEAST)
                    if(src.dir==SOUTHWEST) return
                if(NORTHWEST)
                    if(src.dir==SOUTHEAST) return
                if(SOUTHWEST)
                    if(src.dir==NORTHEAST) return
                if(SOUTHEAST)
                    if(src.dir==NORTHWEST) return

            REPULSING=TRUE

            var/RepulseDir = A.GetTrueDir(src) //we want src to go backward
            world<<"A=[A] src=[src] BUMPED=[BUMPED] RepulseDir=[RepulseDir]"
            var/count=0

            var/test=src.Bumped(A,RepulseDir,0)
            var/test2=A.Bump(src,RepulseDir,0)
            while(test/*src.Bumped(A,RepulseDir)*/>0||test2/*A.Bump(src,RepulseDir)*/>0)
                count++
                if(count>=A.step_size) break
                src:PixelMove(RepulseDir,1)
                world<<"in loop test=[test] test2=[test2] RepulseDir=[RepulseDir] count=[count]"
                test=src.Bumped(A,RepulseDir,0)
                test2=A.Bump(src,RepulseDir,0)

            REPULSING=FALSE


At first I didn't think I needed this function, but since an object can pass through an object if it's pixel_step size is too large, then I need a way to check for time (ex: every 1 pixel, instead of every 4).
I'm currently using a crude while loop to do this, and I don't know if there's a more efficient way.

So are there other universal methods for dealing with what to do after a collision is detected?


Jun 2 2008, 8:39 pm
I check the next step before it's taken to see if it will result in a collision. There's still a problem if your next step goes completely through an object, which I haven't figured a way around, but it's better than checking as objects collide.
Jun 2 2008, 9:14 pm
In response to Xooxer
Xooxer wrote:
I check the next step before it's taken to see if it will result in a collision. There's still a problem if your next step goes completely through an object, which I haven't figured a way around, but it's better than checking as objects collide.

Right. I'm using a while loop that's kind of ugly though because I'm checking for a collision within every pixel. Is there some magical math formula for dealing with this? Forgive me, I'm a writer, I tend to believe that (jargon-intensive) advanced math was made by gnomes and spritely faeries.

Example for my circle2circle test:
while(c<src.step_size)
                switch(Dir2Move)
                    if(NORTH)
                        if(((srcFakeY+1)>>5)<world.maxy)
                            srcFakeY++
                    else if(NORTHWEST)
                        if((((srcFakeY+1)>>5)<world.maxy)&&((srcFakeX-1)>>5)>0)
                            srcFakeY++
                            srcFakeX--
                    else if(NORTHEAST)
                        if((((srcFakeY+1)>>5)<world.maxy)&&((srcFakeX+1)>>5)<world.maxx)
                            srcFakeY++
                            srcFakeX--
                    else if(WEST)
                        if(((srcFakeX-1)>>5)>0)
                            srcFakeX--
                    else if(EAST)
                        if(((srcFakeX+1)>>5)<world.maxx)
                            srcFakeX++
                    else if(SOUTH)
                        if(((srcFakeY-1)>>5)>0)
                            srcFakeY--
                    else if(SOUTHWEST)
                        if((((srcFakeY-1)>>5)>0)&&((srcFakeX-1)>>5)>0)
                            srcFakeY--
                            srcFakeX--
                    else if(SOUTHEAST)
                        if((((srcFakeY-1)>>5)>0)&&((srcFakeX+1)>>5)<world.maxx)
                            srcFakeY--
                            srcFakeX++


                centerX = srcFakeX - (src.maxWidth - src.GetPoint("CENTER",TRUE))
                centerY = srcFakeY - (src.maxHeight - src.GetPoint("CENTER",FALSE))
                AX = AFakeX - (A.maxWidth - A.GetPoint("CENTER",TRUE))
                AY = AFakeY - (A.maxHeight - A.GetPoint("CENTER",FALSE))
                oldPos2center = Pos2center
                Pos2center = Find_Dist(centerX,centerY,AX,AY)
                world<<"Pos2center=[Pos2center] < src:radius+A:radius=[(src:radius+A:radius)]"
                world<<"BUMPED=[BUMPED] src=[src]"
                if(Pos2center<(src:radius+A:radius))
                    if(!BUMPED)
                        src:Repulse(A) //I'm pretty sure Repulse(A) is a bad way of doing this, but I can't figure out where to move src mathematically because it would require knowledge of where the closest point on the rectangle/square is
                    else
                        A:Repulse(src)
                    /*if(BUMPED) A:PixelMove(Dir2Move,c)
                    else src:PixelMove(Dir2Move,c)
                    world<<"A=[A] src=[src] circle collide!"*/
                    if(oldPos2center<Pos2center) return TRUE
                c++


Jun 2 2008, 10:26 pm
In response to Rockinawsome
Well, if you know the radius of the circle, and it's location, and the location and radius of another circle, you can get the distance between the two center points and see if it's less than the two radii combined. I think it would be pretty simple, actually. Not much math involved.
Jun 3 2008, 6:14 am
In response to Rockinawsome
Please don't abuse the : operator. =(

Also, I can't tell how you're detecting whether circles are colliding, but as Xoox said it's not a lot of math:
var/dx = x2 - x1
var/dy = y2 - y1;
var/radii = radius1 + radius2
if ((dx*dx) + (dy*dy) < radii*radii)
    // Collision happens

In the above code, x2 and x1 would be the absolute pixel locations of circle 2 and circle 1, respectively (which you might find via the formula of (x-1)*32 + pixel_x (you might skip the step of subtracting 1 from x if you don't care that pixel offsets start at 32 instead of 0), and the y vars are calculated similarly.
Jun 3 2008, 7:48 am
In response to Kuraudo
Ah Pythagoras. Heck of a guy. But, if this has to be called a lot, is multiplication wise?
Jun 3 2008, 10:03 am (Edited on Jun 3 2008, 10:49 am)
In response to Kuraudo
A lot more is going on in that function than I showed. I just didn't want to take up too much space dumping my entire lib in a post. The formula I'm using though is basically the same as yours.
Jun 3 2008, 10:47 am
I track movement with an hspeed and vspeed set of variables. One tracks horizontal speed in pixels per step, the other vertical speed. If the object detects collision, and I need it to bounce back, I simply do hspeed *= -1, or lower if you want less bounce for horizontal rebounding, and vspeed *= -1 for vertical bounce. I use a loop to move objects according to their speed every so often, so reversing the hspeed or vspeed variables will effectively reverse the direction the object will move in. As far as I know, this is how most 2D games handle it.
Jun 3 2008, 10:58 am
In response to Xooxer
So your objects always move within a while loop? So if the speed is 0 the object doesn't move. That's kind of odd for movement that isn't like a car or something though, because why would I want to run a while loop all the time? I guess I'm just not getting it. Why would would I want to use a speed system instead of moving the object manually?

I'm not saying your system is bad or wrong, I'm just not following the logic.
Jun 3 2008, 11:13 am (Edited on Jun 3 2008, 11:56 am)
In response to Rockinawsome
My system is based on a common 2D design. Using a loop is just a good idea, for any game. If it's quick and efficient, it shouldn't matter if you call it in a loop or manually for every object in the world. My loop doesn't update things that don't need to move, and only does collision detection every round because I need it to emulate gravity, to keep objects falling and resting on their platforms. There might be better ways, I'm just sharing this one.
Jun 3 2008, 2:33 pm
In response to Rockinawsome
Rockinawsome wrote:
Why would would I want to use a [loop] instead of moving the object manually?

Because there's always unexpected situations where things change around the object and the programmer wasn't counting on that happening, and if they programmed movement to activate whenever they called for it, then their guy would just float in the air as the platform disintegrated under him because the programmer never expected that to happen.

If you use a loop, things will always effect your character, even if you weren't expecting them.
Jun 3 2008, 5:32 pm
In response to Xooxer
Xooxer wrote:
My system is based on a common 2D design. Using a loop is just a good idea, for any game. If it's quick and efficient, it shouldn't matter if you call it in a loop or manually for every object in the world. My loop doesn't update things that don't need to move, and only does collision detection every round because I need it to emulate gravity, to keep objects falling and resting on their platforms. There might be better ways, I'm just sharing this one.

No it makes sense to me, I just wanted to make sure I understood your reasoning before I took all the effort to overhall my current system, especially when I had concerns about efficiency.
Jun 3 2008, 5:37 pm
In response to Foomer
When you put it like that it makes a lot of sense. Still, using a loop in BYOND always makes me worry about efficiency, but I think I may try to construct a new collision detection system using this loop idea.
Jun 3 2008, 9:07 pm
In response to Rockinawsome
 
Repulse(var/atom/A,var/BUMPED=FALSE)
    if(isturf(src))return
        //world<<"A=[A] src=[src]"
        //world<<"get_dir(A,src)=[get_dir(A,src)] A.dir=[A.dir] NORTH=[NORTH] SOUTH=[SOUTH] BUMPED=[BUMPED]"
    if(REPULSING) return
    if(get_dir(src,A) == turn(src.dir, 180)) return
    REPULSING = TRUE
    var/RepulseDir = A.GetTrueDir(src) //we want src to go backward
    world<<"A=[A] src=[src] BUMPED=[BUMPED] RepulseDir=[RepulseDir]"
    var/count=0
    var/test = src.Bumped(A,RepulseDir,0)
    var/test2 = A.Bump(src,RepulseDir,0)
    while(test/*src.Bumped(A,RepulseDir)*/>0||test2/*A.Bump(src,RepulseDir)*/>0)
        count++
        if(count >= A.step_size) break
        src:PixelMove(RepulseDir,1)
        world<<"in loop test=[test] test2=[test2] RepulseDir=[RepulseDir] count=[count]"
        test = src.Bumped(A,RepulseDir,0)
        test2 = A.Bump(src,RepulseDir,0)
        REPULSING = FALSE<dm>

I made it shorter! =D
Jun 3 2008, 9:34 pm
In response to Wires
Wires wrote:
Repulse(var/atom/A,var/BUMPED=FALSE)
>   if(isturf(src))return
>       //world<<"A=[A] src=[src]"
>       //world<<"get_dir(A,src)=[get_dir(A,src)] A.dir=[A.dir] NORTH=[NORTH] SOUTH=[SOUTH] BUMPED=[BUMPED]"
>   if(REPULSING) return
>   if(get_dir(src,A) == turn(src.dir, 180)) return
>   REPULSING = TRUE
>   var/RepulseDir = A.GetTrueDir(src) //we want src to go backward
>   world<<"A=[A] src=[src] BUMPED=[BUMPED] RepulseDir=[RepulseDir]"
>   var/count=0
>   var/test = src.Bumped(A,RepulseDir,0)
>   var/test2 = A.Bump(src,RepulseDir,0)
>   while(test/*src.Bumped(A,RepulseDir)*/>0||test2/*A.Bump(src,RepulseDir)*/>0)
>       count++
>       if(count >= A.step_size) break
>       src:PixelMove(RepulseDir,1)
>       world<<"in loop test=[test] test2=[test2] RepulseDir=[RepulseDir] count=[count]"
>       test = src.Bumped(A,RepulseDir,0)
>       test2 = A.Bump(src,RepulseDir,0)
>       REPULSING = FALSE

I made it shorter! =D

Thanks!
Jun 4 2008, 1:33 pm
In response to Wires
Curses. I was about to suggest the same improvements -- the turn(src.dir, 180) thing in particular. ;-)