generalrelativity

At OMGPOP, I’m working on a physics-based, real-time multiplayer game. Keeping a user-run simulation synchronized is a difficult (read: impossible) challenge. I’m fairly happy with the result, so I thought I’d share the idea and logic behind the networked simulation synchronization pipeline.

The model on the end user application consists of the current player and a list of all other players in the match. Each player is a subclass of a MovableElement type which defines relevant properties:

MovableElement
{
    //position
    public var x:Number;
    public var y:Number;
 
    //velocity
    public var vx:Number;
    public var vy:Number;
 
    //angular velocity
    public var av:Number;
}

Each user runs a copy of the simulation locally. Because frame rate can vary so drastically from machine to machine, it’s necessary to advance the simulation by a dynamic time-step. This introduced a problem in the collision detection scheme, as a large enough time-step would allow the character to tunnel through the floor without intersection being detected. As per the previous post, collision detection occurs between a circle and a line segment. To guarantee tunneling does not occur (without a true continuous solution, and thus a rewrite), I had to ensure that the time-step was small enough that any change in position was less than the circle’s radius:

max Δt = (r - λ) / ||v||

Where r is the circle’s radius, λ an error term to ensure we’re working with less than the radius, and v is the linear velocity of the circle in question.

Here is the main simulation loop, including solving for the maximum allowed time-step, without any opponent input:

//solve for dt
var dt:Number = synchronizedTime - lastTime;
 
//ActionScript does not throw a divide by zero error- max will be positive infinity if speed = 0
var max:Number = ( currentPlayer.radius - 1e-8 ) / currentPlayer.velocity.magnitude;
 
physicsEngine.step( dt, max );//ensures we never take a sub-step larger than max
 
lastTime += dt;

Now, when a user changes input (through key presses) and thus applies forces to their character, a notification must be sent to everyone with the current physical state of the sending player’s character; alongside a list of keys being pressed and a timestamp. Upon receipt of the character state, the corresponding player is updated on the receiver’s end, and the simulation is rewound to the time the sending player changed inputs, and then re-simulated over the latent time for just that player, according to the new set of inputs (which map to forces applied remotely to all opponents). This looks something like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

private function onUserUpdatedRemotely( event:CharacterUpdateEvent ) : void
{
 
    var s:PlayerState = event.playerState;
    //find the local instance of the remote player who has updated
    var updatedOpponent:MovableElement = playerMap[ event.characterID ];
 
    //copy the state
    updatedOpponent.x = s.x;
    updatedOpponent.y = s.y;
    updatedOpponent.vx = s.vx; 
    updatedOpponent.vy = s.vy;
    updatedOpponent.av = s.av;
 
    //update forces being applied to opponent
    remoteKeyMapper.updateForces( updatedOpponent, event.keyList );
 
    //solve for change in time and advance just this opponent
    var dt:Number = synchronizedTime - event.updateTime;
    physicsEngine.stepSingleElement( updatedOpponent, dt );
 
}

And that’s pretty much it- very simple. All the hard work is writing a clean model and tight logic so that it doesn’t become a heaping pile of updates here and events there, etc.