I've been trying to implement casey's collision detection algorithm and it works great for colliding with objects that are not moving. If my player is moving towards the wall and the wall itself is moving towards the player then the player can easily go through the wall. Is this supposed to happen with this algorithm? I looked ahead in the videos and this issue doesn't seem to come up, forgive me if I'm wrong. As I understand the problem is that once the wall moves in the direction of the player then the player will no longer collide with that wall in the next frame, so I tried to implement something that would move the player along with the wall in case the wall registers a collision with the player. That did improve somewhat but I can still make the player go through if I try hard enough. So my question is how do we fix this? Is a different method of collision detection required or can we do something that fixes this for good with casey's system?
Edited by BernFeth
on
Reason: Initial post
Hello,
I'm not a collision detection expert, I've been watching this part of Handmade Hero a long time ago, and this will answer the question about collision detection but not collision responses, so there might be gaps in my answer below.
For moving objects, to model the movement of the object between two frames, you compute the Minkowski sum 2 shapes: your moving object at the position of the previous frame + your moving object at the position of the current frame. This allows you to detect any collisions when your object moves between those 2 positions, regardless of the distance your object travels between those frames.
After this, if for example your moving object is a circle, the minkowski sum of these two shapes will be a capsule that contains those two circles.
If you want to move another object like a wall, and be able to detect collisions happening between these 2 moving objects between two frames, you'll also need to compute the Minkowski sum of this wall:
If you're doing the sum of only 1 of the shapes, you might miss some occurrences of collisions depending on the speed of the objects. If you do the sum for both objects, you'll basically compute the collision between two bigger objects.
I'm not a collision detection expert, I've been watching this part of Handmade Hero a long time ago, and this will answer the question about collision detection but not collision responses, so there might be gaps in my answer below.
For moving objects, to model the movement of the object between two frames, you compute the Minkowski sum 2 shapes: your moving object at the position of the previous frame + your moving object at the position of the current frame. This allows you to detect any collisions when your object moves between those 2 positions, regardless of the distance your object travels between those frames.
After this, if for example your moving object is a circle, the minkowski sum of these two shapes will be a capsule that contains those two circles.
If you want to move another object like a wall, and be able to detect collisions happening between these 2 moving objects between two frames, you'll also need to compute the Minkowski sum of this wall:
If you're doing the sum of only 1 of the shapes, you might miss some occurrences of collisions depending on the speed of the objects. If you do the sum for both objects, you'll basically compute the collision between two bigger objects.
Edited by Guntha
on
Hi there! Thank you for answering my question.
I'm not really sure I understand what you are suggesting.
I thought minkowski sum was about expanding a point into a bigger shape but by how you are talking it seems to me that the sum would be the bigger shape a particular shape would make after moving between two frames. So I'm not really sure I can make sense of it yet and what the implementation for it would be.
I'm not really sure I understand what you are suggesting.
I thought minkowski sum was about expanding a point into a bigger shape but by how you are talking it seems to me that the sum would be the bigger shape a particular shape would make after moving between two frames. So I'm not really sure I can make sense of it yet and what the implementation for it would be.
In handmade hero, the collision system only simulate the player, no other object moves. And I think the current iteration uses only grid based movement so there are no more collision system (I might be wrong about that).
Without your code it would be hard to help you figure it out, if you can share a simple example that reproduce the problem it would help.
If you want to do collision detection, you can look at GJK. Here is a video from Casey explaining it. Here is a thread in the forum that talk about it.
Note that GJK will only tell you if two shapes are colliding, it doesn't tell you how to solve the collision. That's why EPA is used (if I remember correctly).
Without your code it would be hard to help you figure it out, if you can share a simple example that reproduce the problem it would help.
If you want to do collision detection, you can look at GJK. Here is a video from Casey explaining it. Here is a thread in the forum that talk about it.
Note that GJK will only tell you if two shapes are colliding, it doesn't tell you how to solve the collision. That's why EPA is used (if I remember correctly).
Hi there, thanks for answering! My code is very much similar to casey's around episode 45 to 50 I think it's when he implements it.
TestWall:
Collision detection loop: (It's inside my "game update" function)
This works perfect when World->Obstacle is not moving.
If I make it move with the code below, then I can easily get past it's walls with the Player when it happens that the Player is moving towards the Obstacle at the same time the Obstacle is moving towards the Player.
[code language=c
v2 ObsDelta = V2(sin(GameState->Timer*10) * 1000 * Input->dt, 0);
World->Obstacle->Pos += ObsDelta;
[/code]
The way I went about "solving" this is that after the Player's collision detection I make one for the obstacle:
This seems to be working for what I've tested so far.
So I'm wondering, one thing I could do is loop all entities and for each collision decide if it should glide or push the other entity, is that a good or bad idea? This would be a n^2 if I test all entities against each other so is there a better method?
Thanks for the recommendation, I had forgotten about the gjk thing casey talks about in handmade hero. Will watch the video. I figure that must be a better way of doing it.
TestWall:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | internal b32 TestWall(r32 TestX, r32 TestY, r32 WallX, r32 WallMinY, r32 WallMaxY, r32 *tMin, r32 TestDeltaX, r32 TestDeltaY) { b32 Hit = 0; if(TestDeltaX != 0.0f) { r32 tResult = (WallX - TestX) / TestDeltaX; r32 Y = TestY + TestDeltaY * tResult; if(Y >= WallMinY && Y <= WallMaxY) { if(tResult >= 0.0f && *tMin > tResult) { *tMin = Max(0.0f, tResult - 0.01f); Hit = 1; } } } return(Hit); } |
Collision detection loop: (It's inside my "game 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 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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | v2 ddPlayerPos = {}; if(Input->Keys[KEY_LEFT].Down) ddPlayerPos.x = -1; if(Input->Keys[KEY_RIGHT].Down) ddPlayerPos.x = 1; if(Input->Keys[KEY_UP].Down) ddPlayerPos.y = -1; if(Input->Keys[KEY_DOWN].Down) ddPlayerPos.y = 1; ddPlayerPos *= 5000; if(Input->Keys[KEY_LCTRL].Down) { ddPlayerPos *= 10; } ddPlayerPos += -4.0f*World->Player->dPos; v2 PlayerDelta = 0.5f * ddPlayerPos * Square(Input->dt) + World->Player->dPos * Input->dt; World->Player->dPos += ddPlayerPos * Input->dt; // Colision detection PLAYER r32 tRemaining = 1.0f; for(u32 k=0; k<4 && tRemaining > 0.0f; ++k) { v2 WallNormal = {}; r32 tMin = tRemaining; r32 PlayerDeltaX = PlayerDelta.x; r32 PlayerDeltaY = PlayerDelta.y; r32 PlayerX = World->Player->Pos.x; r32 PlayerY = World->Player->Pos.y; v2 WallMinCorner = World->Obstacle->Pos - 0.5f*World->Obstacle->Size - 0.5f*World->Player->Size; v2 WallMaxCorner = World->Obstacle->Pos + 0.5f*World->Obstacle->Size + 0.5f*World->Player->Size; // Left Wall if(TestWall(PlayerX, PlayerY, WallMinCorner.x, WallMinCorner.y, WallMaxCorner.y, &tMin, PlayerDeltaX, PlayerDeltaY)) { WallNormal = V2(-1, 0); } // Right Wall if(TestWall(PlayerX, PlayerY, WallMaxCorner.x, WallMinCorner.y, WallMaxCorner.y, &tMin, PlayerDeltaX, PlayerDeltaY)) { WallNormal = V2(1, 0); } // Top Wall if(TestWall(PlayerY, PlayerX, WallMinCorner.y, WallMinCorner.x, WallMaxCorner.x, &tMin, PlayerDeltaY, PlayerDeltaX)) { WallNormal = V2(0, 1); } // Bottom Wall if(TestWall(PlayerY, PlayerX, WallMaxCorner.y, WallMinCorner.x, WallMaxCorner.x, &tMin, PlayerDeltaY, PlayerDeltaX)) { WallNormal = V2(0, -1); } World->Player->Pos += tMin * PlayerDelta; World->Player->dPos = World->Player->dPos - Inner(World->Player->dPos, WallNormal) * WallNormal; PlayerDelta = PlayerDelta - Inner(PlayerDelta, WallNormal) * WallNormal; tRemaining -= tMin; } |
This works perfect when World->Obstacle is not moving.
If I make it move with the code below, then I can easily get past it's walls with the Player when it happens that the Player is moving towards the Obstacle at the same time the Obstacle is moving towards the Player.
[code language=c
v2 ObsDelta = V2(sin(GameState->Timer*10) * 1000 * Input->dt, 0);
World->Obstacle->Pos += ObsDelta;
[/code]
The way I went about "solving" this is that after the Player's collision detection I make one for the obstacle:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | // Wall colission detection v2 ObsDelta = V2(sin(GameState->Timer*10) * 1000 * Input->dt, 0); v2 ObsPos = World->Obstacle->Pos; { r32 tMin = 1.0f; v2 WallMinCorner = World->Player->Pos - 0.5f*World->Player->Size - 0.5f*World->Obstacle->Size; v2 WallMaxCorner = World->Player->Pos + 0.5f*World->Player->Size + 0.5f*World->Obstacle->Size; if(TestWall(ObsPos.x, ObsPos.y, WallMaxCorner.x, WallMinCorner.y, WallMaxCorner.y, &tMin, ObsDelta.x, ObsDelta.y)) { World->Player->Pos += ObsDelta; } if(TestWall(ObsPos.x, ObsPos.y, WallMinCorner.x, WallMinCorner.y, WallMaxCorner.y, &tMin, ObsDelta.x, ObsDelta.y)) { World->Player->Pos += ObsDelta; } World->Obstacle->Pos += ObsDelta; } |
This seems to be working for what I've tested so far.
So I'm wondering, one thing I could do is loop all entities and for each collision decide if it should glide or push the other entity, is that a good or bad idea? This would be a n^2 if I test all entities against each other so is there a better method?
Thanks for the recommendation, I had forgotten about the gjk thing casey talks about in handmade hero. Will watch the video. I figure that must be a better way of doing it.
Edited by BernFeth
on
Sorry, I'm a bit rusty, Minkowski sum is actually what you're saying (instead of testing collision between a circle and a polygon, you "add" the circle to the polygon and then only test if a point, the circle's center, is inside that shape, or if a segment representing a movement of the circle between 2 frames collides with that shape). mrmixer's links are better educated than my explanations.
Your fix seems that it should work.
- I would suggest for you to step in the code or log information to try to figure out what breaks. To step in the code you probably want to force the key input ( Input->Keys[KEY_LEFT].Down = 1 ). Stepping in the code is the best way to actually know what is happening, as other fix might just be hiding an underlying issue.
- There might be a floating point precision issue here. You can test the code using double instead of float and see if it works. If it works, than you can revert to float and try to change the line:
Adjust the value 0.01f to see if it improves things. Note that the size of this value will depend on the range of floating point numbers involve so it's not a "general" fix. Changing that value will make the player stop a little further away from the wall. This will not be perfect because the next time the player moves, if it has a smaller velocity, it will move closer to the wall and the problem will mostly likely rise again.
- Physics is complicated and I'm not an expert, but one other way to solve this is to do multiple smaller fixed time physics steps.
I don't think that would solve the issue, but if you want to have several moving entities you will need something like that. As you mention the n² aspect of it is bad. What you can do is a "broad phase": you try to figure out which entities have a possibility to collide with each other and only test those. Depending on how many object you have, it might cost you more time to do the broad phase than to directly do the collision. Profile it to know.
For example you can say that entities that are more than 2 meters away will never collide. You would still loop on all entities and have a n² loop, but it will do a quick calculation to figure out if a collision is possible. If a collision is possible you add a pair of the two object in a list of possible collisions and you will only do the proper collision code on this list.
- I would suggest for you to step in the code or log information to try to figure out what breaks. To step in the code you probably want to force the key input ( Input->Keys[KEY_LEFT].Down = 1 ). Stepping in the code is the best way to actually know what is happening, as other fix might just be hiding an underlying issue.
- There might be a floating point precision issue here. You can test the code using double instead of float and see if it works. If it works, than you can revert to float and try to change the line:
1 2 3 | *tMin = Max(0.0f, tResult - 0.01f); // to *tMin = Max(0.0f, tResult - 0.1f); |
Adjust the value 0.01f to see if it improves things. Note that the size of this value will depend on the range of floating point numbers involve so it's not a "general" fix. Changing that value will make the player stop a little further away from the wall. This will not be perfect because the next time the player moves, if it has a smaller velocity, it will move closer to the wall and the problem will mostly likely rise again.
- Physics is complicated and I'm not an expert, but one other way to solve this is to do multiple smaller fixed time physics steps.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | float physics_step = 1.0f / 120.0f; float physics_time = 0; /* Game loop.*/ while ( running ) { Input->dt = ...; while ( physics_time < Input->dt ) { /* Collision detection using physics_step. */ v2 PlayerDelta = 0.5f * ddPlayerPos * Square( physics_step ) + World->Player->dPos * physics_step; World->Player->dPos += ddPlayerPos * physics_step; TestWall( ... ); /* Same for the obstacle */ ... physics_time += physics_step; } /* In this example I choose to probably simulate more than Input->dt time. It might be a better idea to simulate one physics step less. But in either case you want to keep count of the extra work for the next frame. */ physics_time -= Input->dt; } |
BernFeth
So I'm wondering, one thing I could do is loop all entities and for each collision decide if it should glide or push the other entity, is that a good or bad idea? This would be a n^2 if I test all entities against each other so is there a better method?
I don't think that would solve the issue, but if you want to have several moving entities you will need something like that. As you mention the n² aspect of it is bad. What you can do is a "broad phase": you try to figure out which entities have a possibility to collide with each other and only test those. Depending on how many object you have, it might cost you more time to do the broad phase than to directly do the collision. Profile it to know.
For example you can say that entities that are more than 2 meters away will never collide. You would still loop on all entities and have a n² loop, but it will do a quick calculation to figure out if a collision is possible. If a collision is possible you add a pair of the two object in a list of possible collisions and you will only do the proper collision code on this list.
You need to specify the language in the code tag. It's not specified anywhere, but it's available.
<code language=c> Replace the < and > with [ and ] </code>
<code language=c> Replace the < and > with [ and ] </code>