next »

[vittorioromeo]

When my AABB physics engine resolves an intersection, it does so by finding the axis where the penetration is smaller, then "push out" the entity on that axis.

Considering the "jumping moving left" example:

• If velocityX is bigger than velocityY, AABB pushes the entity out on the Y axis, effectively stopping the jump (result: the player stops in mid-air).
• If velocityX is smaller than velocitY (not shown in diagram), the program works as intended, because AABB pushes the entity out on the X axis.

How can I solve this problem?

Source code:
http://pastebin.com/fEZY78zh - player
http://pastebin.com/FxUhcrjr - AABB physics

[JMickle]

In my platform engine, all the X coordinate stuff and Y coordinate stuff is handled completely seperately.

It checks how much you moved in the X axis, then checks if you are in a wall, if so, moves you out. THEN it checks the Y axis movement, checks if you are in a wall, if so moves you out. This way you won't ever get your problem.

Moral of the story is don't ACTUALLY move your character unless you know his movement will be fine.

Code:

PSEUDOCODE

xmov = 0 //reset movement this frame
xmov += xacc //add in the acceleration (from player input etc.)

if collision(x + xmov, y) { //if there will be a collision when you move...
  while !collision(x + sign(xmov), y) x+=sign(xmov); //move the character as close as it can before it hits what its colliding with
  xmov=0; //stop moving
} else { //if there ISN'T a collision...
  x += xmov; //go through with the original plan.
}

[st33d]

Real moral of story.

move X axis before Y axis

[vittorioromeo]

It works! However, since I add gravity to velocity every frame, I do not understand when I'm supposed to set the vertical velocity to 0 to make the player being able to jump. If I set it to 0 after a vertical collision resolution, the player can stick to the ceiling after jumping.

Source code: http://pastebin.com/xExZEyy2

[Moczan]

It works! However, since I add gravity to velocity every frame, I do not understand when I'm supposed to set the vertical velocity to 0 to make the player being able to jump. If I set it to 0 after a vertical collision resolution, the player can stick to the ceiling after jumping.

I usually solve this problem using simple state machine. My character has few states, indicating if it's onGround (jump enabled), inAir (double-jump enabled), onWall (wall jump enabled) etc. Also collision detection routine not only returns collision points, but also response, if character hit ceiling, floor or wall, so each state's update function will know how to behave.

[vittorioromeo]

I have another problem now. And it's a pretty big one!

Floating point precision screws up calculations in the physics.

Read about it on my original post on Stack Overflow

http://stackoverflow.com/questions/6422293/floating-point-precision-and-physics-calculations/

[st33d]

When testing for x + width (or y + height), subtract a tiny amount from the width, say 0.000001

thus:

if(pos >= x && < x + width - toleranceValue)

Purists will suggest you account for the actual slip of the binary value, but in all honesty a small subtraction is acceptable for the scale the average platform game works at.

This solved my own problem with floating point slippage.

[vittorioromeo]

I tried changing the overlap check to this, but it didn't work.

public static bool AABBIsOverlapping(Vector2 mCornerMin1, Vector2 mCornerMax1, Vector2 mCornerMin2,
                                             Vector2 mCornerMax2)
        {
            float tolerance = 0.000001f;

            if (mCornerMax1.X <= mCornerMin2.X - tolerance || mCornerMin1.X >= mCornerMax2.X - tolerance)
                return false;
            if (mCornerMax1.Y <= mCornerMin2.Y - tolerance || mCornerMin1.Y >= mCornerMax2.Y - tolerance)
                return false;
            return true;
        }

It actually screwed things up even more, resulting in the bodies not even being able to land on the ground without getting shooted away to the right. 

[st33d]

It's important to understand that the average rectangle is measured from:

X and upto but not including X + WIDTH

thus another rectangle at X + WIDTH is not colliding with your rectangle

So you test for the following:

GREATER THAN OR EQUAL TO X

AND

LESS THAN X + WIDTH

Your conditions do not reflect this behaviour.

If you follow this method strictly, very rarely the x + width position may be slightly off for two objects that are next to each other. Hence the subtraction of the tolerance value from X + WIDTH and not from every single equation.

If you look at my post above, you'll notice I didn't subtract the tolerance value from everything, just X + WIDTH, where there is an infinite edge leading up to but not including X + WIDTH.

This is called a half-open interval.

There's probably another way of handling AABB collisions like this, but that's out of my particular field.

[motorherp]

It seems to me that the real problem you're having is with how you are attempting to resolve object penetration.  Unfortunately with game physics there is no bullet proof way to correctly resolve penetration after the incident by using combinations of simple rules such as pushing the object out along the y axis then the x axis etc.  There'll always be a situation where such rules break down and lead to unwanted behaviour. 

The only real correct way to handle penetration is to prevent objects from penetrating in the first place rather than trying to resolve penetration afterwards.  To do so would require that before moving each object you perform a 'swept' AABB collision test for that object starting at its current position to the position it wishes to move to.  These test take into consideration the total movement of the object throughout the frame rather that just handling collision at discrete time intervals (ie: just at the end of each frame) and if a collision would occur during the planned motion it will return the time of first contact.  You should then only move your object as far as the time of first contact at which point it will be positioned flush against the colliding object but not penetrating it.  You can then apply any collision resolution such as changing the objects velocity etc.

For a truely accurate physics engine you sould then continue to simulate for the remaining time left in that frame after the time of first impact, however having to do many multiples of simulations each time step can complicate your code significantly and slow down your engine.  Fortunately it is often acceptable to simply discard any remaining simulation time for each object each frame after the point of first contant for that object without it being noticable of causing unwanted behaviour.

Although I've not tested this code personaly so cant vouch for it, you might want to take a look at this article I found which describes a swept AABB collision test -> http://www.gamasutra.com/view/feature/3383/simple_intersection_tests_for_games.php?page=3.

If you're wanting to keep things simple and aren't concerned with having a 'correct' solution though then you might want to consider changing your push axis selection method.  Rather than pushing out along the axis which corresponds to the moving objects highest velocity like you are currently doing, instead push out along the axis with the smallest penetration.  This should give you better results without you having to change too much.

[Edit: my bad - you are already pushing out along the smallest penetration axis, I must have misread your OP.]

[vittorioromeo]

I fixed the float problem by using only integers. It works fine. The method I'm using now is to prioritize pushing on the X axis first, then the Y axis.

Consider this situation:



I have a problem with AABB collision resolution.

---

I resolve AABB intersection by resolving the X axis first, then the Y axis.
This is done to prevent this bug: http://i.stack.imgur.com/NLg4j.png

---

The current method works fine when an object moves into the player and the player has to be pushed horizontally. As you can see in the .gif, the horizontal spikes push the player correctly.

---

When the vertical spikes move into the player, however, the X axis is still resolved first. This makes "using the spikes as a lift" impossible.

When the player moves into the vertical spikes (affected by gravity, falls into them), he's pushed on the Y axis, because there was no overlap on the X axis to begin with.

---

Something I tried was the method described in the first answer of this link: http://gamedev.stackexchange.com/questions/13774/2d-rectangular-object-collision-detect-direction
However the spikes and moving objects move by having their position changed, not velocity, and I don't calculate their next predicted position until their Update() method is called.
Needless to say this solution didn't work either.

---

I need to solve AABB collision in a way that both of the cases described above work as intended.

This is my current collision source code: http://pastebin.com/MiCi3nA1

I'd be really grateful if someone could look into this, since this bug has been present in the engine all the way back from the beginning, and I've been struggling to find a good solution, without any success. This is seriously making me spend nights looking at the collision code and preventing me from getting to the "fun part" and coding the game logic

[st33d]

Think of it like this:

When a block moves horizontally it can only push horizontally

When a blocks moves vertically it can only push vertically

When the block moves, check what it is going to move into. And then only push in that direction.

Stop resolving try pushing.

You may want to try a combination of the two if it's a bit over your head.

[vittorioromeo]

Think of it like this:

When a block moves horizontally it can only push horizontally

When a blocks moves vertically it can only push vertically

When the block moves, check what it is going to move into. And then only push in that direction.

Stop resolving try pushing.

You may want to try a combination of the two if it's a bit over your head.

This is a solution, however, since spikes are moved by directly changing their position and not velocity, it would require me to "flag" vertical spikes as such.

I can use this as a last resort solution.

I'm looking for something that "automatically" works in any situation. Maybe I'm being too needy, but I would like to have a simple physics engine I can reuse in any of my games, without having the need to check for special solutions for specific entities.

[bateleur]

I'm looking for something that "automatically" works in any situation.

This is a good thing to look for, but be aware that sometimes this is a Do What I Mean problem. That is, for any given situation you have some intuitive expectation, but in fact there may be no simple, systematic rule that encapsulates all your expectations.

Example: I wrote a 2D game with a ball in it many years ago and initially had a very simple collision system, then across the game's two months of development the collisions got more and more complex as I found more and more obscure cases where I knew what behaviour I wanted and wasn't getting it. In the end my collisions ended up depending on ball velocity, the local geometry of the thing the ball hit, gravity and friction and required processing multiple collisions per frame in cases where a fast moving ball bounced off multiple objects in a single processing step.

[vittorioromeo]

I'm looking for something that "automatically" works in any situation.

This is a good thing to look for, but be aware that sometimes this is a Do What I Mean problem. That is, for any given situation you have some intuitive expectation, but in fact there may be no simple, systematic rule that encapsulates all your expectations.

True

I will keep finding for an optimal solution until I get too frustrated. Then I will "hardcode" special situations in the collision code.

Keep the suggestions coming.
I've got other suggestions that may inspire you in this thread: http://forums.tigsource.com/index.php?topic=20298.msg580418#new

[vittorioromeo]

I've posted a recap of the collision problems on stackoverflow... It should be more ordered and easier to understand.

Can someone take a look at it?

http://gamedev.stackexchange.com/questions/14486/2d-platformer-aabb-collision-problems/

[ThemsAllTook]

I implemented a collision system yesterday and had to solve some of the same problems you seem to be having. I think your solution to the first problem (resolving X before Y) could be improved upon in a way that may eliminate your current problem. The way I've handled this is to resolve collision axes in an order that depends on the particular situation. A summary of how I did it is posted here.

The key part:

If the two collisions have occurred at the same time (within a small margin of error), whichever has the largest "coverage" wins. Coverage is calculated as the amount of overlap between the player and the tile on the non-colliding axis. This is done so that if you're trying to move diagonally, you won't collide with the "crack" between two tiles that form a solid wall.

So, in the situation illustrated at the bottom of your diagram, there are two potential collisions to evaluate: The collision on the X axis with the right edge of the third block from the bottom, and the collision on the Y axis with the bottom edge of the block fourth from the bottom. The amount of contact between the left edge of the player and the right edge of the first block is much greater than between the top edge of the player and the bottom edge of the second block, so the first block's collision (on the X axis) is resolved first. Turn the whole thing 90 degrees, and the Y axis will be resolved first instead.

I'm working on writing a tutorial that demonstrates how to implement this. I'll post it here once it's finished, which hopefully should happen within a day or two. Meanwhile, I'm not sure if it'll be of any help (or is even readable!), but here's my code.

[vittorioromeo]

This seems the solution to all of my problems.
I'm trying to implement it, but reading the code is difficult. What is entity->radius supposed to be in an AABB shape?

[ThemsAllTook]

This seems the solution to all of my problems.
I'm trying to implement it, but reading the code is difficult. What is entity->radius supposed to be in an AABB shape?

It's just half the width and height of the moving object. If your object position and size are represented in some way other than center + radius (which they'd have to be if they're not square/circular), like say as a rect, you can just replace any (position.x - radius) with rect.left, (position.x + radius) with rect.right, etc.

Hmm, using radius does muddy up the code a bit. Hopefully I can make it a lot clearer when I get the tutorial done.

[vittorioromeo]

This seems the solution to all of my problems.
I'm trying to implement it, but reading the code is difficult. What is entity->radius supposed to be in an AABB shape?

It's just half the width and height of the moving object. If your object position and size are represented in some way other than center + radius (which they'd have to be if they're not square/circular), like say as a rect, you can just replace any (position.x - radius) with rect.left, (position.x + radius) with rect.right, etc.

Hmm, using radius does muddy up the code a bit. Hopefully I can make it a lot clearer when I get the tutorial done.

Thanks for the help. I think I will wait for the tutorial though, I'm having a lot of trouble understanding the code