Idea for better high-latency multiplayer support

[Patchman]

This is only an idea, and I'm not sure how well it would work in reality.

As anyone who's familiar with TTD's networking protocol knows, the problem with high-latency TTD games is that for every player action and for each engine tick, TTD sends a synchronization packet to the other player and waits for the ACK packet to come back. This allows TTD to remain in sync all the time. However, it also means that an engine tick takes at least twice the latency of the connection, so for a 50 ms connection there's at least a 100 ms wait for each engine tick. Normally the engine tick is 27 ms, so that means the game is four times slower.

Now my idea to improve that is the following: instead of executing player actions and synching them right away, queue them and assign a future engine tick to them. Then do the synching in the background, and as long as both players know when to execute the action, the games will remain in sync.

This would mean that the engine ticks can be 27 ms, no matter how slow the connection is. It also means that a player action will not be carried out right away, but rather with some delay, and this delay would be the time required to sync the action across both computers. Probably something like twice or four times the latency. I think this is still many times better than having to wait that long and the game stopping for all that time.

Basically when a player does something, you'd do the following
1) Check whether the action is possible, if not abort
2) Queue the action for tick now+n, where n is something that the player either inputs or is determined automatically from measuring the latency
3) Send the action to the other computer, including the tick for which you've queued it, and wait for an ACK
4) (Not sure if this is necessary, somebody who's got more experience with networking might know better.) Send an ACK-ACK so that the other computer knows you've received the ACK and know that both computers know now when to execute that action.
5) In the designated engine tick, check whether the action was synched properly. If not synched, halt the engine at this point until the sync is successful. Then execute the action at the beginning of the player's turn. Make sure to test again whether it's possible, and if not, warn the player and discard it.

This way, actions are still executed on both computers in the same engine tick, and the games will remain in sync at all times. In the case where the engine tick was too optimistic (e.g. sudden packet losses, connection suddenly deteriorates), the game will simply pause, just like it would've done without this improvement. In that case, one may want to either adjust the number of ticks that actions are queued ahead, or hope that it gets better.

I think this should work quite well, but I'm not going to try and put it in TTDPatch*, so I thought I'd suggest it here

[* I might try if it turns out that it really does work well, perhaps.]

[Vurlix]

Thanks for the suggestion. I will be attempting this.

[MadEgg]

But this would mean that if anyone on the first machine builds anything, it gets checked for validity and then sent to the other machine.

What if, on the other machine, the other player tries to execute the same action? Like both trying to build a railroad track in one specific tile.
If I get your idea right, that would mean that the first player would always get what we wants and the other has to hope he's not trying to do something the other player wants.

BTW, you said the original method meant the game was in sync always, but just 4 times as slow. I've tried it lots of times and most of the times, the games did not stay synced, but they both started inventing their own subisidie offers, new industries and industrie closures.

I think only one machine needs to do that kind of stuff and send it to the others instead of all trying to do it and then checking if they did the same. Or maybe even a client/server interface. That would mean player can join in the middle of a game, and for that, OpenTTD is enormously suitable.

You could enter a server, take over a company of another player who wants to stop playing, or just start your own. In that case, there should be a slight compensation to make up for the time they lost, like more starting money.

Now that I think about it, Client/Server would rock the most for this game, it would be extremely cool if it would be that way. Unfortunately it's probably also the hardest way to implement multiplayer the way the current code is.

[Korenn]

But this would mean that if anyone on the first machine builds anything, it gets checked for validity and then sent to the other machine.

What if, on the other machine, the other player tries to execute the same action? Like both trying to build a railroad track in one specific tile.
If I get your idea right, that would mean that the first player would always get what we wants and the other has to hope he's not trying to do something the other player wants.

BTW, you said the original method meant the game was in sync always, but just 4 times as slow. I've tried it lots of times and most of the times, the games did not stay synced, but they both started inventing their own subisidie offers, new industries and industrie closures.

I think only one machine needs to do that kind of stuff and send it to the others instead of all trying to do it and then checking if they did the same. Or maybe even a client/server interface. That would mean player can join in the middle of a game, and for that, OpenTTD is enormously suitable.

You could enter a server, take over a company of another player who wants to stop playing, or just start your own. In that case, there should be a slight compensation to make up for the time they lost, like more starting money.

Now that I think about it, Client/Server would rock the most for this game, it would be extremely cool if it would be that way. Unfortunately it's probably also the hardest way to implement multiplayer the way the current code is.

Sinaasappel and me did some thinking about this as well. (Well...more like general ranting )
Perhaps it would not be that hard to make a dedicated server for ttd? one that does all the decisions and keeps record, without any graphical stuff. This would allow games that are desynced to get resynced by the server, which has the prevalating information. Perhaps this would allow more than 2 player games, since only the server needs to send out the large amounts of packets, not the clients.

And perhaps there should be something done about the whole "force synced" system. If clients are allowed to desync small amounts of time, the server could periodically enforce its view of the world, which would perhaps mean a few teleporting trucks, but would this would allow games to play during lag times.

[guyver6]

In this moment I'm working on network code for OpenTTD (I'm not responsible for it, but if I'll show something maybe devteam will let me do it). It's design is based upon client-server architecture and server keeps the one and only true version of game being played. As for now there are max player limit set to 8 but it's just a matter of changing one #define. And I discussed this with developers, that more than 8 isn't needed.

For running a game with more than two players it is needed to have bigger maps thou (imagine 4 players playing on standard 256x256 map ).

For current development status of my netcode my primary goal is to have stable connection between server and clients, and I have some design notes about synchronization and packets transmission. The major synchronization tick is being planned by me every 100-150 game ticks

Feel free to share your ideas about network code and protocols. I would appreciate any help, as current development team is busy with bugfixing and feature-riching OpenTTD.

Guyver

PS. I'm on OpenTTD's official ( ) irc channel #openttd at irc.freenode.net.

[Bjarni]

I vote for including teleporting trucks

A little more serious, I think it is a good idea to have a server, is have the game and can force sync on the clients. There should not be great jumps since the client will accelrate the truck like the server, even if the connection lacks.
The other problem with two people placing a rail in the same tile at the same time is also fixed, since the tile owner will be the one, who the server revieves first and the other one is forced in sync.

[Korenn]

[snip]
For current development status of my netcode my primary goal is to have stable connection between server and clients, and I have some design notes about synchronization and packets transmission. The major synchronization tick is being planned by me every 100-150 game ticks

Feel free to share your ideas about network code and protocols. I would appreciate any help, as current development team is busy with bugfixing and feature-riching OpenTTD.

Guyver

PS. I'm on OpenTTD's official ( ) irc channel #openttd at irc.freenode.net.

Some thoughts: if you have a "master tick" every 100 - 150 game ticks you can leave out the normal acknowledging. This would allow you to use UDP or another like protocol which focusses on speedy delivery without guarantees. And this would mean a seriously better connection in terms of lag.

and 8 player ttd? You're gonna have to totally rewrite the whole communication setup then, because currently even 3 players generates such a load of communication traffic that it's unplayable. (wheee slide show)

Bjarni: exactly.

[TBOT]

... the server could periodically enforce its view of the world, ...

Problem is that you can't 'enforce' it in a flash, sending the entire game structure would require to transfer about the size of a savegame file I guess (for plain TTD about 300-350 KB IIRC?).
A possible solution for this would be to continuosly (sp. ?) sync the world (e.g. every tick you would sync a vehicle/map tile/etc.), and of course sync when something changes through a player action.
Quite huge desyncs could still occur though (depending on the rate with which things are synced).

[Korenn]

The server shouldn't send the whole world-datastructure but only the delta from the last sync. This would include all vehicle positions and any map changes, so it would still be quite large. Streaming it would become very difficult because the data will be outdated before it's even half-finished... No idea how other games do this...

[guyver6]

Korenn: I think that UDP is amazing thing, but in the world of real time shooters, and it will not be suitable for OpenTTD becouse:
- We need to be sure, that every single packet is delivered from server to client (the other way it doesn't matter, becouse in approach I've taken client can't do anything without ACK from server, and for now ACK packet is 12 bytes long)
- UDP is being used, but as a connecting gate (client sends connection request to UDP port on server, server decides to what port connect client, binds that port and reserves that port to that particular client, then when something comes out from this socket, server accept()s connection, checks if it is that client who requested connection to TCP port, then if not it disconnects that client, if it is ok, then it sets client slot as connected and keeps connection with that client)
- If client sends request that it want's to bulid something, then he waits for reply from server, and server must ACK that it's possible or not to do it. If UDP packet gets lost, client has to resend it, TCP doesn't have that flaw (if it's diffrent tell me, i'm beginner if it comes to network programming ).

Why not 8 players? I mean, if simulation is being run on every machine separetly, and just CMDs are being sent, that's not so bad for bandwidth.

And there's being planned resynchronizating mechanism (server holds the one and true game, right?).

Guyver

[guyver6]

And if there're questions why i'm programming such complicated solution to connect to server, it's becouse devteam decided that it should be in it's final shape something similar to bnet (worms3d, generals online), chat where you meat other players, and where you setup your multiplayer game.

Guyver

[Patchman]

But this would mean that if anyone on the first machine builds anything, it gets checked for validity and then sent to the other machine.

What if, on the other machine, the other player tries to execute the same action? Like both trying to build a railroad track in one specific tile.
If I get your idea right, that would mean that the first player would always get what we wants and the other has to hope he's not trying to do something the other player wants.

Whoever does the click first gets to do it. If player1 tries to do the same after player2 but before the action is carried out, then it will be queued at a later engine tick, by which time player2's action will have been carried out already.

Basically, whoever clicks first gets to do it, and that's the fairest way there is. The only disadvantage is that you don't see right away if it really was successful.

A possible solution for this would be to continuosly (sp. ?) sync the world (e.g. every tick you would sync a vehicle/map tile/etc.), and of course sync when something changes through a player action.
Quite huge desyncs could still occur though (depending on the rate with which things are synced).

That's exactly what TTD does... keep both worlds in sync by transmitting what the player does and executing it on both computers at the same time.

With TTDPatch 2.0.1 alpha 10, there are no desynchs in multiplayer games at all if you don't try to bribe the authorities. That's the only thing that causes desynchs. So basically this mechanism works fine once you fix the bugs (and there were a few bugs in both TTD and TTDPatch causing desynchs).

I think because (Open)TTD's world is so complex, that's really the only way to do it, you can't resynch a game without transmitting the whole gamedata because so many things are inter-related.

[Korenn]

[UDP specifics]

I have no actual experience using UDP, so it was just a suggestion
TCP/IP guarantees that the message gets sent, but no garantuee that it will take less than half an hour...

Maybe UDP is a bad idea, but what I meant is that you effectively stream the actions from server to client, and any lost data will be corrected when doing a "resync" update. screw Ack's, those take too long (like Patchman's suggested idea, that will introduce a constant MINIMAL lag)
client to server info can be normal ack-ed communication, since it will be a lot less (only 1 players' actions versus all other players').

I think it will make things a lot easier by assuming that the game will be desynced and finding a solution, then trying to prevent the desync to happen, which over the internet is impossible.

[TBOT]

- We need to be sure, that every single packet is delivered from server to client (the other way it doesn't matter, becouse in approach I've taken client can't do anything without ACK from server, and for now ACK packet is 12 bytes long)

I wonder why you should need that. If you choose the data in your packet correctly you should be able to do without reliable transfer.
In situations with high packet loss TCP just isn't your best choice, since it _will_ wait for retransmissions...

[guyver6]

Korenn: You're right, desynchs has to be fixed when they occure, and I'm not going to search for solution that prevents from desynchs. Therefore there's a need for fast synching desynchronized client, becouse, sending whole game state (savegame) everytime someone desynchs is not the way to go.

TBOT: By ACK packet I mean packet, that allows client to execute command. Without that acknowledgement it's impossible to let client build/buldoze/buy/sell/anything that has some influance on game.

I'm not so experienced in network coding, so if someone willing to help, I'd be greatful.

Guyver

[Korenn]

Whoever does the click first gets to do it. If player1 tries to do the same after player2 but before the action is carried out, then it will be queued at a later engine tick, by which time player2's action will have been carried out already.

Basically, whoever clicks first gets to do it, and that's the fairest way there is. The only disadvantage is that you don't see right away if it really was successful.

Why does player 1 have to wait to see if his actions work before doing other things? Assume a high lag situation:

Player 1 builds a piece of track. His ttd evaluates if this is possible, and concludes it is. So, it displays the built track and sends the command to the server. The player can continue to do things while the client waits for an acknowledgement, all actions are processed in the same way.
The server recieves the action, checks if it is possible, concludes that just a moment before the opponent built a track there, and sends a no reply to the client, with some contextual data (like the opponent's track).
The client recieves the server reply and updates its view according to the server response, and displays the standard error message "can't build here, track owned by blablabla". Now the player will be cursing the opponent because his railway misses a piece, but who cares .

Effectively this has the same amount of lag as waiting for an acknowledgement, but the user won't notice unless there's a conflict.

[Patchman]

Why does player 1 have to wait to see if his actions work before doing other things?

He doesn't have to wait, but you can't execute actions in general without making sure they happen in both engines in the same tick. Otherwise the game would desynch.

He can happily give more orders for construction, they just won't all be carried out right away. Then if one doesn't work later, he'll have to go back and fix it.

My idea to fix this would keep the symmetry between the players and not give one player an advantage over the other.

[Korenn]

Korenn: You're right, desynchs has to be fixed when they occure, and I'm not going to search for solution that prevents from desynchs. Therefore there's a need for fast synching desynchronized client, becouse, sending whole game state (savegame) everytime someone desynchs is not the way to go.

TBOT: By ACK packet I mean packet, that allows client to execute command. Without that acknowledgement it's impossible to let client build/buldoze/buy/sell/anything that has some influance on game.

I'm not so experienced in network coding, so if someone willing to help, I'd be greatful.

Guyver

I major in architecture of distributed systems, but I'm seeing enough network stuff not to want to do it at home Besides my experience is with Corba and webservices and the like, which don't really depend on speed

my idea:

The server would never need to send the whole gamedata, since every user(client) will have (will need to have) a copy of the last synced game situation. The server only needs to send delta's of the last synced situation, and does not even need to do this for everything all the time (you could update vehicles more often than for instance the map data). Theoretically the client can show some pretty weird things this way, but that does not matter since the server will have the correct and flawless data that it will use to update its clients, so eventually any mistakes get corrected. Clients could even request certain data from the server that they need to display the game, if needed (like the tracks for a train that's apparently following some non existent route).

[Korenn]

Why does player 1 have to wait to see if his actions work before doing other things?

He doesn't have to wait, but you can't execute actions in general without making sure they happen in both engines in the same tick. Otherwise the game would desynch.

He can happily give more orders for construction, they just won't all be carried out right away. Then if one doesn't work later, he'll have to go back and fix it.

My idea to fix this would keep the symmetry between the players and not give one player an advantage over the other.

Ok I understand that, my idea fits more to a dedicated server setup, where the server has no possible use for any advantage.

[guyver6]

The server only needs to send delta's of the last synced situation, and does not even need to do this for everything all the time (you could update vehicles more often than for instance the map data). Theoretically the client can show some pretty weird things this way, but that does not matter since the server will have the correct and flawless data that it will use to update its clients, so eventually any mistakes get corrected. Clients could even request certain data from the server that they need to display the game, if needed (like the tracks for a train that's apparently following some non existent route).

And with sending vehicles data there's following problem: one veh takes 112 bytes, max vehs on map is 640 (right now, and it's gonna change), this gives us something like 72 kb to send with only veh data. Of course not every thing of this 112 bytes needs to be sent, but even if we take quater of this 72kbs, we have amount of data that's too big to send in realtime. Updating some vehs per tick is better solution, and I'm thinking of it right now.

Guyver

Edit:
And no queue is possible, becouse server would need to simulate backward events (at the tick they were generated), and that's not what we want.