2008年06月04日
Bucket Synchronization
A while ago a VRML 3d network game called MiMaze was released. What made it different from other network games was it’s fully distributed (p2p) network architecture.
Distributed architectures have advantages such as scalability, no central point of failure, and lower latency because there is no central server.
Since there is no central server in distributed architectures each client must maintain a game world that is consistent with all other players sharing that world. The problem with that is the world can easily become desynchronized because events from other players arrive out of order. This can be caused from lag, latency or many other reasons.
Let’s look at the left side of figure A. This represents a situation with no latency. Player A and B are equally distant from an object. If A shoots the object at time T1 and B shoots object at T2 , Player A will hit the object and Player B will miss it because it was already knocked down by Player A.
Now look at the right side of figure A. If it requires more time for the “A shot the object” to reach B, than the difference in time of when A and B shoot, the results would look different. B would shoot the object at T2 but not having received A’s shot packet till after T2 would mean that in B’s world B would have hit object first and A would have missed. But on A’s world it would look like A hit the object and B missed.
MiMaze avoided this problem by using a technique called Bucket Synchronization derived from a simpler network technique called Lockstep. In Bucket Synchronization we only process events at certain discrete timesteps called buckets as opposed to immediately. All events that occur between these buckets are queued up into the bucket assigned to that time interval.
The important thing is that events are delayed to later buckets using a “delay synchronization time” and events received from other players over the network are stored in the bucket assigned to that time interval it was assigned to originally. This allows all clients to get all events from other clients before updating their world state. You can think of it as a “wait for game sychronization time”. The delay synchronization time is usually calculated by the highest latency amongst the players plus some buffer time. This is a bit confusing so I’ll show you one example.
For example a game with
- 50ms bucket interval
- 100 ms delay synchronization
50 100 150 200 250
A–L–B–R–C—–D—–E
Local packet “L”is created at 75ms. It would be delayed to d(L) = time created(75ms) + delay sync time(100ms) = 175ms. Which would place it between C and D. The bucket assigned to that interval would be D.
For a remote packet we take the time it was created locally R (125ms) and add the sync delay time (100ms + 175ms = 225ms). So this packet would go into E.
Figure B represents the same situation as figure A but with Bucket Synchronization. The grey boxes represent the buckets, the black dotted arrows represent which bucket the event is placed into and the red dotted arrows represent the delay synchronization time.
At T2 Player B creates a local shoot event, which is queued up into bucket D. After that, player B receives the network event from player A which is queued up immediately into bucket C. C is then processed and A registers a hit. Bucket D is processed next but since A’s event was processed first in bucket C, B’s event registers a miss. The results are now consistent for both clients.
If more that one event is in a bucket we can determine the order or processing events using a timestamp.
A few questions that might pop into your head are, “Won’t the client feel lag if the input isn’t processed immediately?” and “What happens if the lag is greater that the delay synchronization time?”
It’s true that if you delay the reaction of the input the player will feel some lag. This technique is not suited for fast FPS games but better for slower strategy or turn based games in which the delay can be masked with tricks like winding up animations.
If the lag > delay synchronization time then we have to throw the packet away because it’s not valid anymore. MiMaze compensated for this by using Dead Reckoning to extrapolate the next state based on the last valid message. Another form of this technique called Breathing Bucket Synchronization tries to solve this by calculating the synchronization delay dynamically based on the latency of received packets.
Bucket Synchronization is also useful for network games which are completely driven by input. Age of Empires used a method similar to this to drive their network games.
I created a sample app to demonstrate this concept. There are two worlds and each world has one main player, one proxy and one local game object. The red player is the local player on the left side and the green player on the right side. When you hit a fire button the red or green player will create a local event to destroy the white object. You can see who hits it first and who misses. Next to them is a white line where you can look at the buckets. The red dots represent local events and the blue dots represent events from remote players. Try adjusting the parameters and see what happens.
As always the source code can be downloaded here.
Further reading
Design and Evaluation of MiMaze, a Multi-player Game on the Internet
Laurent GAUTIER and Christophe DIOT
INRIA Sophia Antipolis (http://www.inria.fr/rodeo/)
On the Design of Multiplayer Online Video Game Systems
Chia-chun Hsu, Jim Ling, Qing Li and C.-C. Jay Kuo
Integrated Media Systems Center and Department of Electrical Engineering
University of Southern California, Los Angeles, CA 90089-2564
1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond
By Paul Bettner and Mark Terrano
Leave a Comment
Trackbacked