Collision Detection

[Disch]

Oh all right. I'm typing something up now. Gimmie a few mins.

[Lachlan Easton]

Recommended reading: http://gamedev.tutsplus.com/tutorials/implementation/create-custom-2d-physics-engine-aabb-circle-impulse-resolution/

[Disch]

Oh alright.



THE BASICS

The general idea is that your walls consist of line segments, rather than tiles. You can still have tiles to draw your graphics... but the map that the in-game objects interact with is a bunch of line segments.

Likewise, objects are defined by the lines of their bounding boxes (assuming you want objects to be rectangular, which for this example I'm going to assume is the case).


When you move, you no longer have to check tiles to see if you overlap them. Instead, you project lines from each of the object's corners in the direction they're moving. If any of those lines intersect with a wall, you know there is a collision, and you only allow movement up to the point of intersection.

This is really hard to illustrate in ASCII graphics... but I'm going to try

Fig 1:
O is where the object is currently
? is where the object is moving to (position + velocity)
=, | are walls

OOO      |
OOO      |
OOO      |
         |
         |
         |
         |  ???
         |  ???
         |  ???
==========

What you'd do is project a line from each corner of the 'O' in the direction of the movement vector

Fig 2:
. = the projected line
X = where the projected line intersects with a wall

OOO      |
OOO      |
OOO      |
   ..    |
     ..  |
       ..|
         X. ???
         | ..??
         |  ?..
==========

Since there's an intersection here, you know the object is hitting a wall. So to "eject" it, you simply scale the movement vector back so it doesn't exceed the intersection point. In this example I'm only doing the lower-right corner... but in practice you'd have to do all 4 corners (or 3 if you want to get sneaky -- or even down to 2 if you're only moving along 1 axis ... but I digress)

In the end... stopping movement at the intersection point has pretty much perfect results:

Fig 3:
~ = the previous object position
O = current object position
? = attempted object position

~~~      |
~~~      |
~~~      |
   .. OOO|
     .OOO|
      OOO|
         X. ???
         | ..??
         |  ?..
==========

Reasons why this is better than tile-based collision:

#1) There are usually going to be fewer nearby "lines" to check against than there are going to be tiles. So it can perform better
#2) Tunnelling is impossible. Walls can be paper thin, objects can be any size, and you can move as fast as you like -- you will never tunnel through a wall.
#3) Slopes are a non-issue. Angled lines or straight lines don't matter... intersection code for all of them is the same.
#4) You get "perfect" diagonal movement... whereas with the tile approach you have to sort of "zig-zag" across the map because you can only move 1 axis at a time.



THE "STABBING" PROBLEM

While the above is pretty simple and covers most cases, it does not cover all cases. Only projecting from the corners of the object means that you'll only collide with a wall when your corner hits one. It doesn't handle when your SIDE hits one. I call this getting "stabbed" by a wall. Example:

OOOO  ????
OOOO  ?===========
OOOO  ?|??
OOOO  ?===========
OOOO  ????

Clearly we're moving into a wall here. However our collision detection won't catch it because none of the object's corners will intersect a wall line. The wall is "stabbing" the object between its corners.

To solve this, we need to project a line from the corners of the walls in the opposite direction of the movement vector... and check collision with the lines of the object. Doing that here:

OOOO  ????
OOOO  ?===========
OOOO  ?|??
O..X...===========
OOOO  ????

In this example, projecting a line from the bottom-left wall corner towards the object, it shows us that the projected line intersects with the right-side wall of the object. So again... all you have to do is scale the movement vector back so it does not exceed this collision point:

~~~OOOO???
~~~OOOO===========
~~~OOOO|??
~..OOOO===========     (I dont know if this diagram is any clearer....
~~~OOOO???               it's kind of messy.) 

THE MATH

The key to making this approach work is being able to get the intersection point (if any) of two line segments. And quick. This might seem easy... but if you actually try to start coding it you might realize it's a tougher problem than you thought. Especially if you want it to be precise.

But when you know the trick to it, it's pretty simple.

Let's say we have 4 points forming 2 lines. Points A and B form line AB, and points C and D form line CD. We want to find where these two lines intersect. We'll also say that the lines are inclusive of A/C but not of B/D.

First, let's take an interesting twist on how to represent points on a line. Let's scale it back so that we can deal with a normalized (scaled to 1.0) value. We can do this by saying any point 'P' on line AB can be represented by the following formula:

P = ((B - A) * k) + A

With this formula... 'k' becomes a normalized value:
When k=0.0, P=A
When k=1.0, P=B
when k=0.5, P = halfway between A and B

if k is <0 or >=1, then P does not lie on line AB.. but is to either side of it.

We can do the same with line CD:

Q = ((D - C) * m) + C

Here, 'm' is our normalized value. Again, 0 <= m < 1 must be true for Q to fall on line segment CD


Now for the interesting bit. At the point of intersection, both lines share the exact same point (the intersection point). So at that point... P=Q.

This also means that at the intersection point...

        P         =         Q
((B - A) * k) + A = ((D - C) * m) + C

A, B, C, and D are all known values here. So the only unknowns are k and m. If we solve this equation for k and m, we can find the collision point through some simple calculations!


I'll spare you the work of actually solving these. The actual formulas are below:

to simplify, I am using shorthand:
DCy = (D.y - C.y)
BAx = (B.x - A.x)
etc


k = (DCy*CAx - DCx*CAy) / (DCy*BAx - DCx*BAy)
m = (ABy*CAx - ABx*CAy) / (DCy*BAx - DCx*BAy)

Notice:
- The denominators for both are identical
- They seem to follow a pattern: (Fy * Gx - Fx * Gy)

Let's be cute and put that pattern in a function. Let's call it "perpDot" (the name has significance, but nevermind that for now):

double perpDot(const Vector& a, const Vector& b) {  return (a.y*b.x) - (a.x*b.y);  }

The formulas then become simplified further:

k = perpDot( D-C, C-A ) / perpDot( D-C, B-A )
m = perpDot( B-A, C-A ) / perpDot( D-C, B-A )

And with that, it becomes simple to find both k and m... and therefore simple to find the intersection point of two line segments.

bool linesIntersect( const Vector& A, const Vector& B
                     const Vector& C, const Vector& D )
{
    Vector BA = B-A;
    Vector DC = D-C;
    
    // 'f' is the denominator in the above formula
    double f = perpDot(DC,BA);
    if(f == 0)          // can't divide by zero.  This also means (by definition of perpDot which I might
        return false;   //  explain later) the lines are parallel and therefore have no intersection point
        
    Vector CA = C-A;
    double k = perpDot(DC,CA) / f;
    if(k <  0)      return false;   // remember, 0 <= k < 1 must be true for P
    if(k >= 1)      return false;   //    to fall within the line segment
    
    double m = perpDot(BA,CA) / f;
    if(m <  0)      return false;   // same with m
    if(m >= 1)      return false;
    
    return true;
}

[Disch]

THE FINAL TOUCHES

So now that we're able to detect where 2 line segments intersect... we just need to recap on how to use that information to scale back movement to prevent them from moving too far. So let's look at a pseudo-code example:

Vector proj = SomeObjectCorner + MovementVector;

if( linesIntersect( SomeWallLine_A, SomeWallLine_B, SomeObjectCorner, proj ) )
{
    // object is going to hit this wall.  We need to prevent him from moving
    // this entire distance.  But how?
}
else
{
    // object is not going to hit this wall.  Assuming it doesn't hit any other walls,
    //   it's OK to move this object
}

That is the question... isn't it? How can we scale back the movement vector so it doesn't move into the wall? Simply knowing that the lines intersect isn't enough. We need to know how far along the projected line we can move until we intersect. If only there was a way to get that info.

There is! Remember our normalized 'm' value indicates how far along line CD the intersection point is. 0.5 = halfway, 0.25 = a quarter of the way, etc. AND... since we are giving our projected movement line as the CD line to linesIntersect ... that means 'm' is just the value we're looking for! All we need to do is tweak our linesIntersection function to output it somehow:

bool linesIntersect( const Vector& A, const Vector& B
                     const Vector& C, const Vector& D
                     double& m )    // <- add it as an output var
{
  //...
    m = perpDot(BA,CA) / f;  // <- and just assign it, rather than define it locally
  //...
}

With that, we can capture the max distance to travel and scale back the movement vector appropriately:

Vector proj = SomeObjectCorner + MovementVector;
double m;

if( linesIntersect( SomeWallLine_A, SomeWallLine_B, SomeObjectCorner, proj, m ) )
{
    m -= 0.00001;  // shave it just a hair so we stop shy of the intersect point, rather than being directly on top of it
    MovementVector *= m;  // scale back the movement vector
}

And there you have it. Vector based 2D collision detection.



EDIT: Blah of course I get ninja'd with a link to an existing tutorial. hahahahahaha

[N36fSL3A]

Lachlan, physics are useless in a topdown RPG.

Disch, like before, this should be made into an article.

I'll add on to this post if I have any troubles understanding it (got only halfway).

[Daleth]

Lachlan, physics are useless in a topdown RPG.

You're already involving mechanical physics with velocity and collision detection.

Disch, like before, this should be made into an article.

+1 to this.

[o1vk4iN6]

Lachlan, physics are useless in a topdown RPG.

Sure you don't need gravity (you still need reaction, objects bouncing of each other, get hit by an attack and knocked back, etc...) but that's not the chunk of what a physics engine is. There's also a lot of math and geometry used to optimize and also to find collision points for example the trouble your having with 2 axis aligned bounding boxes colliding is covered in those tutorials.

Another tutorial that might help with a simple displacement solver (the reaction) for AABB which could be applicable. In Javascript though.
https://www.ibm.com/developerworks/library/wa-build2dphysicsengine/

[N36fSL3A]

Well I couldn't figure out how to implement the vector-based collision, so I tried to do the one before.

I made a completely different function, and this is what I got.

		void HandleCollide(SDL_Rect object2)
		{
			// Make a temporary rectangle that represents the player's future position
			SDL_Rect futurepos = {X + Xvel, Y, Box.w, Box.h};

			// If there is collision Move the box to the closest possible position
			// to the object without overlapping it.
			bool coll = Collision::ChkCollision(futurepos, object2);
			if(coll)
			{
				// If the object is moving left
				if     (Xvel < 0) {X = (object2.x + Box.w);}

				// Else if the object is moving right
				else if(Xvel > 0) {X = (object2.x - Box.w);}
			}

			futurepos.x = X;
			futurepos.y = Y + Yvel;

			// We check collision a second time, this time for the y coordinate
			coll = Collision::ChkCollision(futurepos, object2);
			if(coll)
			{
				// If the object is moving up
				if     (Yvel < 0) {Y = (object2.y + Box.h);}

				// Else if the object is  moving down
				else if(Yvel > 0) {Y = (object2.y - Box.h);}
			}
		}

Works well if you move in the opposite direction after you collide, but if you move right and then immediately hit the up key I fly around the map like the wizard I am.

[N36fSL3A]

BUMP

I'm still looking at vector-based however.

What do you mean by this? AC = A-C;

[Disch]

What do you mean by this? AC = A-C;

Just what it says? You subtract 2 vectors (A and C) and store the result in AC. =P

vector addition/subtraction works on each coordinate. So this would be the same as:

AC.x = A.x - C.x;
AC.y = A.y - C.y;