next »

[Aloshi]

I've been working on a tile-based platformer in C++, and collision response has been the worst part so far. I believe the particular problem I'm trying to solve is very common, but I haven't found a good solution.



What happens is, occasionally the player will collide against the vertical edge of a tile and be pushed left/right instead of up (sort of like he stubbed his toe).

The logical solution to this would be to just not check these hidden edges. So I set up a system for detecting them:



The problem I now have is integrating this ignore system with my SAT-based collision detection algorithm.

So my question is really this: how do I ignore an edge in an SAT-based collision test? Do I skip projecting on that axis (I assume for both shapes I'm testing the axes of)?

[ThemsAllTook]

I talk about this a little bit in my collision tutorial (see "Surface Area and the Crack Problem"): http://sacredsoftware.net/tutorials/Collisions/CollisionsPart1.html

Basically, my approach to this is to sort potential collisions based on some measurement that prioritizes the tile you're standing on higher than the one you've just stubbed your toe trying to step onto. The example in the tutorial does it by surface area, but there are other ways that would also work. As long as you resolve the closer collision first, the farther one shouldn't snag you on a corner.

[sublinimal]

Move vertically first, check collision & correct vertically, then move horizontally & correct horizontally.

[ThemsAllTook]

Move vertically first, check collision & correct vertically, then move horizontally & correct horizontally.

That seems likely to cause false positives when you're moving diagonally near the outer corners of blocks. Your path of motion each frame would essentially become L-shaped instead of being a straight line. Whether or not this is a problem would depend on how fast objects can move in one frame, but it's something to be aware of.

[sublinimal]

Move vertically first, check collision & correct vertically, then move horizontally & correct horizontally.

That seems likely to cause false positives when you're moving diagonally near the outer corners of blocks.

That's more of a feature than a bug: it gives you a slight protection from slipping off those pesky cliffs.

[Belimoth]

My approach is to use the regular "pushing"-type collision response for entity-entity collisions, and use "look-ahead" collision response for entity-level. I cover the basic idea here.

Pros:

• you don't ever have to deal with hidden edges
• things like one-way platforms are easy to code in
• easy to cache results for faster checking
• easy to check if an entity is touching level geometry on a given side

Cons:

• collision events have to be generated in a slightly different way
• hard to extend to things other than rectangles
• slope response for things with ground speed (side-view platformers) is much harder to code in
• becomes complicated when more complex tile shapes are used

[Aloshi]

I should mention I plan to use sloped tiles in the future.

[ChevyRay]

Move vertically first, check collision & correct vertically, then move horizontally & correct horizontally.

That seems likely to cause false positives when you're moving diagonally near the outer corners of blocks.

That's more of a feature than a bug: it gives you a slight protection from slipping off those pesky cliffs.

Yeah for pixelly-like games like this, I tend to consider this a good thing as well.

But when you want to integrate things more smoothly, this system kind of falls apart.

[Aloshi]

I figured out why my method of skipping edge collision checking wasn't working (I had my normals flipped and didn't notice until now). Fixing that, I was running into troubles with collision order, so ultimately...

Basically, my approach to this is to sort potential collisions based on some measurement that prioritizes the tile you're standing on higher than the one you've just stubbed your toe trying to step onto.

I ended up doing this by sorting by tile distance. I'm not sure of the cons of doing it this way as opposed to surface area, but it seems to work. Hopefully it doesn't fall apart when I add slopes.

[ThemsAllTook]

I figured out why my method of skipping edge collision checking wasn't working (I had my normals flipped and didn't notice until now). Fixing that, I was running into troubles with collision order, so ultimately...

Basically, my approach to this is to sort potential collisions based on some measurement that prioritizes the tile you're standing on higher than the one you've just stubbed your toe trying to step onto.

I ended up doing this by sorting by tile distance. I'm not sure of the cons of doing it this way as opposed to surface area, but it seems to work. Hopefully it doesn't fall apart when I add slopes.

Heh, to be honest, I can't remember why I chose surface area either. I know I used tile distance in a previous game. I think it might have been because I was writing something with differently-sized tiles, and if I did it by measuring the distance between the center of the tile and the center of the player, smaller tiles would be prioritized higher than larger ones (because their centers are closer to their surfaces). If all of your tiles are the same size, doing it by distance should work great.

[vittorioromeo]

I have another problem related to AABB collision detection/resolution. I fixed the "stubbed toe" problem by sorting by surface area overlap. But, there is another annoyance...

In my simple collision engine, I resolve collisions between AABB bodies by finding the shortest intersection vector, and adding that to the position of the AABB body. This works almost perfectly, unless the body gets stuck between two other static bodies.

The gap between the static bodies isn't big enough to contain the dynamic body:

on frame A, the dynamic body will be pushed to the right, overlapping the second static body
on frame B, the dynamic body will be pushed to the left, overlapping the first static body
The loop continues infinitely. Is there any way I can solve this without rethinking the whole design of the collision engine?

The entire source code is available here, written in C++11. It should be easy to understand.

https://github.com/SuperV1234/SSVSCollision

(some pics, taken from here http://gamedev.stackexchange.com/questions/15836/collision-resolution-in-case-of-collision-with-multiple-objects)

frame a


frame b

[nickgravelyn]

Discord Games (guys making Chasm) have a good post on their collision that sounds like a good approach: http://discordgames.com/?p=2221. Essentially it boils down to not treating the player as a box, but instead just sampling small points or line segments in specific ways.

[Belimoth]

The sensor-based approach, which is what I believe they are describing there, is good but doesn't really deal with tunneling.

Here's another, older, article about it: http://games.greggman.com/game/programming_m_c__kids/

Also, the typical thing to do with slopes is to move the player vertically when their "feet" sensor is triggered. Not moving in the direction of the slope normal means your x velocity isn't affected at all. Just something to be aware of.

[bateleur]

In my simple collision engine, I resolve collisions between AABB bodies by finding the shortest intersection vector, and adding that to the position of the AABB body. This works almost perfectly, unless the body gets stuck between two other static bodies.

If you want to handle this kind of thing perfectly, you need to write your whole collision system to be correctness-preserving. This is a MASSIVE complexity increase over what you're doing at the moment. Basically, every time something is about to move you need to compute all the consequences of that move (potentially involving all sorts of objects pushing each other in various directions) and then work out how much of the original move is possible (maybe none at all). With this kind of system, the situation above cannot arise in the first place.

A reasonable compromise solution, which is easier to write, is to use a multi-pass system. So in your example above, instead of pushing the block all the way outside the lefthand scenery, you push it by only one pixel. Then, in the same frame, you run collision tests again and so on, maybe 10 times or so. When pushes happen from both sides at once, average them and round down.

[motorherp]

The problem I now have is integrating this ignore system with my SAT-based collision detection algorithm.

So my question is really this: how do I ignore an edge in an SAT-based collision test? Do I skip projecting on that axis (I assume for both shapes I'm testing the axes of)?

Sorry if I'm a bit late to the party.  Your idea is correct in that eliminating hidden edges is the most robust way for you to prevent issues with unwanted collisions.  These edges however can still form a seperating axis when using SAT and hence simply ignoring that axis wont work since it will lead to the algorithm reporting false positives.  In my experience, the most solid and realiable method you can use to resolve these issues is to replace your collision detection with a series of 'swept AABB to line segment' tests (where the swept AABB is from your sprites last position to your sprites desired new position).  Simply repeat this test for every exposed edge in range of the moving object and keep track of the earliest time of collision reported.  When done, simply move your object from its previous position in the direction of its desired position but only by an amount according to the earliest collision time reported.  This will bring your object perfectly into contact with your terrain whilst avoiding unwanted edges and without resulting in any unwanted penetrations or tunnelling.

In my simple collision engine, I resolve collisions between AABB bodies by finding the shortest intersection vector, and adding that to the position of the AABB body. This works almost perfectly, unless the body gets stuck between two other static bodies.

The gap between the static bodies isn't big enough to contain the dynamic body:

There's no correct way to resolve the issue you describe once you're in it.  You'd require some kind of teleport fudge to fix the situation, the nature of which would be dependant on your game.  The real trick is to have a collision system which never lets you get into those situations in the first place.  The collision system like I just described above would do the job.

[Aloshi]

In my experience, the most solid and realiable method you can use to resolve these issues is to replace your collision detection with a series of 'swept AABB to line segment' tests (where the swept AABB is from your sprites last position to your sprites desired new position).

I actually would really like to do this (this is my second project dealing with collision) but I hadn't been able to find a very good tutorial anywhere. I guess I'll keep looking.

EDIT: I actually think I've gotten swept collision detection working, but collision response is much harder...

[Aloshi]

I ended up trying to implement swept SAT-based collision by following this tutorial. Collision detection works (it finds the time of intersect), but the document doesn't explain much about how to do collision response.

The problem I'm having is that if a collision is found, the player basically 'sticks' to the surface, because my simple collision response code for the static collision test doesn't work anymore. The logical thing is to set the player's new position to the point at the time of entry - but because of gravity, if the player is on the ground, the time of entry is almost always about 0 - so the player can't move.

I'm not sure how to resolve this. Testing each axis individually seems like it wouldn't work once I add slopes. Some math to change the Actor's velocity and re-testing seems like the best way, but I don't know how to go about doing that (something to take into account the collision normal, so you can walk up slopes).

It's been really hard to find good information on swept SAT tests.

If anyone wants to look at my code, CollisionShape.cpp and Actor.cpp (Actor.cpp still uses the old collision method).

[ThemsAllTook]

Some math to change the Actor's velocity and re-testing seems like the best way, but I don't know how to go about doing that (something to take into account the collision normal, so you can walk up slopes).

That's what I do. Once I've found the time of intersection, I subdivide the timeslice I'm testing against, update the object's velocity, and iterate again with the new value. In the case of gravity, you'd get one very early intersection, have the downward velocity canceled out in an early part of the timeslice by the collision response, then run the rest of the timeslice with whatever horizontal motion is left over.

Taking into account the collision normal for walking up slopes is another matter. The simple approach would be to reflect the object's velocity against the slope's normal, but that would have a negative effect on gameplay if you don't want slopes to be too hard to climb. You'll probably have to fudge it a bit. I tried a system once where slopes had a separate "collision normal" which wasn't orthogonal to its surface, but never got it 100% working...

[vittorioromeo]

Going back to the original topic, today I made a video tutorial on the "stubbed toe" problem, and on two possible fixes (both the fixes work with any direction of gravity, and are not limited to tile-based games).

It's my first time doing a video tutorial and I was wondering if the explanation was clear enough, and what could be improved. (I'm already aware of the horrible blue marker, I'll buy a new one tomorrow)

[CharsAce]

http://www.metanetsoftware.com/technique/tutorialB.html
The style I use. Every side of a tile can be set to inner-edge or not inner-edge. I keep a list of minimum translation vectors that I get from checking for collisions against the tilemap. I sum the list to get the total mtv and add that to the dynamic object's position. I limit the speed of dynamic objects to avoid tunneling.