Sliding AABB collision - getting stuck on edges

A:

From your diagram, it seems you want the smallest move that minimises the overlap between the player and the cubes. Each cube with overlap will try to "push" the player in two orthogonal directions. Can you do something like pick the minimum push of the maximum pushes in each direction?

Rafe 2010-10-11 00:33:01

I think that would cause issues if the player was walking into a corner. In that case, I need to push the player backwards along 2 axis.

Jeff 2010-10-11 02:29:46

Okay; thinking in 2D, the push must have a vertical and horizontal component. Each overlapping cube can impart a push in two directions from {N, S, E, W}. If there are multiple overlapping cubes, then you need to consider the maximum pushes in the {N, S} and {E, W} directions (anything less will leave overlap, but it may be possible to ignore, say, a NS push because an EW push will do the job). There are at most eight possibilities. Can you try all eight in order of magnitude and pick the first that clears the player from the cubes?

Rafe 2010-10-11 03:33:40

Unfortunately, there would be even more possible sets in 3 dimensions. It would probably be more efficient to just initially sort the blocks based on distance as Tom suggested.

Jeff 2010-10-11 04:30:35

Well, there are at most 26 possibilities for 3D and the only way you'd have to consider all of them is if somehow every face of the player cube intersects with a game cube.

Rafe 2010-10-11 04:51:37

+2 A:

A discrete implementation forces you to inject some continuous math in the system, only when required (cubes / directions overlap).

For each cube c1, c2 ... ci with which the user cube (uc) intersects at the time of the check, you want to find out which cube was "touched" first - there is only one, as in real life. Consider the direction d of uc, and, taking the amount of uc in ci (overlapping) find the position of cu at the time it "touched" ci.

Determine which cube was "touched" first cj (the one that required the most rollback on the d axis - the sooner in time) and use only this one to calculate the collision reaction.

Not only you'll reach accuracy. but it will help if all cubes are moving, have different speeds etc...

ring0 2010-10-11 01:33:16

+1. I did something like this once, though it's a pain to implement and debug. You can run into trouble using this approach when the motion of objects from one frame to the next isn't along a linear line, but otherwise it works really well. You'll need to remember the previous position (and maybe previous velocity) of each object that can move so that you can calculate the position and velocity of the objects at any given time between two frames.

Cameron 2010-10-11 02:33:57

I'm having a little trouble understanding what you are saying, but I think this answer would also have an issue if the player was trying to walk into a corner of a room. I believe it would be necessary to take more than one block into account. I could perhaps sort all the blocks that the player is colliding with, but I'm not sure if it would be best to avoid having to sort things.

Jeff 2010-10-11 02:45:00

The wall of the room is to be treated the same way as other cubes - this is a particular (easier) case: you check if the cube is out of the bounds, and, using the same algorithm, determine how much of the cube is out, then you check collisions with other cubes. Again, the first "touched" (another cube or the wall) has to be dealt with collision reaction. Wall is just a particular non-moving and bigger object with which the cube may collide.

ring0 2010-10-11 02:50:01

I'm saying that if the player walked into the corner, he would be intersecting 3 cubes (if this was 2D). How would I calculate the appropriate response only using one cube, when the player has to be moved along two axis? I think I would have to sort them by distance and potentially consider each of them. Though I would only need to consider two in this case.

Jeff 2010-10-11 03:00:36

A:

You might implement a kind of hybrid broad phase when your two (or more) stationary cubes in a row can be combined into one larger rectangle. Test against the larger rectangle first. It will give you the results of your green check mark and be faster than checking each cube anyway. Then, after that, only if you need to, check against the individual cubes.

Steve H 2010-10-11 01:43:15

I'm trying think how I would apply this to 3 dimensions. If I had a shape like an 'L' that was standing up, I could combine 2 blocks horizontally or vertically. But I think the order I would have to apply the response would depend on the player's position or movement direction.

Jeff 2010-10-11 02:55:26

A:

I think I am going with Tom Sirgedas' suggestion of sorting the collisions by distance and applying them as necessary. Unfortunately it was a comment and not an answer, so I don't think I can mark it as the answer, but I've marked it as a great comment. Thanks for the input everyone.

Jeff 2010-10-13 16:20:32

Tom Sirgedas comment is essentially saying the same thing as ring0's answer, but a little more concisely.

Cameron 2010-10-13 20:36:20

ansaurus

tags:

views:

answers:

Sliding AABB collision - getting stuck on edges

related questions