In late 2012, a significant fraction of ROBLOX developers worked together to make games run on performance-constrained hardware (iPad, iPhone and iPod touch, to be exact). The team set off on an exhaustive hunt for inefficient processes within the ROBLOX source code, then found ways to optimize the problem areas that had substantial performance payoffs. This allowed us to bring the full in-game multiplayer ROBLOX experience to mobile devices in December, but we did have to make a concession: there would not be a destructible environment in ROBLOX Battle. The physics simulation was too resource intensive.

Soon, that’s going to change, as Kevin He has altered the way ROBLOX handles collisions – one of the major components of our distributed physics engine. Better yet, you’re about to see a 2-4x increase in physics performance across all games and hardware.

Before getting into the gritty details, it’s worth illustrating the final result of modeling collisions with “impulses” rather than “springs.” ROBLOX runs much smoother when the physics engine is under heavy load, as demonstrated in the following video.

Testing physics performance using Agent767’s fragmentation test, which generates many parts

The basics of collision detection

Our latest improvements to the ROBLOX physics engine center on collisions between the parts that make up each world. Modeling these collisions is a complex process that can be split into three phases.

1. Broad Phase
2. Narrow Phase
3. Solver Phase

These phases are always happening behind the scenes, with every step of the physics simulation. The broad phase is the physics engine’s check to see whether any pair of parts in a ROBLOX world is capable of colliding. If two objects are far apart, they are rejected. If two objects are in close proximity, though, the physics engine considers them a possible collision and sends them along to the narrow phase. The narrow phase is the physics engine calculating the exact contact points between the pairs of bodies. The solver phase, then, is the physics “kernel” actually applying force to maintain the contact constraint between the parts.

These three phases serve as a method of narrowing down the objects that need to go through a collision simulation. All three steps are expensive, in terms of CPU resources. The broad and narrow phases run at 100-200Hz (100-200 times per second), and the solver phase runs at more than one thousand times per second – this is the phase to optimize.

Background on modeling collisions

Before getting to the optimization, it’s worth understanding how the solver phase works. Essentially, it creates an in-game representation of the laws of physics. For our purposes, collisions should happen according to Newtonian laws – particularly the second law. (The acceleration of an object is dependent upon two variables: the net force acting upon the object and the mass of the object.) For a long time, ROBLOX has modeled collisions as a stiff “spring.” Depending on how hard two objects collide – or how far one penetrates the geometry of another – the spring pushes back with the force needed to separate them in a physically accurate way.

This is pretty intuitive. Many objects in the real world have some measure of elasticity, and they push back after colliding with another object. The downside is the spring solver is very resource-intensive. In order for it to work, the spring must be stiff, without being overly sensitive (thus blowing up the physics simulation). It also must continually exert less force as it lengthens. We have to simulate springs at a very high frequency in order to maintain their stiffness and accuracy, which causes slowdown in situations where many collisions are happening simultaneously.

Collision optimization #1: free-fall objects

The first optimization we implemented to make physics run faster is a “free-fall solver.” Free-fall objects (aka ballistic objects) are defined as only having gravity acting on them – the collision hasn’t happened yet. There’s no need for us to simulate a complex spring at high frequency if there is no collision, so we now take a shortcut: objects in free-fall are simulated at about 1/20^th the frequency of the spring simulation. We get an equally accurate result.

Using Newtonian laws, we can figure out exactly where an object in free-fall is supposed to be at any given time. It’s a given, it works great and saves a lot of processing power. However, the object will eventually reach the ground and, when that happens, we need to be able to model the collision efficiently.

Collision optimization #2: impulses instead of springs

Once an object collides with another, we want a fast algorithm to model the reaction in a physically realistic way. As mentioned above, using a spring to model the collision is very realistic, but it requires tremendous resources to simulate. The force of the spring changes at it lengthens, which is something we cannot calculate in one step; we must do it continuously and at high frequency. So, we’re moving away from springs and toward “impulses.”

An impulse is not as intuitive as a spring but, when boiled down to its essence, it’s pretty easy to understand. You can think of it as a change in momentum; the effect of a force applied to a body over a given period of time (Impulse = Force * ΔTime). Since an impulse does respect time, it can be a small force over a long period of time or a large force over a short period of time. A textbook illustration is how a baseball bat applies impulse to a baseball: a lot of force for the little bit of time the bat is in contact with the ball (a split second).

We treat impulses in ROBLOX as an instantaneous force over a short period of time. We use them to correct the velocity of parts that have collided (whereas a spring corrects the position); to find the force needed to accurately separate two bodies.

Here are some simple examples of momentum changes that could occur in ROBLOX:

1. Two balls collide with a certain velocity. Following Newton’s second law, we can instantaneously determine the velocity of each ball after the collision by plugging the velocities, masses and elasticity of the objects into a simple formula.
2. Two boxes collide – a more common situation in ROBLOX. This complicates the above scenario because we have to determine not just the resulting velocity, but the resulting linear and rotational velocity. We can find these velocities using the motion of inertia (MOI), which is similar to mass but takes into account the amount of inertia of each primary axis.

For two boxes colliding, we use an impulse formula to predict the results of the collision.

---

Impulse: the impulse needed to separate body A and B following Newtonian laws

c: coefficient of restitution (elasticity)

normal: the normal direction vector of the contact point

V_ab: relative velocity between A and B

M_a, M_b: mass of A and B

I_a, I_b:  moment of inertia matrix of A and B

R_a, R_b: the positions of the contact points on A and B, relative to the center of mass of each body

---

Ultimately, using this formula we can skip a lot of intermediate processing and directly simulate for the result of a collision. This lets us process collisions in one step, rather than 20, 100 or more with a spring. Impulses simulate collisions at a higher level – that is, with less detail – than springs, but collisions happen quickly and often, and the efficiency gained is more important than the subtle detail lost.

Challenges

Impulses sound great: they’re instantaneous, velocity based, and skip unnecessary details. What’s the catch?

The first challenge is simultaneous contact points. In many collisions, objects make contact at more than one point. For instance, if a box is sitting on a baseplate in ROBLOX, we need to simulate the collision at the box’s four corners (or it will rotate). While we could model this with incredible accuracy by solving a matrix enforcing all the constraints at all contact points, we need something simpler and more efficient. We use a “sequential impulse solver.”

Using this technique, we resolve one contact point per collision at a time. With every step of the physics simulation, we assume one contact point between each pair of bodies, find the impulse needed to separate them, apply the impulse, then move onto the next contact point and repeat the process. It’s an approximation, but we do this so quickly we create a believable representation of simultaneous collisions.

The second challenge is resting contact. Imagine a 10×10 wall of blocks in ROBLOX. Using the sequential solver, we can continue looping around the contact points for each block very quickly to keep them from becoming unstable. As we run more and more iterations around the contact points, the wall becomes more stable. The key, then, is determining how many iterations to run – run too many and we lose performance.

It’s not unstable until we start removing pieces from the bottom.

Our solution is what we call “adaptive iterations.” For any physically simulated ROBLOX environment, our engine determines whether it’s dynamic (lots of moving parts) or static (lots of resting contacts). If an environment has a lot of resting contacts, we need to care more about stability and we’ll run more iterations of the sequential solver. If it has a lot of dynamic contact, we need to we need optimize for speed and run less iterations of the solver. To determine whether an environment is dynamic or static, we measure the frequency and magnitude of impulses applied. If the parts are constantly being separated by frequent, small impulses, the scene is static. If parts are separated by low-frequency, large impulses, the scene is dynamic – parts are colliding at high speed and we’re separating them quickly.

The end result of all of this optimization is a significant increase in the speed at which ROBLOX can simulate physics. Whether parts are flying in every direction or comfortably resting on one another, impulses help us keep the simulation moving forward without sacrificing anything more than nearly invisible details. We’ll soon be able to run our physics simulation better on all hardware – and don’t forget to re-visit ROBLOX Battle when these optimizations go live next week. It’ll be a new game.