# 2D game with collision detection, and I need help with how to resolve a collision

At the moment I have built a custom Vector2 class and have a character object that has an acceleration vector (modified by vector forces), a velocity, and a position as well as bounding boxes for every entity within the scene.

Right now my physics works quite well and the character falls and moves with gravity and player input and is able to detect when it collides with another rectangle bounding box shown here:

 void
PhysicsEngine::TimeStepProcess(float deltaTime,
Entity* character, std::vector<Walls*> walls,
double screenWidth, double screenHeight,
int timeStep)
{
double processedDeltaTime = deltaTime / timeStep;

//Process entire physics engine multiple times per step with
//a smaller deltaTime for more accuracy
for (int i = 0; i < timeStep; ++i) {
ComputeForceAndTorque(character);
//ApplyForce(character, gravity);
ApplyForce(character, character->GetForce());

//Calculate and resolve collisions
ResolveCollisions(character, walls, processedDeltaTime);

//Set angular acceleration
angularAcceleration = character->GetTorque() / character->GetIntertia();

//Add Velocity per frame for linear and angular
*character->GetAngularVelocity() += angularAcceleration * processedDeltaTime;

//Add displacement per frame for linear and angular
*character->GetAngle() += *character->GetAngularVelocity() * processedDeltaTime;

CalculateFriction(character, processedDeltaTime);

//Clear forces per frame
Vector2::ScaleMult(*linearAcceleration, *linearAcceleration, 0, Vector2::EQUAL);
}

//Log
LogCurrent(character);
}


With the collision being detected quite accurately here:

void
PhysicsEngine::ResolveCollisions(Entity* character, std::vector<Walls*> walls, double deltaTime)
{
double minDistanceFromObject = 1; //pixels

//Iterate through all walls
vector<Walls*>::iterator wallIter;
for (wallIter = walls.begin(); wallIter != walls.end(); ++wallIter) {
if (character->GetCollisionBox()->CheckCollision((*wallIter)->GetCollisionBox())) {
//Resolve collision
}
}
}

//Does this rectangle contain other rectangle
bool
Rectangle::CheckCollision(Rectangle* other) {
//The sides of the rectangles
int leftA, leftB;
int rightA, rightB;
int topA, topB;
int bottomA, bottomB;

//Calculate the sides of rectangle A
leftA   = static_cast<int>(this->X());
rightA  = static_cast<int>(this->X() + this->W());
topA    = static_cast<int>(this->Y());
bottomA = static_cast<int>(this->Y() + this->H());

//Calculate the sides of rectangle B
leftB   = static_cast<int>(other->X());
rightB  = static_cast<int>(other->X() + other->W());
topB    = static_cast<int>(other->Y());
bottomB = static_cast<int>(other->Y() + other->H());

//If any of the sides from rectangle A are outside of B
//Then there is no possible way the two boxes are colliding
if (bottomA <= topB) {
return false;
}
if (topA >= bottomB) {
return false;
}
if (rightA <= leftB) {
return false;
}
if (leftA >= rightB) {
return false;
}

//If none of the sides of the primary rectangle are outside of other
//Then there must be a collision of some sort
return true;
}


But my vector math is quite shaky and I have no idea how to resolve these collisions and stop the character moving through surfaces. I want to be able to walk along floors and collide with any surfaces realistically. I have now been trying to accomplish this for over a week and have gone through at least 20-30 posts, comments, articles and questions about this and cannot understand how it works or how to implement it.

I get this question a lot at my school's physics club. As an immediate answer, check out the source code from Box2D-lite, which is an educational engine designed exactly for this purpose, and is provided by Erin Catto, one of the makers of Box2D. According to him, he recently updated his box2d lite implementation. What you'll find in here is the result of an incredible amount of research and planning rolled up into a small, easy to follow codebase. While you're reading that, I highly encourage you to examine the following presentations which outline the mathematical details pertaining to your question, as I could not explain it all in one go.

Having tried collision resolution before, I can tell you what happens when trying to solve the problem of resolution on your own using kinematic equations alongside the collision equations; you will wind up with tolerable results at first, but you will find that your boxes do not stack, and multibody collisions are a nightmare, and when you get to apply the rotational aspects of collision resolution it will get even harder.

This is why I recommend these resources first; the task of realtime rigid body simulation in games is a non-trivial problem, and there are many many ways of going about solving them. There are tried and true methods such as sequential impulse solvers (which I believe Erin Catto came up with and demonstrates in his engine) or projected gauss-siedel solvers which are industry standards when it comes to this. Currently PhysX, for example, employes a mysterious solver that we're all waiting for documentation on called the Temporal Gauss-Sidel solver, which appears to have made some stability improvements.

Resources:

Here is the file containing the code you're looking for, but the setup for an iterative solver like this requires a bit of extra design in addition to what you've got. Most importantly caching contacts so they persist over frames is tricky, but for most comprehensive implementations, it's a must.

http://box2d.org/files/GDC2006/GDC2006_Catto_Erin_PhysicsTutorial.ppt

http://www.chrishecker.com/images/e/e7/Gdmphys3.pdf

https://www.toptal.com/game/video-game-physics-part-iii-constrained-rigid-body-simulation

http://box2d.org/files/GDC2011/GDC2011_Catto_Erin_Soft_Constraints.pdf

https://www.randygaul.net/2013/03/27/game-physics-engine-part-1-impulse-resolution/

http://twvideo01.ubm-us.net/o1/vault/gdc2013/slides/822403Gregorius_Dirk_TheSeparatingAxisTest.pdf

http://box2d.org/files/GDC2013/GDC13_vandenBergen_Gino_Physics_Tut.pdf

https://gamedevelopment.tutsplus.com/tutorials/how-to-create-a-custom-2d-physics-engine-friction-scene-and-jump-table--gamedev-7756

http://box2d.org/files/GDC2013/Tonge_Richard_PhysicsForGame.pdf

http://box2d.org/files/GDC2005/IterativeDynamics.pdf

(i believe Erwin Coumans did a lot of work regarding Featherstone, possibly with Rockstar games in developing their fabulous ragdoll implementation alongside the Euphoria engine) http://box2d.org/files/GDC2014/ErwinCoumans_ExploringMLCPSolversAndFeatherstone.pdf

• This is... probably the most detailed answer I've ever gotten. Thank you so so much. A couple of those articles I've actually already read, but Randy Gaul's Game Programming Blog actually gives me a lot of the answers I need. I'm trying to keep my solution simple so as to avoid coding a full engine as this is just a small uni project and what I was really really looking for is how to find the direction of a collision and resolve a collision simple by reversing the velocity direction. But this answer is fantastic and really does answer quite a few questions I've had. – Aquaphor Sep 11 at 13:03
• The only thing I'll need to do is just clean up my vector class cause there's a lot of very shaky vector math in it right now. But again, thank you so much for all these articles and info. This gives me great detail about how to best approach this. Again, I'm trying to keep it very simple. The only thing I'm moving are the entities that collide with the stationary "flooring/surfaces" so hopefully now I can get it working – Aquaphor Sep 11 at 13:06
• Thanks, I put some oomf into it cause I've been exactly where you're at, spending a few months trying to do it all from scratch without any guidance. This is why I started physics club. Incidentally, the struggle is how I came to love physics programming and geometry. Addictive problem solving I guess. Please feel free to hit me up any time, I have a folder full of the collective resources we've been able to accrue over the last few years on the topic plus the means to ask questions to others who might be able to help. – Jon Koelzer Sep 11 at 13:16

In particular, for as simple as a possible solution, I could just use this code and make sure that the second object has 0 velocity and infinite mass or has a restitution coefficient of 0.

// j = -(1 + epsilon) * N dot Vrel
// -------------------------------
//        invM_1 + invM_2
void Manifold::ApplyImpulse( void )
{
Vec2 rv = B->m_velocity - A->m_velocity;
real contactVel = Vec2::DotProduct( rv, normal );

// Do not resolve if velocities are separating
if(contactVel > 0)
return;

// Calculate restitution
real e = std::min(A->m_material.restitution, B->m_material.restitution);

// Calculate impulse scalar
real j = -(1.0f + e) * contactVel;
j /= A->m_massdata.inv_mass + B->m_massdata.inv_mass;

// Apply impulse
Vec2 impulse = j * normal;
A->m_velocity -= A->m_massdata.inv_mass * impulse;
B->m_velocity += B->m_massdata.inv_mass * impulse;
}

• This Randy Gaul's old code? Just as an FYI, that site is good for conceptual understanding and his explanations, but I would take that code with a grain of salt. It's a bit of an amalgamation. I believe this is where he also employes positional correction, a technique commonly referred to as non-linear gauss siedel. Randy gaul has a more recent implementation of simplified 2D physics covering niche techniques and tricks which he presented to physics club last fall, his demo and slideshow are available on his github github.com/RandyGaul – Jon Koelzer Sep 11 at 13:49
• @JonKoelzer This is perfect. His slides and demo are exactly what I needed. Thank you so much. – Aquaphor Sep 12 at 3:26
• Happy to help, friend – Jon Koelzer Sep 12 at 3:46