Collision Detection

ID:145170
 
May 30 2006, 6:24 am
Code:
mob/Player/CheckHit(atom/S,Slope)
    //y=mx+b
    var
        Rad = 6
        Y1 = y+pixel_y/32+16-Rad //Bottom
        Y2 = y+pixel_y/32+16+Rad //Top
        X1 = x+pixel_x/32+16-Rad //Left
        X2 = x+pixel_x/32+16+Rad //Right
    if(Slope)
        var
            BI = (Y1-S.y)/Slope  //Bottom intercept
            TI = (Y2-S.y)/Slope  //Top intercept
        if((X1<=BI && BI<=X2) || (X1<=TI && TI<=X2))
            world<<"-----------HIT----------"
            return src
    var
        LI = Slope*X1+S.y        //Left intercept
        RI = Slope*X2+S.y        //Right intercept
    if((Y1<=LI && LI<=Y2) || (Y1<=RI && RI<=Y2))
        world<<"-----------HIT----------"
        return src
    return 0


Problem description:
I've been working on this bit of code for a while now, and I think this method should work, but it doesn't. Can anyone see any reason? It works at a few different slopes, but not at all of them, and it sometimes registers a hit even if I'm facing 90 degrees away from them...

Thanks in advance!
May 30 2006, 12:52 pm
All you need is the distance formula and the law of sines. For reference, that's

proc/distance(x1, y1, x2, y2)
  return sqrt( (x2-x1)^2 + (y2-y1)^2 )


For this example, let's ditch the "grid" and use circles instead.

circle
  var
    radius
    x
    y


So, let's write our checkhit() proc.

proc
  checkhit(circle/one, circle/two, slope/* as angle in degrees*/)
    // first, let's get the distance between
    // our two circles.
    var
      d = dist(one.x,one.y,two.x,two.y)
    // next, let's determine the point at the end of
    // they line segment with its origin at one's
    // coordinates, going at an angle of slope
      ls_y = d*sin(slope)
      ls_x = d*sin(90-slope)
    // finally, we can check to see whether there's a
    // collision
      hit = dist(ls_x,ls_y,two.x,two.y)
    if(hit <= two.radius) return 1
    else return 0


Without comments, it looks like this:

proc/checkhit(circle/one, circle/two, slope)
  var
    d = dist(one.x,one.y,two.x,two.y)
    ls_y = d*sin(slope)
    ls_x = d*sin(90-slope)
    hit = dist(ls_x,ls_y,two.x,two.y)
  if(hit <= two.radius) return 1
  else return 0


Does that make sense? Let's give a test example.

You (at origin (0,0)) shoot at a circle at (4,7) with radius=3, with an angle of 40 degrees.
d = dist(0,0,4,7)
  = sqrt( (4-0)^2 + (7-0)^2 )
  = sqrt( 16 + 49 )
  = 8.06 (approx)
ls_y = 8.06 * sin(40)
     = 5.18 (approx)
ls_x = 8.06 * sin(90-40)
     = 8.06 * sin(50)
     = 6.17 (approx)
hit = dist(6.17, 5.18, 4, 7)
    = sqrt ( (4-6.17)^2 + (7-5.18)^2 )
    = sqrt ( 4.7 + 3.31 )
    = 2.83
2.83 <= 3?
Yes => return 1 (a hit!)

Like I said, all distance formula. And a little law of sines to spice things up.

Please do double-check my work. It's hard to think about this stuff without scratch paper.
May 30 2006, 1:29 pm
In response to PirateHead
sqrt is slow and ^ is xor and not power. ** is for power, but that's still slower than just plain old multiplication. You're better off returning the squared distance and adjusting the checks to account for that.
proc/distance(x1, y1, x2, y2)
  var/dx = x2-x1
  var/dy = y2-y1
  return dx*dx+dy*dy

May 30 2006, 1:46 pm
In response to tenkuu
You still need square root, whether or not it's slow. Good catch on the ^ vs ** thing -- and it seems silly to me that ** is slower than good ole' multiplication, but whatever.

proc/dist(x1, y1, x2, y2)
  var
    dx = (x2 - x1)
    dy = (y2 - y1)
  return sqrt( dx*dx + dy*dy )


That ought to work well, yes?
May 30 2006, 2:09 pm (Edited on May 30 2006, 2:15 pm)
In response to PirateHead
I just realized you will need sqrt(), but that means you'd only need it once in checkhit() for the first distance calculation. It's unneccessary for the second. Just cutting it out of the distance() proc means you can use it only where you have to. That one change cuts out quite a large number of sqrt() uses for a proc that's going to get used heavily. Also, what's with the sin(90-slope)? That's just cos().

proc/checkhit(circle/one, circle/two, slope)
  var
    d = sqrt(dist(one.x,one.y,two.x,two.y))
    ls_y = d*sin(slope)
    ls_x = d*cos(slope)
    hit = dist(ls_x,ls_y,two.x,two.y)
  return (hit <= two.radius*two.radius)


** is slower since it most likely uses a loop internally not to mention it also supports decimal powers and the like.
May 30 2006, 2:13 pm
In response to tenkuu
Distance always requires a square root, unless you're doing distance in one dimension (which we can never assume in this example). Cutting sqrt out of distance() and putting it in elsewhere doesn't help you any.

Besides, it's not *so* slow. You'll probably do this once per tick at most, because things shouldn't move much between then in an action game.
May 30 2006, 2:19 pm
In response to PirateHead
If you're just comparing distances, you don't need sqrt(). It doesn't matter if you're comparing distance or squared distance, it's going to work the same.
May 30 2006, 2:32 pm
In response to tenkuu
Oh, so you're saying just to compare dist() to radius*radius. That makes sense.

DarkCampainger, are you catching all this?
May 30 2006, 2:56 pm
In response to PirateHead
Sorry it's taken me so long to reply, but there are some large storms rolling through my area, and I shutdown during them just to be safe.

If ls_x and ls_y are the endpoint of the radius as I suspect, shouldn't you add circle one's x/y to it? If so, then the only reason the test example worked was because one circle was at (0,0).

I finally got it working just a second ago! Here's what I ended up with: 
proc/dist(x1, y1, x2, y2)
    var/dx = x2-x1
    var/dy = y2-y1
    return sqrt(dx*dx+dy*dy)


mob/Player/CheckHit(atom/S,Angle)
    // first, let's get the distance between
    // our two circles.
    var
        S_x = S.x+0.5+S.pixel_x/32
        S_y = S.y+0.5+S.pixel_y/32
        T_x = x+0.5+pixel_x/32
        T_y = y+0.5+pixel_y/32

        d = dist(S_x,S_y,T_x,T_y)
    // next, let's determine the point at the end of
    // they line segment with its origin at one's
    // coordinates, going at an angle of slope
        ls_y = (d*sin(Angle))+S_y
        ls_x = (d*cos(Angle))+S_x
    // finally, we can check to see whether there's a
    // collision
        hit = dist(ls_x,ls_y,T_x,T_y)
    if(hit <= 0.25) return src
    else return 0


Thanks for all the help guys! You'll both be going down in the credits :D

May 31 2006, 10:27 am
In response to PirateHead
Do you think incorporating the update system on Move() would be more lag efficient than doing it once every tick? When any player moves, update his radar as well as those around him.
May 31 2006, 11:26 am
In response to CaptFalcon33035
I don't understand your comment. The post that you replied had nothing to do with radar, and made no insinuation that anything ought to be done every tick. Would you elaborate?