   Set me straight on platformer collision detection
  WARNING:  The following post is as long as a book.  It is me describing my (failed) attempt at implementing platformer collision detection/physics and me asking various questions I have about the subject.Platformers are my favorite genre yet I have always had the hardest time programming them.  Ive read countless articles on the theory behind the collision detection and handling and even looked through games source code.  But my implementations are always slightly off and have weird bugs.  Im also always so unsure of everything and I just want to get it FLAWLESS, though I know the implementation really depends on the game, im sure im doing many things wrong and im sure there is a pretty good method of doing everything that would work for most games.Lets start.  Basically in any platformer, you need to beable to detect which side of the player is hitting which side of what object.  I do this by checking if the players right edge's x value is greater than the objects left edge's x and also check if the players left edge's x value is less than the objects right edge's x.  If both of those are true, then the player and object are intersecting on the x axis.  I then do the same logic for the y axis.This is where things become unclear for me.  Once we know a hit test has occured, we need to know which edge of the player and which edge of the object are being hit.  What I have been trying out in my latest fail-fest is, figuring out which corner of the object the player is closest to.  So lets say the player is closest to the bottom left corner of the object and we then assume the players top right corner is the one making the contact.  Then I find the difference between the players top right side's x and y and the objects bottom left side's x and y.  This gives me the difference in x and the difference in y (and I make sure to take the absolute value of the two).  I check which is lesser, the difference in x or the difference in y, which ever is least then that means that is the axis that is being hit.  So if the difference in x is smaller then that means that player just hit the side of the object.Now time for questions.  Is finding the difference in x and y the correct way of doing things??  It gets loopy if I put two platforms side by side and the player tries to walk across them.  He gets stuck in the middle of the two because it thinks he is hitting the side.  Other than that, the whole figuring out what sides are making contact works like a charm.When do I apply forces such as the result from the players input and gravity?  I have it apply them first then check for the collisions using the players FUTURE position, deal with the collision, then actually move the player to its correct future position.  Is that correct?Im constantly applying gravity, even when I have registered that the player is on a platform.  I do this because if I dont, my collision handler will move the player just above the platform, out of contact, yet say it is on the ground, so that if the player runs of the edge, gravity never takes effect.  Im guessing I am handling this incorrectly.Many of my problems come from platforms being close together and the player touching them both, like I referenced earlier, if part of the player steps on a platform, then the other part of the player is still on an adjacent platform, sometimes it works fine, sometimes it doesnt let him move horizontally.  If you jump up though and fall straight down, you fall through both platforms because its registering as the sides :(Moving platform problem.  Im not too worried about these, but after looking at my code, I dont get why its not constantly setting the player on TOP of a vertically moving platform.  Instead half the time the player gets stuck then falls through.  Ideas?IN CONCLUSION, I hope someone can go through and just tell me how stupid I am and correct me on everything, perhaps give me pseudo code of when I should be doing each step and how to handle states such as when the player is on a platform and such.  I would greatly appreciate it.Thanks!LINK: The Flash PrototypeUse arrow keys to move and jump.EDIT:  Added a link to a SWF of a prototype of my attempt at this.  The same problems persist that I asked about.  Also,  you can see the player sometimes bounces while other times he perfectly lands and other times he is a few pixels above the platform.  Not sure what is causing that exactly.   
  It actually reminds me of when square objects clip the edges of other square objects in Box2D. The only way around it is to either round out the corners so it moves over smoothly, or have another box inside that's a little bit smaller, which, upon colliding with platforms, moves it, and the larger box it's within, to the resting position of the bigger box (if that makes sense). Basically the bigger box doesn't actually collide, but acts as a reference point to where the box should be sitting.   ;  There is such a wildly easier and more reliable system then what you've outlined. It's simple:Do a test move of the object based on it's velocity. If it collides in that position, then move it pixel by pixel from it's initial location, checking if it collides each time. Once you see that it collides, then stop moving it. Done.The only problem with this is if the velocity is great enough to move entirely past an object on one swoop. The solution is to simply check the collision every pixel, no matter if there is a final collision or not. This is what I do, and the routine to check for a collision is very small and inline, so it's plenty fast.   ;  cclyde is half right there about incrementing the object forwards until you find where the collision occurred however a better solution would be to do a binary search to find the point of the collision down to a resolution.Basically you take the point you started from and the point you finished at and do a LERP between these points to find the center point. This is you new object position for the test. Then test to see if this position is intersecting with the platform. If it is intersecting do the same test but use the start point as the next tests start point and the new end point is your LERPed value. If it is not intersecting then use the LERPed value as the new starting point and the end point as the end point. You repeat this process down to some set resolution (I've usaully gone 6-8 as an maximum). From reading that I'm not sure how clearly I explained it so I think I should show you some code. Bear in mind this is designed to be a recursive test so it is going to be a little odd.class Rectangle{Vector3 position;float width, height;};const unsigned int MAX_BINARY_SEARCH_RESOLUTION = 8;void RecursiveCollisionResolution(const Vector3 &entityPrev, // The previous position of the entity.Rectangle entityBounds,   // The entities bounds where it was colliding.Vector3 &entityFinalPosOut,   // Our output position when we have resolved the position to the said resolution.Rectangle platform,   // The platform / other rectangle we are testing against.unsigned int currentStepResolution,  // The current resolution of our recursive function. This is always 1 when you first call it.unsigned int maxStepResolution) // The resolution we want to resolve to.{// Check to see if we have tested up to the specified resolution.if (currentStepResolution >= maxStepResolution || currentStepResolution >= MAX_BINARY_SEARCH_RESOLUTION){// When the collision is resolved always use the previous position(s) as the outputs other wise you will notice// that your entity will 'slide' down. Its an interesting look (and a frustrating bug).entityFinalPosOut = entityPrev;// Terminate the recursion as we have resolved the collision to the specified / exceeded the max resolution.return;}// The position where the entity was collidingconst Vector3 entityFinal = entityBounds.position;// Do a linear interpelation between the last position and the current position we know is colliding.const Vector3 entityHalf = LERP(entityFinal, entityPrev, 0.5f);// Update the entity bounds to the new position.entityBounds.position = entityHalf;// If the new position intersects with the platform then we know the collision occured slightly backwards in time.if (Intersects(entityBounds, platform)){// Shift backwards.RecursiveCollisionResolution(entityPrev, // TheentityBounds,entityFinalPosOut,platform,currentStepResolution + 1, // Update our step resolution, if you dont do this it will break your program.maxStepResolution);}else{// We know that the collision must have be further forward than the halfway point in time other wise it should// be colliding. So we shift forward by using the centre position as our starting position and the final position// as our ending position.entityBounds.position = entityFinal;RecursiveCollisionResolution(entityHalf, // TheentityBounds,entityFinalPosOut,platform,currentStepResolution + 1, // Update our step resolution, if you dont do this it will break your program.maxStepResolution);}}I hope that makes sense. Its an odd thing to get your head around at first (or at least it was for me) but it works well. I am sure there are better was to do it like some crazy maths equation but that is a cleanish solution.[EDIT] Sorry about the exploded code...   ;  That is not a better solution, it is an unnecessarily complicated solution that introduces possible errors into a bullet-proof system. The problem with your system seems to be this:You are moving around the test box in a binary search. Each time, the test of collision comes back either positive or negative. Neither one tells you if the test box is flush with the edge of a solid object. Being flush looks exactly the same as being a mile away from. Now, you're right back in the OP's post, trying to extricate objects from tiles. Either that or using some workaround that throws away whatever amount of time you saved not just checking it in a linear way.In my system, if that last move had no collision, and this move has collision, then clearly you are flush with the tile. Platformers need to be 100% solid in their collision detection, and in a tile based system nothing but the most straightforward and simple system will suffice.   ;  I disagree cclyde, if you are moving an object forward on a pixel by pixel basis you are running many more checks than are necessary to find the collision location.For instance, say we know the collision happened within a 256 pixel span between frames. In a test where you slide the object forward 1 pixel you will do 0 - 256 tests to find out where the collision occurred. In a binary search (for this test case at least) you can find the exact collision position in absolutely no more than 8 collision tests.Just a note about my previous post, the binary search assumes a collision has already occurred and you are attempting to resolve it. However, it is complicated so you are probably better to go with cclydes solution. My post was aimed to be a faster way to resolve the collision once you know it has occurred.   ;  I have already implemented your approach Mr Robbins, thank you guys for the replies.I havnt had time to fool with it much, but in the one or two tests that I have done with it, it has worked perfectly.  It looks smooth as well.  I changed the number of resolutions to 5 and I could see gaps, changed it to 6 and it worked, but I will just use your recommended 8 iterations as that seems to never have a problem.  I will play with it more tonight/tomorrow and let you know how it goes!Thanks!   ;  What i do check if in the current frame there is no collision,and then check if in the next frame there will be collision. if there will be,i check how deep the player is within the platform,calculate a T value for each axis by dividing the length for that axis with the velocity of that axis. then i take the smallest T of them all,and move the player -velocity * smallest t for all axis. this puts the player in the right spot. it does seem to have some problems though with moving platforms.my code(a bit ugly,sorry) :std::pair<bool,Vector3> Platform::CheckCollision(AxisAlignedBox* playerWorldBox,AxisAlignedBox* playerBox,Vector3 playerPosition,Vector3 velocity){if(this->path.path.size()) {Vector3 position = this->node->getPosition();this->path.Move(&position);this->node->setPosition(position);}AxisAlignedBox boxer = this->GetWorldBox();if(!boxer.intersects(*playerWorldBox)){//set the copy bounding box of the player to match next frameplayerWorldBox->setMaximum(playerWorldBox->getMaximum()+velocity);playerWorldBox->setMinimum(playerWorldBox->getMinimum()+velocity);if(boxer.intersects(*playerWorldBox)){//collision occured. let's move the player to the collision point//we do that by using the equation position = -velocity * tVector3 playerCenter = playerPosition-velocity;Vector3 boxCenter    = box.getCenter();float   distanceX    = boxCenter.x - playerCenter.x,    distanceY    = boxCenter.y - playerCenter.y,distanceZ    = boxCenter.z - playerCenter.z;float   t1  = (velocity.x != 0 ? distanceX / velocity.x : 99999),   t2  = (velocity.y != 0 ? distanceY / velocity.y : 99999),t3  = (velocity.z != 0 ? distanceZ / velocity.z : 99999),tf  = 0;//check which t is the smallestif(t1 < t2) tf = t1;if(t3 < t1)tf = t3;if(t2 < t1) tf = t2;//set new positionif(velocity.x > 0)playerCenter.x -= -velocity.x * tf;elseplayerCenter.x += -velocity.x * tf;if(velocity.y > 0)playerCenter.y -= -velocity.y * tf;elseplayerCenter.y += -velocity.y * tf;if(velocity.z > 0)playerCenter.z -= -velocity.z * tf;elseplayerCenter.z += -velocity.z * tf;playerWorldBox->setMaximum(playerWorldBox->getMaximum()-velocity);playerWorldBox->setMinimum(playerWorldBox->getMinimum()-velocity);return std::pair<bool,Vector3>(true,Vector3::ZERO);}playerWorldBox->setMaximum(playerWorldBox->getMaximum()-velocity);playerWorldBox->setMinimum(playerWorldBox->getMinimum()-velocity);}return std::pair<bool,Vector3>(false,Vector3::ZERO);}