next »

[Quarry]

Here's a small world and a rectangle (red) just standing around still.



It wants to move left (orange), and there's some gravity that's pulling him down.



If he didn't collide with anything, he would be at the same position as the purple rectangle. Yet by the laws of physics, he should collide with the world.



What I'm doing here at this point is checking for collisions with the tiles and responding to them per-axis. The shortest time taken for the collisions is taken into account and applied to the player's position in the next frame. The green-dotted rectangle is the predicted position.



It works as intended for the case demonstrated, as the player only collides with the top of the two tiles he was standing on, it takes equal time to reach to both of them on the Y-axis and therefore his position is resolved accurately. There is no collision on the X-axis so everything is fine and dandy.



The problem occurs when the player must collide with two axes at the same time. As you can see on the diagram he's one pixel into the next tile's right side. He is obviously pushed back by the code for both the Y-axis (which is practically indifferent to the case before) and the X-axis. The green-dotted rectangle in this case is incorrect, as the desirable case is demonstrated below:



Instead of being able to move to one pixel to the left to have its left bound as the pink line, it's positioned incorrectly and "stuck" on that specific position.

Is there any way to combat this phenomenon? How can I make sure that the collision code realises that the player should not be stuck there and be able to move on on the X-axis?

Here's the code for the swept AABB response http://pastebin.com/tGMeSFzM

...and the one checking against all boxes http://pastebin.com/hgLD4rgf, as you see I take the shortest time for each axis and move accordingly, which works perfectly if the AABBs are not aligned. However in a tile based world they are and this results in the sticking glitch I mentioned.

[Quarry]

Appending this GIF to demonstrate the issues that are resulted from this. It's not so visible while I'm moving horizontally, but you can easily see that I can cling to the wall and even trick the code that I'm actually on the ground when I hold the left key and space at the same time.

[Sik]

I just process the two axes separately (rather than shifting both and then checking both), which really works just fine for stuff like this. You still have to be careful about slopes though (mostly because they follow completely different rules, e.g. you don't want horizontal motion to stop because you collide with a slope).

[bdsowers]

Does your game have a concept of friction? I've seen similar 'wall cling' situations happen when trying to physically simulate friction while applying forces against a wall. Not necessarily a problem with the geometry.

Afraid it's been over 5 years since I've mucked with AABB stuff, so I can't be too much more helpful. 

[RandyGaul]

You should try computing a TOI with the actual AABBs like you are doing. However when you resolve the collision, dilate the AABB slightly so your penetration depth is just a little bit larger.

The idea here is to keep your player AABB floating just a little bit above the ground this way you don't catch any edges.

Alternatively you can use a grid which doesn't have any of these issues at all. You can also weld the AABBs together so you don't have any edges to catch in the first place, so you don't need a grid.

[ThemsAllTook]

This is an annoying problem. I've solved it a variety of ways in the past, and never been entirely happy with any of them. What I usually do is some sort of sorting of potential collisions, process the ones that happen earlier first, and re-run detection with a readjusted trajectory. If two intersections happen at the same time, I prioritize by surface area between character and tile at the time of collision.

[Quarry]

I just process the two axes separately (rather than shifting both and then checking both), which really works just fine for stuff like this. You still have to be careful about slopes though (mostly because they follow completely different rules, e.g. you don't want horizontal motion to stop because you collide with a slope).

In that case what will happen is:



The first axis check on is say Y, in that case the player will be located at the red rectangle, and when I check X afterwards it'll be in green while after all it should be in pinkypurple. It unfortunately doesn't work as I intend it to.


Thanks for the suggestions guys, will try and jam something up based on what y'all said.

[Photon]

This is something I might be dealing with soon. Here's what came to mind for me:

Order your collisions based on the intersection area of the different collisions, going largest to smallest. As you knock out different collision shapes, recalculate intersections and knock out the next one. Not sure how intensive on performance this might be, but I get the sense that physics calculation typically aren't cheap anyhow.

If you have really thin objects where part of the actor might pass through the other side, try to account for this extra area by getting the intersection then expanding the width/height of it to the actor's side that passed through (for instance, if the actor was moving down through a thin plank because of gravity, get the intersection area then expand the area's height to reach down to the actor's bottom side.) Not sure this is necessary though unless things are moving really fast, and again for thicker objects it may not be an issue at all.

When I get to this in my current development, I can potentially post my results.

[tjcbs]

What about ignoring collisions on interior edges? So, in your example above, the two colliding blocks with the "!" would not collide in the x axis at all, since their vertical edges are bounded by other blocks. Whereas, the block to the right of the "!" would only collide with leftward x motion, since only it's right vertical edge is exposed.

[ThemsAllTook]

What about ignoring collisions on interior edges? So, in your example above, the two colliding blocks with the "!" would not collide in the x axis at all, since their vertical edges are bounded by other blocks. Whereas, the block to the right of the "!" would only collide with leftward x motion, since only it's right vertical edge is exposed.

Ooh, good idea! Now I feel dumb for not thinking of it. I can think of a few degenerate cases for differently sized or non-grid-aligned blocks, but that seems like it would work perfectly for simple tile-based levels.

[Quarry]

I did try doing that (or at least I think I did) by doing two additional checks for the blocks that are actually collided with. The Y colliding box's index is stored in say yBox, and the X colliding box's index in xBox.

What I did afterwards is that as I normally do:

Code:

var newXResolution = resolveCollisionX(player, boxes[i], dX, dY);
var newYResolution = resolveCollisionY(player, boxes[i], dX, dY);

I just added two ifs after the loop saying like:

Code:

if (yResolution < 1) { // Has it collided with the Y axis?
  xResolution = resolveCollisionX(player, boxes[i], dX, dY * yResolution); // Then I should try moving with the Y axis collision
}

The problem here is probably that I'm missing some additional check that makes stuff still go through certain walls it's not checking through or something. I believe this may be a start but it's working so good right now.

In the meantime, here's the full code. Slap .html at the end of it and left-right-space bar to check around (this is with the proposed fix so that you can try and debug it if you would like to) http://pastebin.com/tH6P0i4K

[RandyGaul]

You really should just go with my original suggestion and save yourself some time and use a floating epsilon. All other solutions either won't work in all cases, or you'll need an alternative that takes a lot more work (like geometry welding, adjacency information, re-write with a grid).

[Quarry]

I have managed to fix it, I did exactly what I mentioned but instead of running it only against the old box I just run it against the other boxes. This allows me to get rid of the cases where I don't push against the check boxes but another box and I can go through it. Now I basically do it in two runs and get the higher value, here's the code:

Code:

var xResolution = 1, yResolution = 1;

for (var i = 1; i < boxes.length; i++) {
  var newXResolution = resolveCollisionX(player, boxes[i], dX, dY);
  var newYResolution = resolveCollisionY(player, boxes[i], dX, dY);

  xResolution = Math.min(xResolution, newXResolution);
  yResolution = Math.min(yResolution, newYResolution);
}

var xResolution2 = 1, yResolution2 = 1;

for (var i = 1; i < boxes.length; i++) {
  var newXResolution = resolveCollisionX(player, boxes[i], dX, dY * yResolution);
  var newYResolution = resolveCollisionY(player, boxes[i], dX * xResolution, dY);

  xResolution2 = Math.min(xResolution2, newXResolution);
  yResolution2 = Math.min(yResolution2, newYResolution);
}

Don't mention that I'm running this against all boxes, it's just laziness

EDIT: I can't really think of any reasons to run the simulation more than twice for my use case, it works perfectly right now

[Quarry]

A minor amendment to the old code, I realised that sometimes both axes may be found to be able to go through so a very little check for that can eliminate bugs:

Code:

if (xResolution > yResolution) { // Can be rewritten as yResolution == 0 for most cases but just to be safe
  xResolution = Math.max(xResolution, xResolution2);
} else {
  yResolution = Math.max(yResolution, yResolution2);
}

I hope this thread manages to help future generations deal with AABB collision prediction and resolution, I am very happy with the results and I'm sure someone else out there will too

[vittorioromeo]

Sorry for the bump, but this is a problem I've tried to solve a long time ago, and came up with a pretty "stable" solution that works with moving platforms any gravity in any direction.

Basically, as you can see in my collision/game-physics library here...

https://github.com/SuperV1234/SSVSCollision/blob/master/include/SSVSCollision/Resolver/Retro.hpp

...after the broadphase, I sort every possible colliding body by the "overlap area" with the player.
Then, by doing some calculations on the player's velocity and position in the previous frame, everything seems to work properly.

I've made a video about the issue a long time ago here:



---

I'm really curious to know if your solution works with moving platforms (for example, a platform rising from the floor by constantly decreasing its Y coordinate every frame) or for gravity that can change (horizontal gravity, for example), as it looks simpler than my own.

[Quarry]

Gravity change, yes. Moving platforms, no. With very simple changes to the function it can support both slopes and moving platforms though (in theory). I'm leaving those problems for you to solve as I'm pretty busy nowadays and my currents projects don't necessarily need either one of those solutions right now.


Also, as a comment on your video has mentioned "There's a problem with the first method that if you're moving right fast enough you can still get stuck in the "crack"." while this solution works in speeds up to positive and down to negative infinity

[vittorioromeo]

I'd really like to experiment with your code, implementing moving platforms and possibly slopes.

I'm having a little trouble understanding what "bugged" parts to replace in your original full html file - sorry to bother you again, but could you please post the complete html+js code for the fully-working version?

Thanks.

[Quarry]

http://pastebin.com/JUwNHLaC

Everything's in loop. It also demonstrates non-vertical gravity