I have been struggling with collision resolution forever. I always wanted to create a platforming game but never managed to get past the collision resolution part. Usually I would start programming a game, and after a while when it comes to collisions, I just sit there for days and weeks, fiddle around with the code and NOTHING works, absolutely nothing. I work less and less on it because it's just nothing except pure frustration and then I kind of let it die. A few months or years later I start trying again, hit the brickwall again and the same thing goes on forever...

I even procrastinated like crazy until I decided to make this post but I don't even know where to start and how I should even formulate my questions.

Sometimes I just have a feeling I may be just too stupid for game development and I will never understand it. My brain just doesn't come up with any solutions anymore. Most of the time I just sit there, looking at the code and after 30 minutes of thinking and not coming up with anything new I just go do something else, this repeats forever, so here I am asking you!

I have read almost every article that I could find on google, a lot of sites links to the same old stuff that doesn't even really explain anything, or just doesn't fit my game. I'm still trying to create some kind of megaman clone, or maybe like shovel knight or mario. Simple 2D collisions without fancy physics. Just 2D box shapes, no rotations, no polygons or circles or whatever.

There are articles that don't cover tunneling, others only try to solve 1 body vs 1 body collisions, others have weird behaviour like jittering on the floor, falling of the edge of a platform, because there is only one "collision point" on the bottom of the player, or when there are 2 points on the right and left foot, fall through blocks if they are narrower than the two points. Player can't be smaller than n x m, can't be faster than x pixels per seconds etc... There doesn't seem to be anything out there that fits my idea of a good collision system.

But there HAS to be a solution because there are TONS of good games out there that don't seem to have all those restrictions.

All I want is a consistent collision resolution system for axis aligned bounding boxes without tunneling, pixel perfect movement, no jittering, or any strange behaviour, because I want the game to be difficult, and when the player suddenly falls through the floor and has to start all over again just because the collision system encountered a rare condition in which it fails, it's going to be extremely annoying and frustrating, especially when it could happen again anytime.

Same goes for suddenly getting pushed through walls, that would make the game too easy ;)

A lot of those articels also don't cover how a "collision system" should be designed in general or how entities/objects/whatever can check and react to collisions, or check their surroundings (like if they are touching the floor or whatever). I want to have a system where I can easily react to

At first when I started I put all of my code in the Player class, had a reference to a class called World, which basically was just a collection of Tiles, with functions to ask something like:

class Player
{
  //...
  private:
    World& _world;
  //...
  public:
    Player(World& world):_world(world){}
  //...
}

void Player::Update(float dt)
{
  if(_world.GetTileAt(x,y).IsSolid())
    // Do something
  if(_world.GetTilesInRect(this->GetBoundingBox()).count() == 0)
    velocity.y += gravity * dt; // Or whatever, just an example
  position += velocity * dt;
}

But then I realized this is going to result in a lot of duplicate code when I want to have the same collision resolution for enemies or pushable boxes or whatever.

So I generalized it, In hopes to be able to just have to implement a function like "HandleCollision(...)" in whatever class I would like to be a part of "the World".

So here are the classes that I have:

Body - Holds information like position, velocity, size, and has a function GetCollisionInfo(Body* other) which returns a struct of data describing when and how this body is going to collide with the other body, by comparing position, size, velocity etc...

CollisionHandler - An Interface that specifies the function HandleCollision(Body* other, CollisionInfo colInfo)

Player - Implements CollisionHandler, holds a reference to it's Body created using World::CreateBody(), then sets body->SetCollisionHandler(this)

World - Keeps a list of all bodies and provides a function CreateBody() which inserts a new body into a vector or whatever and returns a pointer to it.

In my gameloop, world.update() gets called, which then loops over all bodies, asks each body to get a collision info of it and the other body, puts all colliding bodies in a list, orders it by timeOfImpact and then calls body->HandleCollision(other, colInfo) on the first object ("other" is whichever the body collides with first) which delegates the call to player->HandleCollision or whatever has been set as the collisionHandler.

And there I do checks like these:

// Gets called by World::Update()
bool PlayerWalking::HandleCollision(CollisionInfo colInfo, Body* other)
{
	Vector2D newVel = player.body->GetVelocity();
	Vector2D pos = player.body->GetPosition();

	RECT obsRect = other->GetBoundingBox();

	switch (colInfo.impactSide)
	{
		case CollisionInfo::Side::LEFT:
			newVel.x = 0.0f;
			player.body->SetPosition(obsRect.left - player.GetBoundingBox().GetWidth(), pos.y);
			break;
		case CollisionInfo::Side::TOP:
			newVel.y = 0.0f;
			player.body->SetPosition(pos.x, obsRect.top - player.GetBoundingBox().GetHeight());
			break;
		case CollisionInfo::Side::RIGHT:
			newVel.x = 0.0f;
			player.body->SetPosition(obsRect.right, pos.y);
			break;
		case CollisionInfo::Side::BOTTOM:
			/*newVel.y = 0.0f;
			player.body->SetPosition(pos.x, obsRect.bottom);*/
			break;
	}

	player.body->SetVelocity(newVel);

	return true;
}

So this then modifies the velocites or position and at last, the world class increments the position by velocity * timestep, or whatever.

This way I can change how the timestepping works in one place: World::Update(float dt) instead of the objects like player/enemy etc.

So you're probably wondering why I'm even complaining, right? Because it just doesn't work like I want it to and I have a feeling no matter how much I fiddle with the code I will never figure out how to do this correctly.

With this method, what happens in the following scenario?

The first collision that will get handled is the one with the right block.

It cancels out the y velocity, then comes another iteration of checking the velocity against other bodies and since we are now only moving straight left, we move OVER the gap instead of into it.

This is what should have happened (all happening in one frame, animation just for clarification):

So this is what I DONT want! NO SLIDING over gaps!

Of course I could solve this by NOT initiating a NEW iteration of collision checks and instead continue with the one that would happen next.

Instead of checking again, I say I already know we would collide with the left block, so we handle that and place the block at the right side of it.

(Forgot to make a picture for this case, just imagine the "player" a little more to the left, so its left side is aligned at the right side of the left blue rectangle)

Now for this case you COULD say, well thats ok, the player will just start falling down the hole the next frame, right?

Sure, but what if there is no gap? Just 2 blocks next to each other (ground)? Yep, the goold old "player gets stuck when walking over tiles" problem because he gets blocked by the left one..... *sigh*

So all I can do is shuffle the code around, do it in a different order and jump from one problem to another one, without ever being able to eliminate ALL of them at once.

These are the two solutuons that I came up with and none of them work:

// Handle all of the collisions one after another, this one places the block on the right side and stops floor-movement
for (auto it = toiOrderedList.begin(); it != toiOrderedList.end(); it++)
{
	bodyA->HandleCollision(it->second, it->first);
}

// And this one only handles the first collision, then starts another iteration of checks with the new velocities,
// this one makes the player be able to move over gaps/holes and prevents being able to move into a space in a wall,
// because the body just slides past it.
if (!toiOrderedList.empty())
{
	bodyA->HandleCollision(toiOrderedList[0].second, toiOrderedList[0].first);
}

The only thing I can think of is splitting this movement up into 3 different velocity vectors. The first one until it hits the right block, then "slide" it to the left until it hits the edge, then create another vector that moves it left+down again, once the first block doesn't block downward movement anymore.

But that seems insanely complicated, and I am 100% certain this will NOT work or create 5 new problems and I'm just going to waste my time...

Another thing this brings up is, how should it look like if I wanted to check if one body is "touching" another body, or "at the edge" or something?

What does a GOOD collision system design look like? Should the player modify the position/velocity of it's body directly or return some kind of "desired" correction, which then gets evaluated by the "physics system"? Should It all have some kind of generalized behaviour that it just sets up at the beginning? body->SetBehaviour(FALL_ONTO_FROM_ABOVE, SLIDE_ALONG) or something like that instead of having a HandleCollision() which modifies position etc itself?

Btw the reason I'm not using Box2D is, first of all, I want to understand this stuff and be able to do it myself and second of all it just doesn't work very well with pixel-precise movement. Jittering on the floor, having to parse my level and create ghost vertices everywhere two bodies are side by side etc... I tried It and it was ugly. Why should I use a physics library and then program workarounds for the "physics"-part anyway, then why use physics simulation in the first place? Shovel Knight uses it apparently, that's why I tried it.

Hi,

I don't have yet any experience with anything past rudimentary collision detection, but I've been watching the Handmade Hero series, and skimming through your post reminds me of several key points that the series illustrates in great detail how to go about solving. Although his game genre is not a platformer, most all the math applies equally the same.

Check out the episode guide -- starting at roughly "Week 10: Player Collision" and onwards; "Basic Minkowski-based Collision Detection", at an absolute minimum, should be watched. It might even be best to start at "Week 9: Vector Math and Player Movement", tough to say.

Cheers,

Jeff

It sounds like you're on the right track. Have you read this? http://www.gamasutra.com/view/feature/131790/simple_intersection_tests_for_games.php

@JeffCarp:

Wow, thanks, nice find. Checked out a few videos today, but since I didn't watch all the previous videos it's kind of hard to just jump in and understand whats going on.

I'll try to watch more in the coming days. The video for Day 50 seems to be what has the most relevant information for my problem.

At the end of it it kind of seems to work, but who knows, I'm sure I'll find a problem with it ;) I am never satisfied...

One problem that I already see is that hes doing it all in one place, so the player kind of is the collison system and handler at the same time?

Maybe he seperates it and makes a more generalized collision system in a future episode, I don't know, I need to check out more of his videos.

@Glass_Knife:

Yep probably read it in the past, just skimmed over it right now because I don't need it, but thanks.

I'm already pretty happy with my collision detection code, detecting is not the problem, the only problem is, now that I know what collides with what, when and how, what do I do to prevent the collision and set the objects to their correct location and correct their velocities? And where should I do it? How should the "World" or collision system, that does all the moving and checking, interact with classes that actually "own" the bodies? I think I want the behaviour defined inside of the different entities/objects like player, enemy, bullet etc.

But how can they both work together? As explained in my original post, currently every body has a CollisionHandler assigned to it and when system detects a collision it calls the bodies CollisionHandler to pretty much tell the player or whatever "Hey you're going to collide, change your position and velocity yourself however you want to react to it". I'm not sure if it's a good idea to manipulate the pos/vel directly, would it be better to just return some kind of "desired position/velocity change" struct and have the world take care of actually updating the values?

One of my main problems right now is that solving ONE collision works perfectly but as soon as there are more than one collisions per timeframe, it doesn't work like I want it to.

Here is one example. The player is on the ground and starts walking left, his velocity is slightly downward because of gravity.

If I change the velocity after the first collision, It won't "slide into" the gap, because the Y velocity is now zero. He would end up on the other side of the gap instead of falling into the deathhole ;)

The excpected behaviour would be that he gets stuck on the edge and starts falling down next frame:

But THIS method has as a side effect that he will get stuck when walking:

So the problem is kind of with the ordering when handling multiple collisions in the same timestep and the needed correction of position and velocity.

I actually had a tile based system before, where in this case I could just easily check if there is an adjacent solid tile, if so, don't count the X collision.

But now I have a tile-free system where objects can be anywhere and any size and thats where this simple check doesn't work anymore.

Somehow I need to check for two cases basically, one: the gap is smaller than the player, then ignore the X collision and walk over it or two: the gap is big enough for the player to slide/fall into. But I need to do these checks only if the Y coordinates are exactly the same, otherwise he SHOULD always get stuck, if there is a little bump.

I'm thinking of maybe a ton of raycasting and conditional checking... Is there a better way?

Edit: A bit of info of how I detect collisions.

I basically just extend bounding box A by its velocity (swept), then do a check which other bodies intersect with that rect, those are the POSSIBLE collisions.

Then I divide the velocity by the distance to get the "time of impact":

toi < 0 collision happened before this frame.

0 < toi < 1 collision happening sometime this timestep (0.5 would mean halfway through movement)

1 < toi collision will happen in a future timestep

I get that for every axis, then I move the rect by velocity * toiX or toiY respectively and a little more to actually move it INTO the other rect and then check if it is intersecting.

If both are colliding, which toi is smaller (x or y) determines where the collision happens first.

So I can figure out for instance, that 33% (toiX = 0.33) into the movement, bodyA collides into bodyB from the right side, since vel.x is negative (moving left).

I think it would help if you realize this is a mathematics and geometry problem, and not really as much a computer science problem. If you can't think of a theoretical way to implement this kind of behavior that mathematically makes sense, then just trying random things out won't ever work.

On top of this you are trying to implement what is called a swept character controller. These are extremely difficult to implement, even in 2D. I suggest forgetting all about trying to fall into the gap with the character controller. This kind of task seems to be quite a way out of your ability to implement -- and that's okay! There are simpler and easier alternatives :)

In your case of falling down between a small gap while running very quickly, I would use a level editor technique. Use a level editor to place an invisible "marker tile" over the gap. Then you can run swept collision detection on the player against marker. If the player hits a marker you can have a piece of custom code to move the player downwards a little bit into the gap. This would be similar to marking areas of levels as "stairs" for the player to walk up and down.

Another alternative is to use very short sweeps. This way you calculate only a small portion of the players swept motion each iteration, and apply gravity/integrate forces many times each frame. This way the chances of the player catching some gravity while over the gap rises. In conjunction with this you can use a shape with rounded edges on entrances to corridors. This allows the player to more easily slide into gaps instead of just catching sharp box corners.

Hope this helps!

Have you considered using an existing API like Box2D to handle the physics and collision detection for you? If you've spent so much time struggling with the collision detection yourself without finding a solution, it's something you should seriously consider. If it's something you REALLY want to do yourself, well Box2D is open source so feel free to look at it's implementation to see how it's done.

@Randy Gaul:

That's definitely what it feels like I'm doing: trying to do something that's almost impossibly difficult.

Maybe I'll just have to design levels with big enough gaps and forget about falling into "1 tile" big gaps.

I'm still using tile based layout, but I'm not doing collisions in a grid or something because I want moving platforms and enemies and the player will move freely anyways, so why not just make everything be free of the restrictions that a tile based system would put in place.

@jHaskell:

Yes I tried it, but I don't like it. It just doesn't really work well if you want pixel precise movement and if there are many "tiles" beside each other, walking over them causes the player to hop over the "seams" between them. So in order to prevent that I would have to basically either add ghost vertices on every side for every body, or create some kind of chain shapes, or somehow merge multiple bodies whose sides are colinear into one big body. And that would really only work if they are the same type, with the same behaviour. So if one was some kind of ice-tile and the other maybe rubber, I would not really be able to make them into one body. Except if I make some kind of "split-body" type, which then defines regions inside of it, and check if the collision happened on the left half of it, it would react like ice, and if it happened on the right, like rubber. Those are just ugly workarounds/hacks.

Box2D really is more of a physics simulation library for more dynamic movements where pixel precision doesn't really matter.

This is from the official Box2D FAQ:

What are the biggest mistakes made by new users? 2. Expecting Box2D to give pixel perfect results.

And #2 is what I want :)

I don't want the character to sometimes stop 1 pixel in front of a wall, other times 2, or 0.

I want consistent behaviour. No jittering. Otherwise it just feels "cheap".

Right now after kind of randomly changing the code, I seem to be able to fall into gaps, but sometimes I just walk through walls, especially when objects are involved that should be not be collidable and just return false in HandleCollision(), returning false should mean "ignore this collision"...

Heres a little demo what it looks like: (the white things are supposed to be ladders, pass through, except when standing on the last rung of the ladder on top, like a platform).

Just detecting if a collision has or will take place isn't that difficult. Doing all the other things that are expected to fall under the umbrella of "collision detection" is another matter. You pretty much need to determine what results you want or find the results that you don't like and just work at it until you get the desired behavior.

I suspect that the way I'm doing things doesn't come close to best practices, and my current project is a top down RPG so my code has changed since working on a platformer but here's some of the stuff I've encountered.

I currently have my collision code in an actor class. The player, NPCs, other objects are derived from that class. For an actor I have two collision rects which I found was the solution that worked for me when doing a platform game. One for the body and one for the feet. The one for feet was what I checked against when dealing with gravity and the body one was for colliding with other objects, whether they're tiles or not. I can modify these rects to values I keep defined in the sub-classes depending on the actor's state if I need to.

For a given slice of processing a move, I know the starting position and the desired destination. I test for collisions for every pixel in between on the sides of the actors that are moving forwards vs the opposite sides of other actors. If a collision occurs, I stop movement and set the actor's location at the previously tested point and process whatever logic is appropriate for a collision between the two actors. Personally, I wanted that sliding effect so I made sure my code allows it to occur but I could probably modify speed or discontinue processing the code to make the actor stick when a collision occurs.

Recently I did some work to test for a collision some distance ahead of the actor in an attempt to implement some steering behavior stuff (which was the reason for a recent code rewrite). I don't test every point between the actor and the point ahead, just the one point. But I do move that point ahead further from the actor as he accelerates. When a collision is found, I alter the actor's trajectory a bit. It sort of works but I strongly suspect there's a lot more required to get it working like most demos that I've seen.

Before that rewrite, I was processing collisions for first horizontal and then vertical moves. I don't remember what I observed but I suspected that there might be some issue if the movement speed was faster than the width or height of the actor's collision rect and that there'd be an issue with doing collision testing this way for the steering behavior code. I don't know for certain if this is true but I ended up rewriting code to do the tests moving on the line between start and destination points instead.

I can't really think of much else without going through my notes in detail. In the end, if you're finding that you have a particular behavior you want or don't want that doesn't match what you're currently seeing, be prepared to spend the effort to get the desired implementation. It might feel like an endless task but this is the way it is when you code from scratch and you won't settle for anything less that a particular result.

(If anybody has a simpler way, I'm all ears. I'd also rather work on the other game logic than mess around with getting this right.)

Oh my god, my system is so extremely poorly designed... I have absolutely no idea how to do it right.

Right now I'm wondering how to transition into the "falling" state of the player.

Before I just checked if the velocity of the body is positive, if yes, change state to "falling".

But after realizing I cannot stand still on a ladder, because gravity is still pulling me down I had to rewrite the code a little bit.

Before, I added gravity to the players body in player::update(), AFTER doing the specific PlayerState::update() (like standing, walking, sliding etc).

This way, vel.y was always 0 inside of the substates, because collision resolution happened before.

But this way I cannot set vel.y to zero in "climbing" state, because right after that, gravity would be applied.

So I changed the order, now gravity gets applied FIRST, then PlayerClimbing::update() runs, which sets it back to zero.

But now in PlayerWalking::update() vel.y will ALWAYS be positive, because gravity got already applied, and therefore it transitions immediately into the falling state.

I have no idea what the correct order would be in a good system.

So instead I now have to actually check if the players body is "touching" any collidable bodies from above.

What a mess...

Just look at this:

void PlayerWalking::update()
{
//...
	RectEx footRect = player.GetBoundingBox();
	footRect.ResizeSides(0, -footRect.GetHeight()-1, 0, 0);
	footRect.MoveBy(0, 1.0f);
	auto tiles = player.level.GetTilesInRect(footRect);
        // I could also ask the world instead, and get generic bodies back instead of the actual tiles/platforms etc.
        // but then I would have to convert them to Tile* or something first.

	bool onFloor = false;
	for each (auto tile in tiles)
	{
		if (tile.second->IsSolid())
		{
			onFloor = true;
		}
	}
	if (!onFloor)
		player.ChangeState(player.states.falling);
//...
}

Is there a better way of keeping track when bodies come in conact and lose it again?

Thinking of it more like callbacks/events "OnContactBegin(...)" and "OnContactEnd(...)" instead of non-stop polling/checking.

I also have huge problems correlating bodies to their actual owners.

For instance if I check inside PlayerWalking::resolveCollision() against the body, how do I know what it actually is?

Is it a platform? An enemy? A bullet? All I have is a pointer to a body.

For now I did it kind of like the Box2D library where every body has a "void* userData" that can be assigned anything. So for now everytime I create a body I save a pointer to its owner in there.

But casting it back and checking then becomes a mess.

Should I give the body class a "GetType" function, which returns a value of an enum?

Something like:

enum BodyOwnerType
{
    TYPE_PLAYER,
    TYPE_PLATFORM,
    TYPE_GIANT_ROBOT_ENEMY,
    TYPE_SMALL_ROBOT_ENEMY,
    //...
};

player.body->SetType(TYPE_PLAYER); // so later I can do huge chunks of checking in PlayerWalking::resolveCollsion like this:
//...
// inside PlayerWalking::ReactToCollsion(Body* body, CollsionInfo info)
if (body->GetType() == TYPE_GIANT_ROBOT_ENEMY)
{

	GiantRobotEnemy* enemy = reinterpret_cast<GiantRobotEnemy*>(body->GetUserData());
	player.takeDamage(enemy.GetDamage());

}
else if (body->GetType() == TYPE_PLATFORM)
{
	Platform* platform = reinterpret_cast<Platform*>(body->GetUserData());
	if (platform.IsSolid())
		vel.y = 0;
}
//...

Are there any good tutorials on how to actually design a GOOD "system" or whatever its called? Software engineering for 2d platforming games?

I just don't think I can come up with something good on my own. My own design feels like a way too complicated rube goldberg machine that does something that should be relatively simple, way too complicated and indirectly.

Or is it not possible to do it any better? Should I stick with this or try to make it better?

Edit: I just realized the video was demonstrating your code? Confusing! I thought it was from some real megaman game on an emulator. It looks like you're having a lot of trouble with floating point error and its implications. Perhaps using tiles will make a lot more sense for your game.

From a tile based perspective it's pretty easy to tweak the system to make sure you fall down into gaps. For moving platforms you can use special case code, and they don't need to be apart of the static tiles. There's no need to make a "generic collision system" that handles all things in a single way! Similar to how you wanted to handle all collisions with the player with a swept character controller -- don't! These generalizations are unnecessary. Write special case code for the specific features of your game.

Since you're asking about code design I suggest looking at Dirk Gregorius's 2015 slides on creating contacts. He talks about using a collision matrix (2d array of function pointers) to dispatch collisions, and like your idea he is just using an enumeration to specify types. You can use an interface to query the type enum from a collider. Then you can use the integral enum on switch statements, or Min( a, b ) comparisons, etc.

For tracking when things come into contact and fall out of contact, you need a piece of memory to represent this "state". The "state" is usually called a contact, or an arbiter, in physics engine lingo (sadly many things are called contacts). When a contact is created and it's state is set to true, the two associated shapes are touching. Once they stop colliding, the state can be set to false, and at some point you can remove the contact. Usually gameplay cares a lot about the moments the state is set to true and false. You can store whatever other useful information about the two touching shapes you need (like the normal of the surface they are touching that represents the axis of minimum penetration, by how far they are penetrating, etc).

A good example of this contact is called an Arbiter in Box2D *Lite* (not the full version, just the Lite version). In Box2D Lite Arbiters are just stored in a std::map and the key is the id of the two associated colliders, iirc. It's a pretty simple and good educational example, but might be overkill for what you need; in the Megaman game this kind of memory usage was not used. Instead state was likely stored with the player, and only a few select enemies that actually needed to interact with tiles.