Deepest Blue Multiplayer.

I have been writing multi player games since the eighties. The essential thing is that two or more games have to play in synchronisation so that all players are playing exactly the same game. Many modern games use a server approach to deter cheating. The server runs the main instance of the game and sends information to each client player  about any game events. The server may send object positions and if the client does not agree the client tries to modify its own positions to agree with the server.

I have always preferred a simpler approach but it requires strict programming practices. That is each machine runs exactly the same game. All they send is any controls hit on the local machine, These may be real controls such as keys or mouse buttons,  or virtual controls such as a GUI button, dropdown or checkbox.

I will come back to Deepest Blue and the story of how I got the multiplayer working. First let me explain how I first implemented this technique in the good old days of Graftgold.

Gamegear.

This was the first time I had attempted a multiplayer game that linked two machines. The game gear could be linked to another using a little serial cable.  I think Superman was the first game that I added this to. Virgin asked Graftgold to provide a linked game feature. The problem was noone in the UK had ever achieved this.  SEGA provided some technical details and the rest was down to me. With a physical link at least there is no lag in sending a signal to the other machine, it is pretty instant. I used 

a simple ping pong protocol. Each machine  sent a message and expected a reply.

When  link game is chosen on each machine it checks to see if the other machine has already sent a message.  If it finds one it replies as the client. If there is no message it assumes it  is the master and tries to send a message. You have to cater for the unlikely event that both think they are the master and send the first message.  In the game cycle the master sends its keys and the client replies with its own.

The 2 games had to run exactly the same game. This is not a problem with well written code as programs are strictly determinative. That is they do exactly the same thing given the same inputs. 

 

The link proved to be very reliable. SEGA approved and actually asked for our code so it could give it to other developers.

International MOTOX

This again involved a serial connection via a lead between two machines. On the PC the big problem I had was that the CPU could be in two modes when a serial interrupt hit. It took so long flipping between modes that the pc could actually miss a whole message. Writing the serial red in both modes helped a bit but the message could come in while the machine was already changing modes to draw graphics. Whatever I did sometimes messages went missing  or caused an error so the protocol had to deal with this.

 The system I used was again a ping pong system where each machine sent in turn. If an error was read or a timeout occurred I just resent the previous sent message which triggered the appropriate reply message. I had though about sending a resend message but what if that went missing.  So having a simple message number and checking they went up sequentially solved the problem.

The other principle I use was to store key presses in a buffer so I could read a few cycles in advance.

In the solo game keys were fed from the buffer to the game. In the linked game keys went from the buffer to the link  message then to the other machine.  This abstraction of the game key read made it easier to implement. It also allowed the key buffers to be saved then reloaded for an action replay. This proved really useful in game testing as we could go back and replay a situation to examine an error.

An issue with pc's at the processing and graphics power could be very different..  Reading the keys a few cycles ahead helped a bit but also the game could drop a  frame display to try to keep the game rate at an acceptable rate.   

I remember a tricky issue where the games would play in sync for a while then the action would diverge. To solve this I ran the game twice on the same machine and compared positions every cycle. It turned out that a bit of code to add more bits of mud on a faster machine used a random number. This put the random numbers out of sync so decisions eventually were different on the two instances of the game. 

I spent many a late night trying to make the same system work on the Playstation version. We had technical information from Sony about the link and a sample program that just sent one word of data between the two machines. I could get that working fine but before a race started I had to transmit a block of data for all the bike and player details. I only managed to get this working once and just could not see what the problem was. The documentation was not clear, it often had errors in translation. It might say "never set this bit for so and so" but  meant to say " always set this bit". When you have several such bits you had to try all permutations to see which worked. In the end I ran out of time and I still I not know why I had it working one night then next time it did not. The SONY tech guys could not help or put me in touch with anyone who had got it working. I suppose I could have send the data a word per cycle which would have caused a small delay before the game started.

Deepest Blue.

So that gives a bit of background of the design decisions of the Deepest Blue multiplayer. When I left Graftgold I had worked on a commercial networked system and completely rewritten the communications layer to make it fast and reliable.  So I had a really good background in sockets programming.

I put in key buffer at the start of programming the game. I also designed an event system so anything a player chose to do using GUI controls could be buffered and supplied to the game with the correct set of keys. Then for the link game the events and the keys could be sent to a server. Then the server could collect all the clients keys and events and supply them to all machines.  I used the read ahead principle even in the solo game so the game was tuned up to use keys a few cycles old.

I had to redesign the multiplayer game forms to use the Steam lobby interface. So one p-layer creates a lobby and chooses a game to play and how many players are wanted. Then clients can join the lobby. Finally the lobby owner can start the game.

 It took a long time to get the communications fast enough. The lag time even on a local network was just too much. I(n the end I revised my communications layer to use a worker thread and callbacks rather than having to keep asking each cycle for messages at set intervals. So when a message comes in the worker thread immediately uses the callback to inform the game the keys have arrived. This was especially important for the server that collected the key messages. It meant it could send the completed keys package.to the clients almost immediately cutting the lag significantly. It was still not fast enough, in the end I also  decided to input the keys every other game cycle to give the process slightly longer leeway. I finally got it working at 60FPS.

Then came the difficult bit. In theory the games  should have run identically but they diverged pretty quickly. I remembered the issue with MOTOX so compared the random numbers used for game decisions. They indeed went out of line after a few thousand calls. I had a separate random seed for every sector and another for graphical effects that could differ on machines. The random seed changes with every random number that is used. In Deepest Blue the seed is just an index into a fixed pre-set table of random numbers. That makes it very fast.  I mix the numbers up a bit by adding different values to the index. A searched and checked every use of a random number. I searched for all uses of random numbers and found a couple of times I had used the wrong seed.

The game still diverged after a while and the random numbers were this time time in sync until after the divergence. So I had to track down the cause.  I added code to send a hash of each ships positi0on each time they changed action. The server sent this to the client which checked against a buffered hash from the same input cycle.  I could thus detect what the ship was do0ing when it was found to be different.  Although I could stop the game when a difference occurred it was little help as the difference was a few cycles ago. Instead I stopped both games so I could look at the log reports I generated. These detailed every ships change of action so I could see what they were doing.

Then I looked at that routine to check it was strictly determinative.  There are only a few ways code can do different things. One is that there is an undetected error so data is read from an unset variable. These issues are usually found by the compiler and shown as a warning. I religiously get rid of warnings but sometimes in a routine with conditional processing the compiler misses them.  I realised I was getting the error when a ship suffered damage. It turned out I was using a variable I had not always set up.  So when any future divergence appeared I knew to check that all variables were set up.

Getting better but still an occasional divergence appeared. I had to use quite a bit of detective work to get to the culprit. The ships were getting slightly out of line. If I left the player ships alone I did not get the same problem. I searched for all uses of the current camera location to check it was never used in game processing. I suspected bullet processing as it seemed to occur while I was watching combat. I hand checked the bullet routines and found one naughty reference to the currently displayed sector.

Still the games diverged during combat.  I put in a test after each collision event and sure enough after a bullet collision things could differ. Next I tried to compare positions of bullets but there were too many to send. So I compared positions of bullets when a collision event with a bullet occurred.  I noticed it was always a certain class of bullet so checked for any special processing I could find none. I checked the bullets start positions and directions but everything seemed the same. I went back to the data table that specified the bullets properties. Something must be different for that bullet class. I found within the data table I had missed a number. The compiler does not warn if you do not put enough entries.( I do not like the way data is specified in C. You type a comma separated list of values and it is too easy to get them out of step. I usually try to use tabs to align all the elements but if they are very different lengths this can make the lines too long to easily look at. The editor ought to allow a little Excel type table with typed columns and headings.)

It seems stable now but needs much more testing to be sure. At least the game plays itself when I set each player ship to be flown by the co-pilot.   That means I can start a multiplayer game off and just let it run until it finds a difference. Then I have to investigate and maybe add more data to narrow down the code that causes the issue.  The problem with an open world game is that objects are effected by other objects and a butterfly effect of causation happens. For example a bullets position is determined by the 

firer then maybe the target. A large bullet can impact and effect a ships position. Ship can collide with other ships, asteroids etc. I have to work back and find the first thing that diverges. When I suspect an object I can be more specific and put more tests to determine the cause. That may lead me to other objects. So key to my testing is the moment of interaction between objects, usually some kind of collision. However object can be affected by others by simply heading towards them. 

During this bout of testing it occurred to me that all testing really boiled down to checking code is actually determinative and should do what it is expected to do , the same each time. It could be a way to catch sporadic errors difficult to find by running several instances of the same code and checking for differences.  

Deepest Blue is in pre release (without the multiplayer game) on Steam.

Deepest Blue on Steam