It can't be really lockstep then could it? Or did I mis-interpreted the term lockstep? (With lockstep I assume no states are being updated until everyone has updated the same state for the same timeframe). If you would continue anyways and find out you miss predicted some state at timeframe x, would you roll back or something?

Well, our model is something that you can develop if you start out thinking everything is lock-step, but then you want to make sure that the locally controlled client doesn't have to delay for everyone else's input. We have to manage "what" happens "when" on each client (and stay authoritative on the server) -- kind of like running a separate lock-step simulation for each separate object, and then being very careful in the interface between them.

Quote:

Well, our model is something that you can develop if you start out thinking everything is lock-step, but then you want to make sure that the locally controlled client doesn't have to delay for everyone else's input. We have to manage "what" happens "when" on each client (and stay authoritative on the server) -- kind of like running a separate lock-step simulation for each separate object, and then being very careful in the interface between them.

Hmmm Im still not sure Im getting this :s

So in the end nobody will wait for each other's input, so predictions must be made? Or aren't there any shared objects between players which they can interact with? Could you please explain the notion of lockstep a bit more as used in that model? It definatly sounds interesting but I can't think of any way of running seperate lockstep simulations and still have an interactive simulation without it being just a traditional deadreckoned simulation...

Quote:

So in the end nobody will wait for each other's input, so predictions must be made?

There are cases where you can't lock-step without latency. For example, if there's a gold coin on the ground, and you and I are both close to the gold coin, and try to pick it up, and picking up is an "instant" action (like avatar movement), then both of our clients will predict that we get the coin. The server will break the tie (one of us gets the coin) and ends up sending a correction to the other. The amount of time that you may get corrected for is the same as the round-trip time between you and the server.

Another option to solve the same problem (rather than sending corrections and time travel) is to design latencies into actions. If picking up was an action that took 500 milliseconds, then the server will break the tie before any one of us actually ends up picking up the thing. We've designed our system such that we keep enough state for time travel that both of us could be on separate continents, playing on a server in a third continent, over dial-up modems, and the system will still work. That takes a bit of memory, but our take on that is that memory on the clients is cheaper than bits of bandwidth.

In our model, for each kind of interaction, you can choose points along this spectrum of instantaneous-with-possible-timetravel through latency-and-guarateed-consistent. For things that are unlikely to have contention (avatar movement), clearly choose the instant response. For things that involve many players (applying brakes to a train, or puching the "go" button on an elevator), you sometimes choose to accept some latency, and hide it with feedback animations/sounds.

Ah ok, thanks for clearing that up!

So basicly you have a hybrid of predicted & lockstep events in There... cool :)

So basically lockstep means "parallel simulation of the game state on all client machines"?

Some time ago, I designed a multiplayer algorithm which worked roughly as follows: each client would have its own "belief state" of the world which it simulates, and the server would have the "real state" of the world, which it then spreads to the clients (not the whole world-state per frame, just a little update), so the clients' belief states are kept at sync. This keeps traffic relatively low and is quite general. Does this algorithm have a name?

-- Mikko

Sounds a lot like like "baselining" -- ie, you send user inputs (or deltas) as your typical means of sending updates (I e, "player fired a bullet") but you cycle through all the state and send periodical full state snapshots for objects, so that an object will know that it always receives the sync-ed data every X seconds.

You don't describe how you make sure that quick interactions (jump, shoot, etc) go to the clients quickly, rather than waiting for the potentially long cycle time, though, so it's hard to tell how close it is.