C++

Forum

 
Collision Detection

Pages: 12
closed account (N36fSL3A)
I remember some time ago, when I was wondering about collision detection, chrisname told me to put the player at the tile poistion - the player's position.

Instead of this, whenever collision was detected I just reverted his coords. However this is becoming a problem, as this isn't the best method in the world. Sometimes there is still space left between the two objects.

I tried implementing this, but whenever I run into a wall my guy teleports all over the map and ends up at right border of it, unable to move. Here's my code:

A snippet from my update function:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
		HandleMapCollision(map);

		if(Xvel != 0) {moving = true;}
		if(Yvel != 0) {moving = true;}

		// If there is a X collision, revert the X coordinate
		if((Box.x < 0) || (Box.x + Box.w > map.getMapW()))// || (Collided) || (CollidedN))
		{
			//std::cout << "Collision Detected.\n";
			//X = prevx;
			Xvel = 0;
			if(Box.x < 0)             {X = 0;}
			if(Box.x < map.getMapW()) {X = map.getMapW() - Box.w;}
			moving = false;
		}
		
		// If there is a Y collision, revert the Y coordinate
		if((Box.y < 0) || (Box.y + Box.h > map.getMapH()))// || (Collided) || (CollidedN))
		{
			//std::cout << "Collision Detected.\n";
			//Y = prevy;
			Yvel = 0;
			moving = false;

			if(Box.y < 0)             {Y = 0;}
			if(Box.y < map.getMapH()) {Y = map.getMapH() - Box.h;}
		}


HandleMapCollision:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
		void HandleMapCollision(Map &map)
		{
			for(unsigned int t = 0; t < map.Tiles.size(); t++)
			{
				if(map.Tiles[t]->getType() < 16 && map.Tiles[t]->getType() > 11)
				{
					Collided = true;
					moving   = false;

					if(Collision::ChkCollision(map.Tiles[t]->getBox(), Box))
					{
						int tX = map.Tiles[t]->getBox().x;
						int tY = map.Tiles[t]->getBox().y;
						int tW = map.Tiles[t]->getBox().w;
						int tH = map.Tiles[t]->getBox().h;

						if((tX < Box.x))              {Xvel = (/*abs(tX)*/tX - Box.x          );}// Xvel = 0;}
						else if((tX > Box.x + Box.w)) {Xvel = (/*abs(tX)*/tX + (Box.x + Box.w));}// Xvel = 0;}
						else if((tY < Box.y))         {Yvel = (/*abs(tY)*/tY - Box.y          ) ;}// Yvel = 0;}
						else if((tH > Box.y + Box.h)) {Yvel = (/*abs(tY)*/tY + (Box.y + Box.h)) ;}// Yvel = 0;}
					}
				}

				else {Collided = false;}
			}
		}


I must admit this isn't the prettiest code, but I just want to see results, then clean up later.
closed account (o1vk4iN6)
1
2
 
if(Box.x < 0)             {X = 0;}
if(Box.x < map.getMapW()) {X = map.getMapW() - Box.w;}


Both these will be true if the box is over the left edge. You aren't really inverting them either, if box.x < 0 how would setting x to zero invert the coordinates ?
Disch (13742)
Line 13:

1
2
3
4
5
6
7
8
9
 
		if((Box.x < 0) || (Box.x + Box.w > map.getMapW()))// || (Collided) || (CollidedN))
		{
			//std::cout << "Collision Detected.\n";
			//X = prevx;
			Xvel = 0;
			if(Box.x < 0)             {X = 0;}
			if(Box.x < map.getMapW()) {X = map.getMapW() - Box.w;}  // <-
			moving = false;
		}


Notice that if Box.x is < 0, it will also be < map.getMapW(). So if you move off the left side of the map, line 13 will make you jump all the way to the right side.

Similar problem with Y coord at line 26.


Regarding HandleMapCollision:

1
2
3
4
5
6
7
8
9
10
11
12
 
					if(Collision::ChkCollision(map.Tiles[t]->getBox(), Box))
					{
						int tX = map.Tiles[t]->getBox().x;
						int tY = map.Tiles[t]->getBox().y;
						int tW = map.Tiles[t]->getBox().w;
						int tH = map.Tiles[t]->getBox().h;

						if((tX < Box.x))              {Xvel = (/*abs(tX)*/tX - Box.x          );}// Xvel = 0;}
						else if((tX > Box.x + Box.w)) {Xvel = (/*abs(tX)*/tX + (Box.x + Box.w));}// Xvel = 0;}
						else if((tY < Box.y))         {Yvel = (/*abs(tY)*/tY - Box.y          ) ;}// Yvel = 0;}
						else if((tH > Box.y + Box.h)) {Yvel = (/*abs(tY)*/tY + (Box.y + Box.h)) ;}// Yvel = 0;}
					}


What good is Collision::ChkCollision if you have to check collision AGAIN a few lines down? Seems like a waste. Maybe instead of returning a bool it could return an enum indicating which side the collision happened on. Then you could do something like this:

1
2
3
4
5
 
switch( Collision::ChkCollision( ... ) )
{
  case none:  break;  // no collision, do nothing
  case left:  /*collision occurred on left side, eject to the right*/ break;
  // etc
Last edited on
closed account (N36fSL3A)
Alright, well what about Handle Map collision? My characters still fly away...
Disch (13742)
Nothing about that routine makes sense to me.

else if((tX > Box.x + Box.w)) {Xvel = (/*abs(tX)*/tX + (Box.x + Box.w));}// Xvel = 0;}

I had assumed this is ejection to push the player to the left (since it's factoring the box width and not the tile width). With that in mind, let's plug in some numbers:

tX = 100
box.x = 80
box.w = 40

Conceptually... you would want there to be a collision and for it to eject the box back to x=60, right?

So now look at this code:

if((tX > Box.x + Box.w))

First of all, this condition makes no sense. If the left-most part of the tile is further to the right than the right-most part of the box, there's no collision:

1
2
3
4
5
6
7
8
9
10
 
=======     =======
| box |     | tile
=======     =======
^     ^     ^
|     |     |
|     |     tX
|     |
|     box.x + box.w
|
box.x


As you can see in this diagram, the tile and the box clearly do not intersect... yet the condition is true (tX > box.x+box.w)


Furthermore, even if that part was correct, the code you do inside the block doesn't make any sense either:

Xvel = (tX + (Box.x + Box.w));

again.. our sample numbers:
tX = 100
box.x = 80
box.w = 40

tX + box.x + box.w = 100 + 80 + 40 = 220

So to eject the player left... you are shooting them incredibly far to the right. It's no wonder your objects are flying all around ;P




PS:

Debuggers are your friend. You already knew this code was suspect so all you had to do to find this on your own was set a breakpoint in that block, step through it, and watch Xvel to see what was going on.


EDIT:

I didn't mean to rag on you in that PS... and I definitely don't want to discourage you from asking for help. I was just kinda in a weird funk when I wrote that. Sorry if it came off as rude... I was just trying to encourage debugger usage. ^^
Last edited on
closed account (N36fSL3A)
It didn't come off rude. :P

Okay, so I made another function that returns a short integer. Now, I face another problem. It always detects that collision is not there. Here's my new code.

Collision class:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
 
// Collision
class Collision
{
	public:
		static bool ChkCollision(SDL_Rect A, SDL_Rect B)
		{
			int leftA, leftB;
			int rightA, rightB;
			int topA, topB;
			int bottomA, bottomB;

			leftA = A.x;
			rightA = A.x + A.w;
			topA = A.y;
			bottomA = A.y + A.h;

			leftB = B.x;
			rightB = B.x + B.w;
			topB = B.y;
			bottomB = B.y + B.h;

			if(bottomA <= topB) {return false;}
			if(topA >= bottomB) {return false;}
			if(rightA <= leftB) {return false;}
			if(leftA >= rightB) {return false;}

			return true;
		}

		static short ChkCollision2(SDL_Rect A, SDL_Rect B)
		{
			bool coll = ChkCollision(A, B);
			if(coll)
			{
				int leftA, leftB;
				int rightA, rightB;
				int topA, topB;
				int bottomA, bottomB;

				leftA = A.x;
				rightA = A.x + A.w;
				topA = A.y;
				bottomA = A.y + A.h;

				leftB = B.x;
				rightB = B.x + B.w;
				topB = B.y;
				bottomB = B.y + B.h;

				if(bottomA >= topB) {return DOWN;}
				if(topA <= bottomB) {return UP;}
				if(rightA >= leftB) {return RIGHT;}
				if(leftA <= rightB) {return LEFT;}
			}
			else {return 4;}
		}
};


Map Collision
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
		void HandleMapCollision(Map &map)
		{
			for(unsigned int t = 0; t < map.Tiles.size(); t++)
			{
				if(map.Tiles[t]->getType() < 16 && map.Tiles[t]->getType() > 11)
				{
					Collided = true;
					moving   = false;

					int tX = map.Tiles[t]->getBox().x;
					int tY = map.Tiles[t]->getBox().y;
					int tW = map.Tiles[t]->getBox().w;
					int tH = map.Tiles[t]->getBox().h;

					short coll = Collision::ChkCollision2(map.Tiles[t]->getBox(), Box);

					switch(coll)
					{
						case LEFT:
							if((tX < Box.x))              {Xvel = (tX - Box.x          );}
						break;

						case RIGHT:
							if((tX > Box.x + Box.w)) {Xvel = (tX - (Box.x + Box.w));}
						break;

						case UP:
							if((tY < Box.y))         {Yvel = (/*abs(tY)*/tY - Box.y          ) ;}
						break;

						case DOWN:
							if((tH > Box.y + Box.h)) {Yvel = (/*abs(tY)*/tY - (Box.y + Box.h)) ;}
						break;
					}
				}

				else {Collided = false;}
			}
		}


The border collision
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
		//Collided = map.TouchSolid(Box);
		HandleMapCollision(map);

		if(Xvel != 0) {moving = true;}
		if(Yvel != 0) {moving = true;}

		// If there is a X collision, revert the X coordinate
		if((Box.x < 0) || (Box.x + Box.w > map.getMapW()))// || (Collided) || (CollidedN))
		{
			//std::cout << "Collision Detected.\n";
			//X = prevx;
			Xvel = 0;
			if(Box.x  < 0)             {X = 0;}
			if(Box.x >= map.getMapW() - Box.w) {X = map.getMapW() - Box.w - 1;}
			moving = false;
		}
		
		// If there is a Y collision, revert the Y coordinate
		else if((Box.y < 0) || (Box.y + Box.h > map.getMapH() - Box.h))// || (Collided) || (CollidedN))
		{
			//std::cout << "Collision Detected.\n";
			//Y = prevy;
			Yvel = 0;
			moving = false;

			if(Box.y <  0)             {Y = 0;}
			if(Box.y >= map.getMapH() - Box.h) {Y = map.getMapH() - Box.h - 1;}
		}
Last edited on by Fredbill30
Disch (13742)
Plug in numbers, Fredbill

if(rightA >= leftB) {return RIGHT;}

This does not properly detect a collision. Example of where it will fail:

1
2
3
4
5
6
7
8
 
=======     =======
|  B  |     |  A  |
=======     =======
^                 ^
|                 |
|                 rightA
|
leftB




Rather than detecting a collision, maybe try to detect if there ISN'T a collision.

1
2
3
4
5
6
 
if(rightA < leftB)  return false; // no collision
if(rightB < leftA)  return false;
if(bottomA < topB)  return false;
if(bottomB < topA)  return false;

return true;


Of course this doesn't tell you in which direction you need to eject the object. Now that I think about it more I'm not sure that's possible with just the information provided... as you have to factor in their velocity (you would eject them in a direction that opposes their velocity).
closed account (N36fSL3A)
I'm still unsure how to do this. I can change the function to the Base class Object's And can use the velocity in the function. But how would I do it?
edfed (5)
you can also return a collision-box in order to have some sort of collision power indication.

the best, as you are coding in c++, is to use geometrical vectors (not the std::vector) to represent the movements, then, when a colision occurs, you just have to reverse the movement and apply it to correct the "overflow" effect.

1
2
3
4
 
if (box1.collide(box2) != 0) {
box1.chgMove();
box1.move();
}

but basically, a good collision detection occurs always after a move, and should lead to another collision detection, for example, when a box is close to collide a corner, and by bouncing, will hit an adjacent wall during the collision.

the collision detection/correction is recursive.
closed account (N36fSL3A)
What do you mean? My function already takes 2 boxes. I'm already doing what you specified as you can see in my code.

I know what a vector is, obviously. Without them my characters wouldn't be moving.

What you specify is irrelevant. I'm not having trouble with handling after collision, I'm having trouble with the collision itself.



Disch, I think you want me to check what direction the velocity was, and handle from there.

1
2
 
// If the player is moving left
if(Xvel == -Vel) {/*Then we do what I was doing above*/}
Last edited on by Fredbill30
Disch (13742)
Fredbill30 wrote:
I'm still unsure how to do this.


Yeah. It's tricky. I always had frustrations getting tile based collision to work the way I wanted. And in fact... I never did... which is why I stopped using it. Get ready for a wall of text.

One problem that nagged me was this one:

1
2
3
4
5
6
7
8
 
####
####
####..
####..
    ####
 OO ####
 OO ####
    ####


# = a wall tile
O = the rect of the object
. = the rect the object is moving to

As you can see if you allow for diagonal movement like this, it will not catch this collision. This is what's called "tunneling" ...ie, moving so fast you actually move through a wall. Another instance of this:

1
2
3
 
  O
#####
  .


If you're falling fast enough, you can fall right through a thin floor.

One approach to solving this problem is to make your walls/objects bigger, and don't let the objects move so fast. But that's a very debilitating workaround, especially if you have sloped or "drop-thru" floors (where the floor could be literally 1 pixel thick in places).


Your problem is loosly related:

1
2
3
4
 
  ##
 .X#   OO
 .X#   OO
  ##


Here the 'X' indicates the object's new position and the wall overlap. Checking the new object position (the dot) in relationship to the wall position (the #) won't work because the object tunneled part way through the wall. If you were to eject based just on that position... you would eject left, causing the object to tunnel all the way through the wall.

But in fact... desired behavior here is to eject right.

This problem is trivial if you are only moving along one axis. The above problem has a clear solution:

1
2
3
4
 
  ##
 .X#~~ OO
 .X#~~ OO
  ##


# = wall
O = original object position
. = object attempted position
X = . overlapped with #
~ = object position after ejection

You can use the object's velocity to determine how far along the axis to push the object.

IE: if the object is moving left and you want to eject right, you'd set object.left = wall.right
Or if the object is moving right and you want to eject left: object.right = wall.left



However.. this approach utterly fails if you are moving along both X,Y axis. Such an example:

1
2
3
 
X#########~
.   O     ~
    O


It's clear the ejection here is wrong... but according to the above logic it's doing exactly what it's supposed to. It sees a collision and it sees leftward movement, so it ejects right.




So what's the best way to solve it?



I don't know what the "best" way is... but I settled on something like the below to address both the ejection issue and the tunnelling issue.

#1 - forget about ejection. Rather than trying to push the object out of a wall... stop them from entering the wall in the first place.

#2 - move one axis at a time. This has its own problems... especially when the object is moving at high speeds... but it makes detecting wall collisions much easier.

#3 - check every tile along the path of the object's motion... not just the tile at their final destination. This is the only way to prevent tunnelling with tile-based collision.


From what I remember of my last implementation, I wrote 4 functions... one for moving in each direction. The functions would take a starting point and a destination point and step through all the tiles between those two points... and would figure out how far you could move in that direction until you hit a wall.



But that was a long time ago. The last project I did with tile based collision was such a nightmare that I left it forever.

Anyway I don't know if any of this helped. hahaha
Last edited on
closed account (N36fSL3A)
#1 - forget about ejection. Rather than trying to push the object out of a wall... stop them from entering the wall in the first place.
But how would I make it move to the closest possible position? This is all I want to do :(
Disch (13742)
I wrote:
From what I remember of my last implementation, I wrote 4 functions... one for moving in each direction. The functions would take a starting point and a destination point and step through all the tiles between those two points... and would figure out how far you could move in that direction until you hit a wall.


I don't like quoting myself without adding additional info... but I'm not sure if I can explain it any better than this. Is there any particular part of this you don't understand?
closed account (N36fSL3A)
So something like:
abs(point a - point b)
Disch (13742)
it's not going to be a 1-line thing. It's going to be rather involved.

You have to figure out which tiles the starting and ending points lie in, and check those tiles and all tiles between them to see if they're solid. If any of them are solid, you pick the closest one to the starting point as the one the object collides with.


EDIT:

Or at least... that's what I did. If you can come up with a shorter/easier way to do it, power to you.

But either way it's something that's going to require you take a step back and think about design --- think about how you want the code to work (and make sure it'll work the way you want) before you start writing any actual code.
Last edited on
closed account (N36fSL3A)
Disch, it's going to be contained in one function, so as long as I change anything there, it will work for all players/npcs :)

Also, can you give me some sample code? Just a framework.

PS - You should really make that post about collision an article. ;)
Last edited on by Fredbill30
Disch (13742)
Disch, it's going to be contained in one function, so as long as I change anything there, it will work for all players/npcs :)


Well when I did it I wrote 4 functions (one for each direction), then had one "master" function send the job out to those 4.

Also, can you give me some sample code? Just a framework.


Best you're going to get from me is pseudo-code... but it's really just echoing what I already said.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
 // see how far east we can move before hitting a wall
 //  returns the furthest east you can go
int checkEast( int start_x, int end_x, int y )
{
    int tile_index_start = start_x / tilewidth;
    int tile_index_end = end_x / tilewidth;
    int tile_y = y / tileheight;

    int canmove = end_x; // assume they can move all the way

    for(int x = tile_index_start; x <= tile_index_end; ++x)
    {
        Tile& t = get_tile( x, tile_y );
        if( t.isWall )
        {
            canmove = t.left_side;  // can't move any further than this tile's left side
            break;  // can stop looking
        }
    }

    return canmove;
}



Of course to keep this example simple, it assumes the object is no taller than 1 tile. Which is unrealistic. You'll have to modify it to check multiple tiles each iteration of that x loop.

Do this x4 (for each direction). You can see why this is hairy and why I hated it. Add in sloped tiles and it gets even worse.

PS - You should really make that post about collision an article. ;)


No thanks. If I'm going to write an article on the subject, it would be explaining vector based maps and collision detection rather than tile based, because they're just about vastly superior in every way.
Last edited on
closed account (N36fSL3A)
For 2D games? If yes can you explain how I would do this?

BTW it's top down, so I wouldn't have to worry about sloped tiles.
Last edited on by Fredbill30
Disch (13742)
For 2D games? If yes can you explain how I would do this?


Yes 2D... but maybe later. It's quite a topic and I don't feel like getting into it now.
Last edited on
closed account (N36fSL3A)
:(

Now that you mentioned it I want to learn how to do it badly.
Pages: 12