How to keep a data structure synchronized over a network?

Question

Context

In the game I'm working on (a sort of a point and click graphic adventure), pretty much everything that happens in the game world is controlled by an action manager that is structured a bit like:

So for instance if the result of examining an object should make the character say hello, walk a bit and then sit down, I simply spawn the following code:

var actionGroup = actionManager.CreateGroup();
actionGroup.Add(new TalkAction("Guybrush", "Hello there!");
actionGroup.Add(new WalkAction("Guybrush", new Vector2(300, 300));
actionGroup.Add(new SetAnimationAction("Guybrush", "Sit"));

This creates a new action group (an entire line in the image above) and adds it to the manager. All of the groups are executed in parallel, but actions within each group are chained together so that the second one only starts after the first one finishes. When the last action in a group finishes, the group is destroyed.

Problem

Now I need to replicate this information across a network, so that in a multiplayer session, all players see the same thing. Serializing the individual actions is not the problem. But I'm an absolute beginner when it comes to networking and I have a few questions. I think for the sake of simplicity in this discussion we can abstract the action manager component to being simply:

var actionManager = new List<List<string>>();

How should I proceed to keep the contents of the above data structure syncronized between all players?

Besides the core question, I'm also having a few other concerns related to it (i.e. all possible implications of the same problem above):

• If I use a server/client architecture (with one of the players acting as both a server and a client), and one of the clients has spawned a group of actions, should he add them directly to the manager, or only send a request to the server, which in turn will order every client to add that group?
• What about packet losses and the like? The game is deterministic, but I'm thinking that any discrepancy in the sequence of actions executed in a client could lead to inconsistent states of the world. How do I safeguard against that sort of problem?
• What if I add too many actions at once, won't that cause problems for the connection? Any way to alleviate that?

Answer 1

If I use a server/client architecture (with one of the players acting as both a server and a client), and one of the clients has spawned a group of actions, should he add them directly to the manager, or only send a request to the server, which in turn will order every client to add that group?

You have three options in this case, two of which you have already mentioned. The choice of which option you take depends on a variety of factors that only you can be the best judge of:

1: Client spawns group of actions adds them directly and then sends them to the server. The server accepts it without any checks

*Benefits of this approach are that as far as the client is concerned, their own actions gives them an instant feedback independent of the network delay. The disadvantage is that the client's messages are accepted by server as fact (which they may not be)*

2: Client sends a request to the server, which in turn broadcasts the request to everyone, including the client that originated the request.

Benefits of this approach are that the server is now is in control of everything that happens in the game which alleviates most issues with illegal activity (here illegal can range from the client clipping a wall to performing a move that is now illegal because the server has more information that the client did not have when the client made a particular move)

3: Client spawns group of actions, adds them directly and then sends them to the server. The server processes the request, runs its own checks on the actions to make sure they are not illegal, and then broadcasts the move to all players including the client.

This takes the best of both 1 and 2 at the cost of slightly more bandwidth requirements. The benefits are instant feedback to the client for their own moves and if the moves the client makes are illegal, the server takes appropriate actions (forcefully corrects the client).

What about packet losses and the like? The game is deterministic, but I'm thinking that any discrepancy in the sequence of actions executed in a client could lead to inconsistent states of the world. How do I safeguard against that sort of problem?

Packet loss and extreme lag is a hard problem to fix. Different solutions (none of them perfect) are employed to deal with the problem depending on the type of the game (e.g. dead-reckoning). I will assume you game does not have to synchronize physics.

One of the first things you should be doing is time-stamping all your moves. Your system should then take these into account and play the moves accordingly (perhaps the server has this responsibility and then deny illegal moves). When implementing this system, assume 0 latency (test locally).

0 latency is of course, not a good assumption, even on local networks, so now that all moves respect time, which time do you trust? That's where the issue of time synchronization comes into play. Many articles/papers online will guide you to solving this proiblem.

What if I add too many actions at once, won't that cause problems for the connection? Any way to alleviate that?

First the obvious stuff. Never send strings or serialized objects. Don't send messages as fast as the game itself is updating. Send them in chunks (e.g. 10 times a second). There will be error (especially rounding error) that the server/client will need to fix the errors once in a while (so every second, the server sends everything [everything = all data that is important to keep things in your game in the correct state] which the client then snaps to and/or takes into account to correct its state). EDIT: One of my colleagues mentioned that if you are using UDP [which you should, if you have lots of data] then there is no network ordering. Sending more than 10 packets a second increases the changes of the packets arriving out of order. I'll see if I can cite that claim. As for out of order packets themselves, you can either discard them or add it to your system's message/move queue which is designed to handle changes in the past to correct the present state

You should have a messaging system that relies on something that takes up very little space. If you have to send something that can only have two values, then send only one bit. If you know you can only have 256 moves, then send an unsigned char. There are various bit twiddling tricks to pack messages as tightly as possible.

Your messaging system will most likely make use of lots of enums to allow you to easily extract moves from an incoming message (I would suggest to take a look at RakNet and examples therein if you do not understand what I mean here).

I am sure you already know that you cannot fix issues that arise with hight latency and packet loss but you can make its effects less pronounced. Good luck!

EDIT: Patrick Hughes's comment above with the link renders this answer incomplete and specific to OP's question at best. I would highly suggest reading the linked topics instead