Author: by Kevin He

[An ex-Blizzard physics and networking lead for online game Roblox shares the secrets of how the Lego-like building game simulates rigid bodies for millions of players at a time -- without losing either performance or fun.]

Roblox is built on a comprehensive physics engine, and our millions of users are constantly generating content that pushes it to the limits of its capabilities. To enable our users' unrestrained creativity and cope with their passion for ever-larger and increasingly complex simulations, we've committed ourselves to a regimen of physics-engine optimization.

In Roblox, we simulate all rigid-body physics because our users create games on the foundation of bricks, blocks, wedges, spheres and cylinders. These elements behave in game as they would in the real world, which eases the learning curve, makes it possible for users to create games in almost any genre, and adds a layer of discoverability -- all contributors to the 250 million hours of gameplay our users logged in 2011.

We should note that complex physics simulation doesn't make a game good and, in many cases, would be a waste of resources. Instead, the complexity of a physics engine should parallel the gameplay requirements.

Roblox's Physics, In Context

Roblox is near the extreme end of the physics-complexity spectrum in gaming. On the other end are MMORPGs -- from EverQuest to World of Warcraft -- which employ basic collision detection to keep players confined to playable areas.

First person shooters, such as Halo, and action RPGs, such as Diablo III, take collision-detection a step further with contact force and limited collision shapes (e.g., capsule) to generate a collision response. They also put characters into a "passive" ragdoll state, sending them tumbling after death or flying after an explosion, and use "decorative" ragdoll -- moving hair, for example -- to add dynamic visuals.

Sports are where physics simulations start to get interesting and complex. In addition to everything seen in MMORPGs and action games, sports games, such as Fight Night Round 4 and FIFA 12, introduce "active" ragdoll, where motors actually power the joints of the fighters and players. This helps achieve smooth, life-like motion and animation. Without their motors, fighters' and players' limbs would hang lifelessly and they'd collapse to the ground.

Finally, there's Roblox, where full physics simulation is enabled by default, disabled as the exception. All physical objects -- terrain excluded -- are simulated. Our engine features:

These simulations must also perform in a networked, multiplayer environment.

From Discrete to Aggregated Physics

Give someone a set of building blocks and they're probably going to use as many as possible to create something massive. Roblox is no exception, but simulating every single part of a skyscraper or a Titanic-sized ship as an individual -- or "discrete" -- rigid body is prohibitively expensive for network and CPU/GPU resources.

We are smart about simulating massive structures and vehicles. When a skyscraper is anchored to the ground and immobile, we treat it as a single entity, attached to the background environment. No dynamic motion is simulated for the discrete bricks and only collision detection is performed between the skyscraper and other moving parts or mechanisms. Our engine compresses the entire skyscraper into a static, "featherweight" part that consumes little memory. "Featherweighting" helps a Roblox world scale to thousands of complex buildings with minimal cost.

For a Titanic-sized ship sailing in water, the entire ship must run in our rigid-body dynamics engine in order to simulate a realistic, floating effect, the interaction with water and collisions with other floating objects. Simulating each of the ship's thousands of parts as individual rigid bodies would be prohibitively expensive, so Roblox simulates such high-volume, welded rigid bodies as a more efficient "Assembly" to manage resources during physics simulations.

Roblox dynamically identifies pairs of objects that do not move, relative to one another, during a frame of motion. It groups such objects together, creating an Assembly. Even a Titanic-sized ship with a thousand parts welded together is simulated as a single rigid body. This is the kind of efficiency we need to scale our physics simulation to millions of parts.

In this scenario, two parts form an Assembly, as they do not move, relative to one another, during a frame of motion.

Assemblies are not a silver bullet; their implementation presents a unique set of challenges. In a dynamic environment with constant movement, collisions, explosions, and human interactions, Assemblies are formed, fragmented, and merged all the time. Here are some common examples:

Our engine has to synchronize a consistent composition of Assemblies in real time, between clients and servers, while these changes are happening. We select the same root bodies for Assemblies and generate them in the same order across the client and server boundary to achieve smooth networked motion.

From Centralized to Distributed Physics

Along with Assemblies, our shift from centralized to distributed physics has allowed more players and more physics simulations in a shared space. Roblox initially used centralized physics simulation, a model under which physics calculations are processed on the game server, and the results are constantly fed to players and reflected on screen.

While a centralized model works on a small scale -- meaning few players, few physics calculations or few simulated parts -- Roblox's implementation wasn't made to stack up against our growth and increasingly complex physics. The server must simulate too many parts and player interactions, causing motion slow down rather than run in real time.

We solved this problem by evolving our centralized engine in 2010 to a distributed physics engine.

This graphic is a simplified illustration of the distributed physics model. In practice, client-simulated regions are not necessarily uniform in shape.

Distributed physics distributes the physics simulation among the server and players. In the graphic above, the blue area represents the server (server-simulated region) and all its physical bodies and players. In the case that no player is within an area, the server handles the physics simulation and relays data to players, as in the centralized model.

The difference is that each player has a dynamic region of physical bodies -- those within close proximity -- that they simulate locally (client-simulated region), taking the strain off the server. Such distributed architecture allows us to scale to an almost infinite number of physically simulated bodies without degrading physics performance.

We implemented load-balancing algorithms to shrink or grow the region size of each player, based on their computation power and network bandwidth. Players with slow machines or internet connections will generally simulate fewer physical objects; the opposite is true for players with fast connections and hefty rigs. The key challenge behind distributed physics is simulating objects at the border of two players' simulation regions.

A strict division works in very simple circumstances; for example, an object is in one player's simulation region and not interacting with other objects. The player runs the rigid-body simulation and sends the results to the other players.

In a more challenging -- and very likely -- scenario, object A and object B are colliding with each other. Each object is in a separate player's region. Theoretically, we could let one player simulate object A and the other player simulate object B, then exchange simulation results. With an immediate network update, this works. But the network update interval is usually lower (e.g., 15Hz) than the rendering rate (e.g., 30Hz) to conserve bandwidth. Assuming our physics engine simulates at 30Hz, twice as fast as the network update frequency, the network update only occurs at every other step of physics simulation. This causes problems during high-speed collisions.

Here's an example:

A is a vehicle simulated by player A

B is a brick simulated by player B

The scenario: Vehicle A runs into brick B. Vehicle A bounces back as though it ran into a rubber wall. (We wrote an article about this phenomenon, for more background.) Vehicle A should slow down and brick B should at least get knocked over. The following steps illustrate why it breaks:

Simulation A (Vehicle A/Player A):

A touches B at high speed and generates contact force, separating A from B

A bounces back and moves away from B; sends update of A to B

A receives update from B; B is not moving

Simulation B (Object B/Player B):

B receives update from A; A is two steps away from B

A is one step away from B; sends update of B to A.

B receives update of A. A moves away from B. B is not moving.

Simulation B doesn't get a chance to witness the collision before Simulation A processes the collision and separates the vehicle from the brick. As a result, brick B behaves as though it was anchored and vehicle A bounces back.

For slow collisions or cross-boundary interactions, this situation does not occur because both sides have a chance to witness the interaction and generate a more believable response. Increasing the network-update frequency or reducing network-link latency will improve the results of high-speed collisions, but will not solve the problem: The two parties involved in a collision are not simulated on the same simulator.

Distributed physics and buffer zones

Roblox addresses the cross-boundary simulation challenge by creating a "buffer zone" between the simulation regions of two players. Objects in the buffer zone are simulated by both players. In our vehicle-collision example, both the vehicle and the brick are simulated by player A and player B. Both vehicle A and brick B will generate correct behavior for the collision, as seen in this demo video.

When a buffer zone is active, two players simulate the same physics object(s). One player is the "authority," meaning they run a remote physics simulation of the object and send the resulting data to other players via the server. The other player is "secondary," which means they run the physics simulation locally to fill in any data gaps that come from the "authority" player. Roblox blends the motion between the remote (actual) simulation and local (estimated) simulation.

The overlapping red areas represent shared buffer zones. Objects in the buffer zones are simulated by both players.

The simplest blending algorithm interweaves the results from the remote and local simulations. Whenever a remote update comes in, we change the object position. This works, but can cause fast-moving objects in the buffer zone to stutter, due to the discrepancy between remote and local simulation results.

A discrepancy is guaranteed to exist in proportion to the network lag. We compensate for network lag between the remote and local physics simulations by including the velocity, positional data and timestamp (send and receive time) of simulated objects with each network packet. An update from the remote simulator (at time t2) would look like this:

Instead of blending x (remote position) directly with local simulation results, we compensate for network lag by figuring x as:

Xremote' = Xremote + (t2 - t1) * v

Then, we blend the compensated Xremote' with the local simulation result Xlocal. The discrepancy between the compensated remote and local simulations will be close to zero when the objects are moving at constant speed. When the delta between Xremote' and Xlocal is very small, we can use Xlocal directly to render a trajectory of the moving object with no stuttering.

When objects are colliding or experiencing a significant change in velocity, the compensated remote result can be thrown off because the velocity value is quickly outdated. In these situations we give more weight to the local simulation results and gradually fade in remote results as the collision settles or acceleration levels off. Assuming the time elapsed since a major impact on the object is e seconds, the position x can be blended between remote and local simulations as follows:

When e < 1:

X = (1 - e) * Xlocal + e * Xremote'

When e > 1:

X = Xremote'

These formulas allow us to estimate motion accurately enough to interpolate the two simulations without causing objects to stutter or move unnaturally.

This is still far from perfect. Our vision for the future is building more intelligence into the algorithm that blends motion between separate physics simulations. Ultimately, we want to seamlessly stitch together the simulation results from hundreds of players and render a massive, coherent, physically accurate world via the distributed physics engine.

A New Evolution in Roblox Physics

We're continuously improving the scale at which Roblox's physics engine performs and integrating new dynamics.

For instance, we recently added water and buoyancy simulation to Roblox. We focused our implementation on clean architecture so the behavior of objects and characters in water looks and feels like a natural extension of Roblox's physics. This included integrating buoyancy into our standard physics pipeline; we consider a body of water to be a physics object and apply buoyancy to floating objects via the contact (or collision) between them and the water. Collisions between water and floater, floater and floater, and floater and sunken objects are all simulated in a unified engine.

Our architecture also unifies all the forces -- buoyancy, water viscosity (drag) force, water-flow force, gravity, contact forces and other external forces. The movement of a floating object is a net result of all these forces on a rigid body following Newtonian laws.

We also implemented water and buoyancy simulation with a high level of detail. For example, think about dropping a cube into water. After gravity has submerged it in water, it's likely going to tumble and re-orient itself as the water's buoyancy forces it back to the surface. In Roblox, we simulate that re-orientation by dividing the cube into eight voxels, each of which has its own buoyancy interpolator.

By voxelizing the force of buoyancy on floating objects (cubes, wedges and corner wedges), they orient themselves properly when stabilized and respond accurately to uneven external forces, such as the pressure caused by a player standing on one corner. We also apply water viscosity force against both linear and rotational velocity to dampen the motion and add realism.

Another example: Our advanced water physics make a fine distinction between cross-section area and tangent surface area when we calculate water viscosity force on floating objects. In this demo video, we don't apply any cheating forces or velocities to the boat body. Our engine simulates the actual interaction between the motorized paddles and the water surface to propel the boat. You can see that the thin boat travels faster than thick boat, even though both of them have the same submerged volume. The boats interact with other objects in the water, an example of our unified simulation of advanced water physics and rigid-body dynamics.

In Roblox, the final orientation of a voxel cube is affected by its density, as it would be in the real world.

Our water and buoyancy simulation facilitate a wide variety of practical applications, from boat modeling to real, water-fueled propellers. We've successfully created these, but believe our users will find ways to improve our primitive designs.

Future Evolution

Roblox is built on a comprehensive, realistic physics engine. It's a fundamental part of our platform, bringing versatility and intuitiveness to the gameplay and game-creation experiences. While water and buoyancy physics represent a significant advance, facilitated by the efficiency of Assemblies and distributed physics, our vision is to continue optimizing Roblox's physics engine so it can handle interactions between millions of parts and hundreds of players.

With such advanced physics simulation, Roblox users will be able to build anything they want in a massively multiplayer, online world, where dreams and reality converge.

Until then, the evolution continues.