AABB Collision problem with adjacent tiles

Game Mechanics
#1

Hi. I have been reading through a lot of collision detection resources, but I haven’t managed to find anything regarding my problem (mainly because I don’t know how to name it exactly …).

I am currently rewriting the collision engine for my 3D game to something proper and wanted to start really simple: only AABBs collide with each other. Also, a dynamic entity (the player) can only collide with static geometry (the map).

So I used SAT in its most basic form and also calculated the minimum translation vector (penetration vector).
Illustration:

Entities are moved by the movement system, afterwards the collision system detects the collision, calculates the penetration vector and adjusts the position and velocity accordingly. All fine until here.

However, the map is similar to a tile-based environment because it consists of a grid of pistons (Screenshot). Those pistons can extend upwards individually, which is why all of them have a separate bounding box.

Now, the problem arises when the player walks over that (for now flat) surface of adjacent AABBs. As it approaches the edge of a piston, the horizontal distance to its wall becomes smaller than the vertical penetration caused by gravity, so the collision system decides to push the player outwards horizontally.
Illustration:


(green arrow indicates the movement of the turquois point because of gravity)

If there would be emptiness around the piston, that would be acceptable, but because they are tightly packed next to each other, the player is now right between the adjacent pistons and simply falls downwards.

I assumed this would only happen at high falling speed, but since it even occurs when just walking, it poses a huge issue.
Are there any established ways to solve this issue? How exactly should this be labelled? (so I can search for solutions …)

Or am I missing something obvious? Shouldn’t this be the problem of any tile-based AABB collision system, even in 2D?

Any help is appreciated. Thanks!

For the sake of completeness, here is the relevant collision code, but I believe that it does what it should and the problem lies in theory, so it shouldn’t be very important:
AABB class: http://pastebin.com/GDCpis9M
Method to detect and resolve collision of 2 entities: http://pastebin.com/ymjZikPG

#2

Anyone? :frowning:

#3

Since no one helped, I’ll give you something general about your answers.

[quote]I assumed this would only happen at high falling speed, but since it even occurs when just walking, it poses a huge issue.Are there any established ways to solve this issue? How exactly should this be labelled? (so I can search for solutions …) Or am I missing something obvious? Shouldn’t this be the problem of any tile-based AABB collision system, even in 2D?
[/quote]
The short answer is there isn’t really anything established, so labeling would be hard as this is a logic based issue. Unless you’ve done a lot of platform games, it isn’t really obvious, and yes, this occurs even in 2D games.

I don’t think that this problem is a syntax issue. However, I did notice a few logic based issues with how you are designing the platform game in the first place. The best method would be to only use gravity when it matters. In other words, make your game state based, and only apply gravity when you entity is falling or jumping.

The piston problem is a little harder though because it depends on the timing of how you react to entities using AABB. What I usually do is base all collisions on the moving entity that matters the most (the player character), and give everything else a lower priority (moving platforms). The collisions that matter to me the most are ones that come from the floor, so if any entity pushes up on my character from the bottom, I prioritize that in my AABB before all other collisions.

Mario (cut & paste in IDE)

There are no moving platforms, but an AABB system has to be robust and have multiple checking points (left and right bottom corner) to be able to check for moving entity collisions. Having a state based gravity system will give you better control of when to check for these collisions.Removing gravity except when you are falling is a very good first step, as it’ll be easier to check for piston collisions.

#4

The corner of boxes colliding is a worst case scenario for using a penetration depth based collision response system. If you want this case to work I recommend you do use a system that determines the actual faces of the boxes that collided and at what time so you can order your collisions correctly. The bottom of your player box and the top of the piston box will be the first faces to collide) Use swept AABB collision tests to do this.

#5

So after being preoccupied for a while, I decided to try and tackle this issue again.

[quote=“ctomni231,post:3,topic:49487”]
While I see reason why you would do this, I don’t see how this fixes the problem. I think it would just add complexity to keep track of the “falling” state. It needs to set when the player jumps, is knocked up by an explosion or other external forces or walks off an edge. The latter being the most cumbersome to detect. But the biggest collision issue I have is not directly related to the player walking on the ground, but definately occurs when falling, so applying gravity based on state does not help too much.

[quote=“ctomni231,post:3,topic:49487”]
Right now, the pistons are not even moving in real-time, they only jump to a pre-defined position at some phase of the game and push anything colliding upwards (which is handled separately as soon as the new extension is set).
So technically the player is the only moving entity colliding with static geometry.

Sorry, I do not understand that part. What about the collision when I am actually falling? The problem that I visualized in my original post still applies, and this is what gives me the biggest headache right now: The player falls down on the floor and their new position is closer to a horizontal edge than the top of the piston.

I could completely leave out dynamic pistons or a grid of boxes and would still run into the same issue. Even if it is only one geometry box that is collided with - falling into it from the top while being close to its side pushes me out horizontally.
I also cannot just make the resolver always push upwards since that would just allow everyone to teleport up arbitrary walls by bumping into them.

I wanted to avoid swept collision systems because I cannot understand the math behind it as soon as more complex shapes than AABBs are involved. If a dead simple grid-like floor collision already cannot be solved with a penetration depth based system at all, I am probably at a loss …

#6

Mario with Pistons… rewritten Cut & Paste IDE

I rewrote my example for you, with working pistons that move up and down. AABB is more than sufficient for this, even if your character is knocked up by an explosion or walks off an edge. In the example I have, my character is always falling. The only things I actually check is to see what is keeping my player character upright.

When I say states, I mean to check what is preventing your player from falling. The only constant collision is gravity, and the movement is player controlled. Honestly, unless there is a boulder rapidly affecting player left & right movement, dividing up your cases is the way to go.

So, when my character jumps, gravity is already applied. I just make him accelerate faster in the up direction so he lifts off the ground. Gravity is a constant force in my game example (just like in real life). When on a platform, I negate gravity by having the player character push upwards. It gives the exact same effect as standing still. I can easily expand this system to vertical and horizontal moving platforms by easily checking to see whether my player character is standing on it. When gravity is a constant force, you won’t have to worry about arbitrary collision checks. It is not every day that someone will write up a fully working example. If anything, just study what I’ve done to get two moving pistons to work in this example.

Sadly, the only two solutions to your problem is to widen the player hit box to a line, or ignore the collision if it is too close to the edge of the piston. Trust me, most of the time, players won’t notice the difference, so just do what feels right for your game. Taking out horizontal movement checks for falling will also help, as you can see where your character is merging with the piston. :point:

#7

The minimum translation vector approach will just always get this use case wrong because it does not contain the data on where the player was in the instance before the objects collided, it has no way to tell the difference between the player being slightly above and being hit from below or slightly to the side and trying to move through the piston. If you just need more temporal “resolution” because the relative velocities of your player and the piston are too high for your timestep you can do a sort of backward binary search iteration over time to find the earliest instance when the player and the piston collide. If in the instance just before that the player was above the piston then move them up, if not then move them to the side. If you still notice inaccuracy then increase the iterations.

Of course this is really just an iterative way of trying to approach the accuracy of a swept collision test, but it is probably the easier way to code it.

Doing a swept collision test for two AABBs is really simple and also avoids any possibility of objects moving through each other and it allow you to order your collisions in the correct order.

Doing a swept collision test between two complex shapes is difficult, but if you keep one of your shapes as a simple AABB or sphere then the other one can be as complex as you like and it is not that hard to write a swept collision test. And most games do keep the collision model of their player as a simple object if for no other reason then to keep it from getting stuck in odd spaces.

You could even write a swept collision test between an arbitrary collision bitmap(I choose this example because it is the most complex shape I could imagine) and a AABB (or other simple non rotating shape) like this:
-subtract the position of the bitmap origin from the starting position of the player to get a relative position
-if the the collision bitmap object is moving (like your piston) then subtract its velocity from the velocity of the player to get a relative velocity
-the AABBs position A will be defined as the relative position calculated above
-the AABBs position B will be defined as position A plus the relative velocity calculated above times the length of the current timestep
-“draw” the collision bitmap at the origin
-(for a relative velocity that is down and to the right do the following, the other cases are obviously just slightly different)
-“draw” the shape that defines all of the area that the RIGHT edge of the players AABB will cover from its A position to its B position (this will be a parallelogram) and find the LEFT most point that the bitmap collides with it and figure out at what time offset during this timestep the right face would be at that position
-“draw” the shape that defines all of the area that the BOTTOM edge of the players AABB will cover from its A position to its B position (this will be a parallelogram) and find the TOP most point that the bitmap collides with it and figure out at what time offset during this timestep the BOTTOM face would be at that position
-compare which of the times occurs first and that will be the time of the first contact and will tell you the exact time and exact point point and edge of player contact and the point of the bitmaps contact

Note that you don’t really need to “draw” the items, you are really just doing a search through the bitmap to find the left most and top most points that fall within the parallelograms.

For a polygon instead of a bitmap you would find which is the left most and top most vertex of the polygon that falls within the parallelograms. But if a polygon is partially inside the parallelogram then you need to insert vertices at the points on the polygon’s edges where they exit or enter the parallelogram because the collision can happen at those points too.

For a circle instead of a AABB the test is just slightly different, but much harder to put into words.