Bounding Circle Collision Detection (Pixel based movement) in Developer Help

ID:140841
 
Aug 24 2009, 4:46 am
Code:
#define PX_STEP 8 // How many pixels to move each step


atom
    var
        radius = null 

turf
    icon='IconSet.dmi'
    icon_state="Grass"


mob
    icon='IconSet.dmi'
    icon_state="Mob"

    animate_movement = 0

    radius = 16

    proc
        pxstep(d)

            if(d&NORTH)
                pixel_y += PX_STEP
                if(pixel_y >= 32)
                    pixel_y = 0
                    y++

            if(d&SOUTH)
                pixel_y -= PX_STEP
                if(pixel_y <= -32)
                    pixel_y = 0
                    y--

            if(d&EAST)
                pixel_x += PX_STEP
                if(pixel_x >= 32)
                    pixel_x = 0
                    x++

            if(d&WEST)
                pixel_x -= PX_STEP
                if(pixel_x <= -32)
                    pixel_x = 0
                    x--

            if(Collision_Check())
                world << "Collision!"

        Collision_Check()
            for(var/atom/a in range(src, 1) - src)
                if((round( Get_Distance(src, a) )) < (radius + a.radius) && a.density)
                    return TRUE

            return FALSE

client
    North()
        mob.pxstep(NORTH)

    South()
        mob.pxstep(SOUTH)

    East()
        mob.pxstep(EAST)

    West()
        mob.pxstep(WEST)


Well my collision detection system works pretty well except from a small minor problem. My Collision_Check() procedure detects collision as expected, but when retreating from the dense object it returns true 3 more times than needed.

So the output being:

Collision!
Collision!
Collision!
Collision!

As there are 4 collision responses I am assuming this is because 32/8(pixel step size) = 4, that's why I need to take the pixel_x and pixel_y variables in account.

One way around could be making my whole collision check dir-specific but that could get pretty annoying when working with non-cardinal directions such as northeast, northwest, southeast, etc.

I understand how the collision system works but I have a strange feeling I'm not implementing it well, if there are any rewrites needed in my system, especially in the "CollisionCheck()" procedure, then please do say.

Here is a working copy of my movement system (including the source code).

Included in the zip file is a video which shows what problem I am running into.

Thank you.

Haywire

#1 Aug 24 2009, 7:12 am
Probably because the player doesn't leave the tile until after it moves 3 more times. So checking the pixel offsets would probably be better in your distance check.

Also, "range(1,src)-src" is the same as "orange(1,src)".
#2 Aug 25 2009, 5:23 am
In response to Kaiochao (#1)
Kaiochao wrote:
Probably because the player doesn't leave the tile until after it moves 3 more times. So checking the pixel offsets would probably be better in your distance check.

Also, "range(1,src)-src" is the same as "orange(1,src)".

Yeah, I knew that much anyway, I was hoping someone could run through my code and check it aswell as explain on how I should go about with my problem.

Thanks for the effort though, and thanks for the "orange()".
#3 Aug 26 2009, 6:56 am
I guess it's safe to say:

@BUMP
#4 Aug 26 2009, 2:07 pm (Edited on Aug 26 2009, 4:08 pm)
There are a couple of problems with your code. The most relevant is in the one proc you didn't care to share; Get_Distance(). For the first problem, though:

Haywire wrote:
Code:
>   proc
>       pxstep(d)
> 
>           if(d&NORTH)
>               pixel_y += PX_STEP
>               if(pixel_y >= 32)
>                   pixel_y = 0
>                   y++
> 
>           if(d&SOUTH)
>               pixel_y -= PX_STEP
>               if(pixel_y <= -32)
>                   pixel_y = 0
>                   y--
> 
>           if(d&EAST)
>               pixel_x += PX_STEP
>               if(pixel_x >= 32)
>                   pixel_x = 0
>                   x++
> 
>           if(d&WEST)
>               pixel_x -= PX_STEP
>               if(pixel_x <= -32)
>                   pixel_x = 0
>                   x--
> 
>           if(Collision_Check())
>               world << "Collision!"

Movement is choppy. When pixel_x goes to say, 34, you set it to zero. Rather, you should set it to 2. You can do this by simply subtracting 32, but I have another point to make. Imagine one object in a tile with a pixel_y value of -31, and another two tiles away with a pixel_y of 31. The former won't be picked up by Collision_Check() because, although visibly close, they are two tiles apart. This can be averted by changing tiles at 16 and -16. See: 
    proc
        pxstep(d)
            if(d&NORTH)
                pixel_y += PX_STEP
                if(pixel_y > 16)  // changing tiles sooner reduces issues
                    pixel_y -= 32
                    y++

            else if(d&SOUTH)    // else if: because d&NORTH&SOUTH is never true
                pixel_y -= PX_STEP
                if(pixel_y < -16)
                    pixel_y += 32
                    y--

            if(d&EAST)
                pixel_x += PX_STEP
                if(pixel_x > 16)
                    pixel_x -= 32
                    x++

            else if(d&WEST)
                pixel_x -= PX_STEP
                if(pixel_x < -16)
                    pixel_x += 32
                    x--

            if(Collision_Check())
                world << "Collision!"
Note that if you need it to be compatible with PX_STEPS that can move several tiles at once, you'll require more math, but that rarely applies.

Also note that your movement proc (and my slightly modified version) does no bounds checking; you can walk right off the map and land in null! You may want to throw some of that in unless you plan on creating a definite border everywhere.<hr>
Well my collision detection system works pretty well except from a small minor problem. My Collision_Check() procedure detects collision as expected, but when retreating from the dense object it returns true 3 more times than needed.

Actually, it doesn't work at all. Have you tried moving along the corner of another circle? You collide from very far away! Luckily, this gets solved the same way as the problem you've posted about. The specific problem is in Get_Distance(). You're not calculating by anything but the objects' x and y values. What about pixel_x and pixel_y? Yours: 
proc
    Get_Distance(atom/a, atom/b)

        var/xx = a.x - b.x
        var/yy = a.y - b.y

        return sqrt( (abs( xx ) **2) +  (abs (yy)**2) )
That gets a distance in number of tiles, not number of pixels like you need for a pixel movement system. On a side note, abs() is absolutely unnecessary because squaring any real number makes it positive. Using the exponent operator ** to square something is also slightly slower than multiplying something by itself. Here's my rewrite: 
proc
    Get_Distance(atom/a, atom/b)

        var
            ax = a.x*32 + a.pixel_x   // absolute position in pixels
            ay = a.y*32 + a.pixel_y
            
            bx = b.x*32 + b.pixel_x
            by = b.y*32 + b.pixel_y
            
            xx = ax - bx
            yy = ay - by
        
        xx *= xx    // x*x faster than x**2
        yy *= yy

        return sqrt(xx +  yy)

[EDIT] Before anyone says anything, yes I know that the absolute x wouldn't be a.x*32+a.pixel_x, but rather (a.x-1)*32+a.pixel_x. That has no real relevance in terms of collision detection (besides maybe reaching the upper limit on number precision one tile sooner), and imposes an additional 4 calculations (in ax, ay, bx, by). [/EDIT]

Once you fix Get_Distance(), your collision issues go away.<hr>Finally, you override only half of the client's directional movement procs; don't forget Northeast(), etc.
#5 Aug 26 2009, 2:15 pm
In response to Kuraudo (#4)
One other thing I wanted to make note of. You can override Collision_Check() to accept coordinates, and then Get_Distance() to do the same. These would be pixel-coordinates (think ax and ay from my rewrite). Then you could pass theoretical new coordinates into Collision_Check() before moving, and if a collision is found you would just return from pxstep() without moving. Here's the idea:

If you check before you move, you don't have to fix the object's position in the event of a collision. However, simply causing movement to fail makes it hard to make colliding objects press right up against each other pixel-wise (I personally think this is a fair trade-off).

If you check after you move, you now have two overlapping objects and have to find a reasonable new position to relocate the object to (which may be based on not only the first collision found, but all objects surrounding it).

Posting as a reply rather than edit, because it's oh-so-common to make an edit after someone has read the post, and then you'd miss it.
#6 Aug 27 2009, 4:10 am
In response to Kuraudo (#5)
Hey thanks for that, I realised the "tile" bit earlier but I wasn't sure if I was thinking the right way or wrong way thus posting this "Code Problem".

Anyhow, it all works fine now thanks to you but just a small question.

When I had put

xx*xx  // knowing that this is faster than xx**2


I was told that this little optimisation doesn't make a difference and that I should revert back to xx**2 as it makes more sense.

So does it really matter? I understand that optimisation is something you shouldn't overdo but it also works if you do it as you go so your program can run at it's optimal, potential speed.

Once again, thank you.
#7 Aug 27 2009, 4:18 am
In response to Haywire (#6)
Haywire wrote:
I was told that this little optimisation doesn't make a difference and that I should revert back to xx**2 as it makes more sense.

Who's that fool?
#8 Aug 27 2009, 4:34 am
In response to Jemai1 (#7)
If I could remember I would tell you, but even then I won't say names on the forum.
#9 Aug 27 2009, 4:42 am
In response to Haywire (#8)
You don't really need to answer that. My question is supposed to answer yours.