A Physics Engine with Incremental Rollback

We want Easel to be powerful enough to make the kinds of games you would play for hours. Popular multiplayer games like Among Us let you walk around an entire spaceship, completing tasks and evading impostors. Unfortunately, up to this point, games of that scale were out of reach for Easel, because the off-the-shelf physics engine would have to snapshot and roll back the entire world to support Easel's predictive multiplayer architecture. It's too much to do every frame.

Until this point, you were required to keep your world small. But not anymore!

Easel's new custom-built physics engine only snapshots and rolls back the parts of the world that change. That big spaceship might have thousands of objects forming the walls, the control panels, the vents, and so on. However, each frame, a surprisingly few number of objects actually change - perhaps less than 30 per frame as the players walk around and interact with the world. A smart implementation keeps objects sleeping while they are offscreen.

With only 30 objects out of thousands needing to be snapshotted each frame, a factor of 30-50x fewer than before, multiplayer Easel games with large worlds suddenly becomes feasible. Release the feral hogs!

Under the Hood

Easel's new physics engine is custom-built for Easel, which is why it supports everything Easel supports, but better! Here is a tour of some of the features that make it special.

Sleep

The fastest way to do something is to not do it at all. When a body is asleep, it does not require any snapshotting, rollback, or any physics calculations until it wakes up again. Unlike other engines which wait for a few seconds of inactivity, Easel puts bodies to sleep immediately when their velocity reaches zero (within a small epsilon threshold, of course, we're not slow).

One tricky case here is gravity, which has the potential to keep your entire world awake with its constant nagging force. Easel tracks the forces and reaction forces on every object and can see whether they are balanced or unbalanced. Regardless of whether it is at zero velocity, as long as one body in a stack has unbalanced forces, the stack has not settled into equilibrium and so the whole stack stays awake.

Spatial Indexing

Like many other physics engines, Easel's broad phase uses a Bounding Volume Hierarchy (BVH) to quickly find potential collisions. Easel's BVH algorithms are optimized to minimize unnecessary snapshotting and rollback, only performing incremental rebalancing when the tree is already undergoing change. Do you only do the vacuuming just before your friends come over? Easel's BVH is lazy efficient just like you.

One additional trick is Easel's BVH also tracks the Categories of each collider, which speeds up common game queries dramatically. It is very common, for example, for a bot to target the nearest player, and if the player is on the other side of the map, it would have to traverse through every single collider in the world to find the nearest player. Finding the nearest Category:Needle amongst a sea of Category:Haystack colliders is a lot faster with a metal detector!

Stepping

Making a character take a step is something so common but surprisingly complex in physics engines. A common method is to add velocity for the step, then subtract it after the physics simulation is complete, but a problem arises when the character collides with an obstacle mid-step.

Even if the physics engine does its job correctly and zeroes out the velocity, later on when the previously-added step velocity gets subtracted, it reintroduces the bounce back that the physics engine just zeroed out. It makes your character feel really bouncy.

• Some games fix this by damping out all velocity, which removes bounce back but also removes knockback too, removing some of the fun and feel of the game. Walk into a wall? No bounce, good. Get hit by a fireball? No knockback. Seems wrong.
• Other games fix this by creating a kinematic character controller based on raycasting. In physics engine terms, kinematic (as opposed to static or dynamic) means that the character is not affected by forces and collisions. In other words, the physics engine has failed to produce the desired results, and so it is now being bypassed entirely. You had one job physics engine. Physics. Do it. Please. Not not like that. Okay fine I'll do it myself.

Non-bouncy stepping has been built directly into the solver of the Easel physics engine. Simply use ForcefulStep with the new restitution=0 parameter, and Easel's new physics engine will make sure the step does not bounce back.

How does it work?

The trick is, Easel treats stepping in a similar way to how it corrects for position overlap.

Have you ever played a game where your character gets stuck in a wall, and the physics engine tries to eject you, sending you flying across the map? It is a common physics engine glitch. Super Mario 64 speedrunners famously love to make him slide backwards up the stairs on his backside using a glitch like this. Ow.

Modern physics engines try to avoid this problem by solving for position correction separately. The force that would eject your character out of the wall is applied immediately to the position without changing your velocity, which means the ejection velocity does not last beyond the current frame.

ForcefulStep in Easel is implemented as part of position correction, which is why it does not cause bounce back, unless you want it to. We're killing two (angry) birds with one stone!

info

In reality, it is a bit more complicated for numerous reasons. Easel first solves for both ejection+stepping and velocity at the same time, then we store that ejection velocity, then we remove the ejection+stepping constraints and solve again, storing the stabilized velocity. At this point, nothing has moved yet, which is why we are now free to sweep for the next time-of-impact using the correct velocities. When it comes time to take a step, we use the ejection velocity, but at the end of the frame we only commit the stabilized velocity and so the bounce disappears.

In other words, Easel collects all the data it needs up front without making changes, so that when it does make a move, it can make the correct one.

Continuous Collision Detection

We love it when two fireballs collide with each other in mid-air.

Finding the collision between two fast-moving objects like this requires continous collision detection, because if we just checked for collisions once every frame, we might miss the precise moment when the two fireballs overlap.

Continuous collision detection is Easel is performed by sweeping and then shape casting like other physics engines, but in doing this we noticed a few differences between Easel other physics engines which may be interesting to some nerds game developers:

• The Rapier physics engine can produce an incorrect result when the fireball begins the frame touching a mirror. In Easel, collisions are resolved first, causing the fireball to bounce and change direction, and only then does it search for the time-of-impact of those two fireballs. In Rapier, the time-of-impact is searched for first using the original velocities, meaning that in this case, it starts by sweeping that fireball in the wrong direction. This difference happens because Rapier does the position integration early, committing to a substep length before it knows what the time of impact is going to be. Easel stores enough information up front that it can do the position integration after it knows the time of impact, avoiding this problem.

• Box2D 2.4 does sweep using the correct velocities but takes a different approach of doing the full normal physics simulation, then backtracking, which is why all collisions are already resolved before continuous collision detection. Interestingly, the new Box2D 3.0 does not support dynamic-to-dynamic continuous collision detection at all, meaning those two fireballs would have no choice but to miss each other like ships in the night. Perhaps this is a future direction for Box2D as, besides this, it seems they have achieved the holy grail of avoiding substepping at all by using speculative contacts.

• Photon Quantum, a professional multiplayer rollback netcode engine, does not support continuous collision detection at all, citing that their physics engine is stateless and so it would be too expensive. It seems incremental snapshotting and rollback of our physics state has enabled Easel to support this feature performantly.

Bodies can move themselves

One inconvenient edge case with the previous physics engine is that a body with a velocity or turnRate and no colliders would not move at all.

It could be argued that this is correct. If there is no mass to hold momentum, there's no movement, but we are not just making a physics engine, we are making a game engine. Sometimes bodies are just a way to group sprites together, and the physics is not important.

Now if you give a body a velocity or turnRate, it will move itself even if it has no colliders. Attach a TextSprite and you could have a simple billboard floating up the screen, scrolling away to a galaxy far, far away.

Sidenote: Photons don't have mass but they still have velocity, in fact there are 10^17 of them hitting your eyes right now every second, so maybe some physics engines need a reality check.

Thanks to

Easel's physics engine is built upon the collision detection algorithms of Parry, an excellent open source library created by Dimforge that powers the Rapier physics engine.

Making a physics engine has been a huge endeavor. Many little decisions have been made to make implement it in a way that is neat, efficient and works well with Easel's multiplayer architecture. Now everything, not just the physics engine, but all parts of Easel only snapshot and rollback the parts that change, meaning you can make much bigger worlds.

It's time think bigger!