This document is Copyrighted 1996 by Kali, Inc. You may make copies of this file and provide this text to anyone wanting to know more about writing games that work better over the internet, but you must include this entire text without any changes. You may not copy any part of this document without prior written consent from Kali, Inc.

This is just a beginning. There is a ton of information that can be included in this text, but it will take quite awhile to gather everything together. If you have anything to contribute please contact Kali by sending email to jay@kali.net.

Not much yet. Just some basics on how to layout your network communications. We have not added any IPX or TCP/IP specific information yet. Everything in this document applies to either system. So far we're just explaining why some games work better over Kali.

Generally you should not write applications that depend on the use of broadcast packets for anything except finding other nodes that are already running the game. Any existing nodes should respond to the broadcast packets by directing a packet to the sending node. After this exchange is made both nodes know the address of the other. There is no longer a need to send any broadcast packets. Any new nodes will send a broadcast that all of the existing nodes can respond to. Because packets might be lost never assume that one broadcast packet will reach every node. It might be necessary for each node to compare lists when connecting to be sure they agree on who's present. Each node is responsible for maintaining their own list of nodes.

One system that works is to have a new node broadcast a message to see who is present already. In the event that no other nodes are present this node should continue to send a broadcast every 2 seconds while also listening for other broadcasts. Any node that receives a broadcast message should reply to the sender with a message indicating that they are present and also provide a list of other nodes already in that user's list. This way even if the new node doesn't get a response from all existing nodes, he'll still have a complete list as reported by one of the existing nodes. In order to assure that each existing node is aware of the newcomers the new node must direct a message to any node that is on his list (the list built from the responses to the broadcast packet) to say "I'm here!". He must also make a reasonable effort to contact this other node.

Resending a packet every 2 seconds for 20 seconds before giving up and assuming the other node is dead.

You don't have to get this complicated, but this is the only way to ensure that a set of players remains intact even if any of them disconnect without notice.

A simpler model, and the one used by most games is to have nodes specified as either hosts or clients. A host doesn't send any broadcasts, but rather creates a game and waits for others to join. As nodes join he adds each node's address to his list and then polls these addresses on a regular bases to make sure they haven't disconnected unexpectedly. A player trying to join will broadcast packets asking for games. All current hosts will respond with game information. The person joining then gets a list of all current games and can choose one. He continues to re-broadcast every 2 seconds or so until either exiting or choosing a game. Upon choosing a game he sends a packet requesting permission to join directly to the node that offered the game. From then on all packets are directed. When the game launches all nodes can still be considered peers, but the host will be responsible for providing the initial game startup information (including the list of nodes).

Descent is unsynchronized. Basically each node just plays at full speed and sends packets about 5-10 times per second to indicate position. When weapons are fired, objects are picked up, or a collision occurs an extra packet is sent which includes this info.

Each node listens for packets from other players and when packets are dropped or late it makes a guess as to where they are based on their last location and trajectory. Descent will continue to guess at locations for up to 4 seconds. Each node keeps track of his own version of the game.

Because of this guesswork each player might actually see different objects and different scores. Sometimes two people are able to pick up the same object which tends to cause weapons to build up until there are lots of extras lying around. Recent changes to the code fix it so that each PC knows where each object is supposed to be available and it will reduce the number of available weapons when too many appear.

Warcraft 2 is totally different. It's a synchronized game. This insures that all players see the same thing and that all scores match exactly. To allow this to work and still run fast over the internet they delay actions by a value which can be set by the user on the command line.

With War2 there is a commandline option to adjust a delay for the other nodes to have time to respond. When increased, War2 will do something like this:

1. The game runs on all nodes at full speed. Packets are sent at a regular interval to make sure everyone is still connected. There is data in the packets, but echnically until a user issues an order there is no need to send any real data. Just a frame number and possibly a time stamp that can be sent and returned for adjusting for lag. This packet can also contain a value that indicates the last command received from the remote node. This way the remote node will know everyone received his command without having to issue an extra ack (acknowledgement) packet.
   
   
2. The user commands a grunt to move. We're talking about the final command to move...not just the first click to select the Grunt or the scanning of the map for grunts.
   
   
3. War2 immediately sends a copy of the command to all nodes and then places this command in a "command buffer". Basically just a list of commands to be executed and a time stamp or frame stamp to indicate when the command was issued or when it's supposed to be executed.
   
   
4. The packet sent will contain the command and the time or frame stamp so that all nodes will know when to execute this command. Basically each packet that is sent will contain the information on what to do at each future frame. Each packet can also contain the number of commands that have been issued so far so that if one packet is lost, and the next packet arrives indicating that the number of commands has not increased the receiving node will just ignore the lost packet and continue normally. If data is missing, it can set information in it's own packet to that remote node to indicate which commands are missing.
   
   
   By letting the remote node know right away that a command needed is missing delays can be minimized (better than waiting until time to issue the command and then asking for the data again).
   
   
5. When a node gets a command from another user it adds this command to the command buffer just like it places it's own commands. It also sets the last command received information in the next packet it sends to the user that sent the command.
   
   
6. At each frame the game checks the command buffer to see what needs to be executed during this frame. If the command information for all users is not available it will continue to send the same packet to the other nodes until it receives all of the information. For remote nodes that you need data from your packet will contain the range of missing commands (like previous packets already contained) and for other nodes you just send a packet that basically states your waiting on someone else.
   
   

Duke Nukem seems to guess at the lag between nodes and adjusts a delay like War2. Quite a nice idea, and it mostly works very well. Being able to auto-adjust means that LAN games seem to run more like Doom. It's not exactly the same, but close. With Doom you KNOW what you're shooting. With Duke it's still a small guess (but still synched).

There is a problem though. Apparently the game runs out of room to store actions and you'll find your gun has stopped firing. If you don't let off and let the game catch up it eventually goes out of sync.

I suspect this could happen in War2 also, but the game is such that you don't have to send rapid- fire packets that can quickly overload a buffer. I also think War2 actually stops when it runs into trouble like this. Duke Nukem keeps running full speed until it dies. I think I would prefer to slow down for just a second or two.

Actually, I've added a few extra items to the scenario above that improves slightly on the War2 model. One further improvement, that can be made would be to have the game itself try to determine the lag and adjust the command delay automatically. It could start with the delay specified on the command line and then adjust up or down based on the average time it takes to get the acknowledgement of each packet. Using a little statistics you can calculate the average and standard deviation and set the delay to handle 95% of the response times. Of course you can put limits on the range that it tries to use, but if it really does take 1000ms to get a response then using anything less would cause lots of problems.

This system takes care of several problems that are faced on the internet:

1. Bandwidth: By only including command information in packets when the commands are issued the normal packet will be very small. Your application already does this so you should be ok here. Reducing bandwidth requirements also helps lag and packet loss. If too much data needs to be sent the game either has to slow down or data has
   to be dropped.
   
   
2. Lag: By not requiring immediate confirmation or trying to synchronize every frame you can basically work with ANY amount of lag. The penalty is the slight delay between issuing a command and seeing the command executed. Not all games would work as well with this delay, but in this type of game players would rather these delays as long as the normal execution of the game is full speed (the construction moves along at full speed). The only time the game will slow down is if data is either lost and the resend doesn't occur before time to execute the command or the delay is not set long enough (thus causing unnecessary resends).
   
   
3. Loss: Even if lots of non-command packets are lost the game will not slow down. No re-sends are necessary except for packets containing commands. As a result we also reduce bandwidth (which in turn helps lag and loss...which is good...
   
   
4. Sequencing: getting data out of order is not a problem since each command contains a framing number to indicate when it needs to be executed. Old data might arrive after replacement data has already been sent. No problem...just drop the redundant information. Even if a command for frame 10 arrives before the command for frame 9 the data for 9 might be re-sent, but the data for frame 10 is not lost since it's already added to the buffer.
   
   
   

These techniques handle lag, but there are at least two more factors to consider. The first is packet loss, and the second is sequencing. The internet can and will drop packets and even get them out of order. Your software needs to be able to deal with lost packets and has to be able to handle packets out of order. Kali can be set to drop packets that arrive out of order (late). We had to add this feature because several games would crash if the packets weren't in the right sequence.

To improve the handling of lost information, you might allow for backup information to be stored in packets. In the simplest case you might have each packet contain the current information along with a copy of the last bit of information. If one packet is lost, the next packet will contain the missing data. In a setup like Descent this would not help since lost information isn't important and the added packet size would decrease performance. In the case of Doom2, this can actually be adjusted to have each packet contain as much backup data as you want.

If you were sending action info (to be accomplished on a certain frame) you would normally have to wait until that frame to know if it was sent. If the next packet that went out also included this information (as a backup) the response might arrive late (thus causing a resend), but the response from the second packet might arrive soon after (the response isn't an extra packet, but rather just acknowledgement in one of the regular packets that the next action item had been received). In this case instead of a 300-500ms delay while waiting on acknowledgement of the resend, we would actually be able to continue the game almost right away since the next packet from the other node would have acknowledged the backup data.

Doing this properly will allow you to avoid those occasional and sometimes very annoying pauses that occur in War2 and C&C. With this option set properly I can play Doom2 over a bad connection with almost no pauses, but of course it's still somewhat slow.

Just combine all the best ingredients from these other games and you'll have a game that runs fast and plays smooth.

One last item to consider. Bandwidth. Keeping the number of packets and size of packets to a minimum is a must. If you run out of bandwidth on your connection everything will slow down. Allowing a users to reduce the number of packets sent per second can help a lot. Compressing or removing unnecessary data from packets will help.

Even in a 2 player game where you might not have a bandwidth problem, you would still want to use smaller packets simply because they travel faster across the modem. It just takes longer to send a 150 byte packet than it does a 15 byte packet. Just don't add more packets in your effort to reduce packet size. It will take longer to send two 15 byte packets than it will take to send one 50 byte packet because of the overhead on each packet.

..more to come someday...