Back to General and Gameplay Programming

2D AABB Collision resolution and collision system/class design

Noneofyour Business · 2015-04-01T10:08:35

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.