Multiplayer Platformer Log #2 – Physics

This second log was supposed to be about making the server authoritative so we would prevent cheating. Authoritative server has to simulate physics while client does client-side prediction. The first step took a bit longer than expected and deserves its own log.

The previous naive implementation of our multiplayer platformer used Phaser’s Arcade Physics. Given new requirements, which will be further explained in the next log, we can’t use Arcade Physics and need to create our custom solution.

Originally I thought this will be really primitive, but it wasn’t.

First implementation

For now we are trying to keep the game as simple as possible, so all we really need is simple axis-aligned bounding box based physics. That means just rectangles without rotation.

Quick googling showed a couple of tutorials on how to implement it, and the collision detection itself is really simple as expected. I followed Simple AABB Collision Detection Using the Minkowski Difference by Kenton Hamaluik, because it was well written and in Haxe, so I could just copy the code verbatim.

The principle behind the collision detection is to check the penetration of objects, find closest wall edge and push the dynamic object out so it doesn’t penetrate the static object, but just sits on the edge of it.

This worked fairly quickly, but just being able to resolve a collision doesn’t mean it will resolve correctly.

Issues with collision resolution after the fact

The main problem with discrete step collision resolution is usually tunneling – fast objects passing through walls. I wasn’t worried about that much, as I don’t expect very fast objects in our game, although I don’t like making such assumptions either.

But let’s take this example:

Our moving object is blue, tiles are gray. This is a situation after falling down because of applied gravity, before resolving the first collision.

The red lines are push forces, visualized as starting from the center of the tiles outward, given to us by the AABB algorithm. If we apply this force to the dynamic object, it would stop penetrating.

What would happen after the collision resolution?
It depends on the order in which we handle these collisions.

If the tile on the right would be handled first, the result would be as expected. But if we applied the left one first, it would push the object to the right, not up as we want.

I spent some time tinkering with this problem, but came to the conclusion that it’s impossible to handle correctly without taking all collisions into consideration at once. That means picking which collision to handle first out of them all.

Picking the closest tile first would solve this issue, but even then I am not entirely sure it would work in all cases (and it surely wouldn’t in high-speed situations). So I decided to look for an alternative solution.

Swept AABB

After discussing this issue on Phaser’s Slack chat, @bitnenfer pointed me towards an article about Swept AABB Collision Detection and Response.

The essential difference with this algorithm is that it handles the collisions before they happen, stopping them in their tracks, so to say. It’s also more precise and completely solves tunneling.

Implementation didn’t take long, but a problem similar to one described before showed up again.

Issue with tile-based blocks

Swept AABB would work well, if there were be only big rectangles, not tiles. When it comes to tiles, the seams between them cause issues (and as I learned, this is true for all kinds of approaches to physics engines).

After Swept AABB stops the moving object on the edge of the tile, it will sit exactly at the edge, basically colliding, but not penetrating.

When moving sideways, the tile under the object wouldn’t allow it to fall down, but the tiles on the sides, despite being at the same height as the bottom tile, would register a collision and prevent movement.

I wasn’t sure how to solve this in a clean and neat way. After some research I found out it’s usually handled by pushing the dynamic object away a bit further than necessary. Enough to stop colliding, essentially sliding on top of the tiles, but without being actually visible.

In my case it looks like this (simplified code):

//get swept collision result
var collision = sweptAABB(player, box);
//move player as much as possible
player.x += player.velocityX * collision.time;
player.y += player.velocityY * collision.time;
//move it a bit back to prevent collisions with tiles on the same height
player.x += collision.normalX * 0.02;
player.y += collision.normalY * 0.02;
//...handle the rest of the time (1 - collision.time)

There are other ways to handle this issue, but this one seemed easiest to implement for my case.

Conclusion

I learned that handling collisions isn’t really that simple and that there’s multiple approaches. There is a lot written on the topic already and it’s a world of its own.

Nevertheless it was enlightening exercise and now, I have a better idea about issues and solutions that physics engines need to deal with. Kudos to all the people who wrote about their solutions.