UDP message dependency graph continued

In my last post I talked about some issues that come with using UDP and some approaches to dealing with them. In this post I'm going to describe my solution, a message dependency graph.

On the sending side, each guaranteed message has a sequence number associated with it. The sequence number is incremented each time a message is sent. When a message is sent, its sequence number is stored in a reference to a user-provided MessageDependency object. This way, when sending future messages, you call addDependency() and pass in the MessageDependency instance. You might wonder why I have a MessageDependency object instead of just using the sequence number directly. There is a good reason, which will be important later on.

Included in each message's header is the sequence number of that message as well as a list of dependencies. In my implementation, sequence numbers are 2 bytes unsigned integers in the range [0,32767] which wrap around when advancing past their maximum value. The reason I didn't use the full range is because the first bit is used as a "list termination" flag - if the first bit is 0, it signals the end of the list.

The following algorithm is used on the receiving side. When a new message arrives, a node in the graph is added for that message (if it doesn't already exist), and the node is initially flagged as "not executed". Next, the message nodes for each dependency are examined (if a dependency node doesn't yet exist, it is added and flagged as "not executed"). A directed edge is added pointing from each not-yet-executed dependency to the new message node. If the dependency has already been executed, then we don't add an edge between the two nodes.

Once the node has been added to the graph, we attempt to recursively execute any ready nodes. The algorithm for this is: start at node N. If N has any incoming edges, terminate, as this means it still has pending dependencies. Otherwise, if it has no incoming edges, execute it and flag it as "executed". Then, remove all outgoing edges from that node so that its successors know that it's been executed. Then recursively perform this algorithm on each successor.

Here is some pseudocode:

 void addMessage( seqNumber, dependencies[] )
     n = getNode( seqNumber )
     if n == null
         n = addNode( seqNumber )
         n.executed = false  

     // don't do anything if we've already executed the message
     if n.executed
         return  

     // add each dependency node
     for depSeqNumber in dependencies
         d = getNode( depSeqNumber )
         if n == null
             d = addNode( depSeqNumber )
             d.executed = false
         if !d.executed
             addEdge( d, n )  

 void tryExecuteMessage( seqNumber )
     // check to see if all dependencies have been completed
     n = getNode( seqNumber )  

     // if there are no dependencies, this message is ready to be executed
     if n.predecessorList is empty
         // execute the message
         executeMessage( n )
         m.executed = true  

         // try executing all messages dependent on this one
         for depSequenceNumber in n.successorList
             d = getNode( depSequenceNumber )
             removeEdge( n, d )
             tryExecuteMessage( depSequenceNumber )

One detail is that you should remove nodes from the graph eventually. Not only does this prevent a memory leak, but it's also required because sequence numbers wrap around. If you don't remove nodes, then after a while ("after a while", the mark of a bug full of pain and suffering!) you'll start dropping messages when the wrap occurs because the graph thinks they've already been executed. I choose to start removing nodes after they've been around for the connection timeout limit plus a second of padding. I also made it so that if an unexecuted node reaches this removal timeout, a connection error is signaled.

So far the implementation is pretty good. But there are still two major issues with it. The first issue is subtle, but fundamental. The problem is "old dependencies". Here's an example: suppose you send a message to spawn an enemy, and the message has sequence number 10. Then the player leaves the area, so the enemy goes idle. After an hour, the player returns and kills the enemy. The "kill enemy" message has a dependency on the "spawn enemy" message. But since it's been an hour, the sequence numbers have wrapped around, and "10" now refers to a completely different message. In fact, mostly likely, "10" wouldn't refer to any message at all, since the node containing message 10 has most likely been removed from the graph. Clearly this will not work at all.

The second issue is something that all network game programmers should be concerned about: bandwidth. Each guaranteed message with n dependencies is an additional 2+2n bytes. Using the plain old ordered channels method, each guaranteed message will cost only an additional 2 bytes. We need to find a way to cut down on all the extra dependency data.

Fortunately, there's something we can do that can sovle both of these problems at once! The idea is to determine, on the sending side, when a message must have been executed on the receiving side. Once we've determined that a message has been executed, we can simply remove any dependencies on that message. Remember that the reason we have dependencies in the first place, such as "B depends on A", is to ensure that A gets executed before B. And if we've determined that A has already been executed, we've already met that requirement!

To do this, we keep a local copy of the message dependency graph on the sending side in addition to the one on the receiving side. In the local graph, a node is added whenever a message is sent, but that node is initially marked as "not executed" (since when we first send it, it hasn't been executed on the receiving side yet). When we send a packet containing guaranteed messages, we keep a list of the sequence numbers of messages in that packet. Then, when we receive an ACK for that packet, we call the tryExecuteMessage() function for each guaranteed message that was previously sent. This will cause the local dependency graph to be evaluated just as it is on the receiving side.

Locally, when evaluating messages in the dependency graph, we don't want to actually evaluate the data sent along with the message as we would on the receiver. Instead, whenever a message is executed, we want to remove future dependencies on it. (Implement executeMessage() as a function pointer to be able to easily interchange this functionality). Remember how above I talked about using a MessageDependency object instead of passing around the raw sequence numbers? This now becomes important.

First of all, take a look at my endMessage() method's signature:

 bool endMessage( MessageDependency * dependency = NULL );

The important thing to note is that rather than returning a dependency object, I pass in an existing one to be filled out (or optionally none). Internally, when the function is called, a pointer to the dependency object passed in is stored along with the message. This is because the MessageDependency contains not only the message sequence number, but also an "executed" flag. Whenever a message is executed in the local graph, the corresponding dependency object's "executed" flag is set, so that next the object is passed into a call to addDependency(), it is simply ignored. Everything is completely transparent to the user!

(The implementation of this takes a bit of care; for example, the MessageDependency class should not be copyable, and its destructor needs to make sure to clear the external reference to it.)

Let's reexamine each of the above issues with this new local graph solution. The first issue was "old dependencies". E.g. message A is "spawn enemy", message B is "kill enemy". Message B is dependent on message A but occurs a long time after. With the local graph solution, an ACK for message A will be quickly received (usually in the connection round trip time), and A's dependency object will be marked as "executed". When message B is sent a long time later, the dependency won't even be added. First problem solved.

The second issue was bandwidth. Since we're quickly removing dependencies, the 2n term in the number of additional bytes needed per message will rapidly disappear, and we'll just be left with 2 bytes for the sequence number, which is just as good as having an ordered channel. Of course, this won't be the case when rapidly sending a ton of guaranteed messages with many interdependencies, but I can't imagine very many scenarios where this would occur, so I think it's safe to call the bandwidth issue "solved".

So far my implementation has been working great. I'd be interested in hearing your thoughts on the idea, or results if anyone has used something like it before.

UDP message dependency graph

Many multiplayer games with realtime requirements, such as first person shooters, use UDP for networking (huh, it just dawned on me that saying "UDP protocol" is like saying "ATM machine"). The advantage of using UDP rather than TCP is that if a packet is lost, the connection doesn't have to wait until that packet is recovered before processing newer packets. Of course, the downside is the fact that you acutally have to deal with lost packets (and that you don't even have a connection).

Glenn Fiedler has a great series of articles called Networking for Game Programmers which talks about TCP and UDP in more detail, and then goes on to describe how to implement a virtual connection on top of UDP and how to deal with packet loss. I won't go into detail here, as I've linked the articles, but in summary the implementation works by having the side receiving a packet send an ACK (acknowledgement) back to the sender to alert them that the packet has been received. This way, when sending a packet, you can know for sure when it gets through, and if an ACK is missed, you can decide how to proceed (whether or not to resend data). In this post I'm going to talk about my approach to making this decision.

In my project, "DR", packets are made up of a series of messages. Each message represents a command like "spawn object of type ENEMY at (x,y,z)" or "update object with ID 5 to position (x,y,z)". Some of these messages are important - if a packet with a "spawn enemy" message is dropped, you definitely want to resend that packet, since if you don't, the player would have an invisible enemy draining its health, and that wouldn't be very fun. Well, maybe it would be, but it's certainly not the intent. Other messages, like the "update object" message, aren't as important - if a packet with an "update object" message is dropped, the player might see a a very brief moment of lag (or maybe not even that, if extrapolation/prediction is used), but another "update object" message would be sent immediately after, and the mistake would quickly be fixed.

The first choice I made was to have two message types: guaranteed messages and non-guaranteed messages. When sending guaranteed messages, the content of the message is copied in a buffer, and once the ACK for the packet containing that message is received, the message is removed from the buffer. However, if the ACK for that packet is missed, the message is automatically sent along with the next packet. This process keeps occurring until an ACK for a packet containing that message is received. For non-guaranteed messages, none of this happens - you just send out the message and forget about it.

So that solves the issue of guaranteed messages. But there's another issue with UDP: packets don't necessarily arrive in order. I made the decision to simply drop packets which are older that the most recently received packet, but messages can still arrive out of order. For example, consider the following sequence of events:

Server sends packet 1 containing message A

Server sends packet 2 containing message B

Client receives packet 2 (packet 1 was lost) containing message B and sends back an ACK

Server realizes packet 1 was lost and resends message A in packet 3

Client receives packet 3 containing message A

The server sent A, then B, but the client received B, then A. This could cause some bad situations. For example, suppose message A contains "spawn ENEMY with ID 1", and message B contains "kill ENEMY with ID 1". Those messages need to be correctly ordered. A common solution is to implement a small part of TCP to allow for ordered messages. Each guaranteed message has a sequence number which is incremented, and a message with sequence number N is only executed once all messages with sequence numbers from 0 to N-1 have been executed. So when an out-of-order message is received, it is stored and then recalled to be executed once the messages that should come before it are received.

Of course, implementing TCP on top of UDP brings the same problems that we wanted to avoid with TCP! Messages can get delayed if other messages are dropped. For example, suppose you want chat messages to be guaranteed, as well as "spawn enemy" messages. If a player says something over chat and that packet is dropped, no "spawn enemy" messages can get through until the chat message is recovered. This contraint is obviously pointless and undesirable. One way to fix this is to have several guaranteed message "channels", such as one for critical game events and one for chat messages. Each channel would have its own sequence number counter, so messages from the "chat" channel wouldn't delay messages from the "critical game events" channel. This is better, but still not ideal. If you're spawning 10 enemies and the message to spawn the first enemy gets dropped, it would be nice if the other 9 weren't held up.

I was thinking about this when I came to the realization that message ordering "channels" are simply a special case of a more general data structure - a directed acyclic graph. In the message channel model, each message has a single dependency: the message that came directly before it. (Terminology: if B depends on A, then B is a successor of A and A is a predecessor of B). If you had 3 different message channels, the graph representation would look like 3 separate chains of nodes. If you remove the channel restriction and just allow for arbitrary dependencies (without cycles of course), all the issues I talked about above are solved. For example, a chat message would have a single dependency to the previous chat message, a "spawn enemy" message would have no dependencies, and a "kill enemy" message would have a single dependency to its corresponding "spawn enemy" message. Another example: suppose you have the server send info about each of the N players to each player, and then a "start game" message. The "start game" message could have N dependencies on the N "player info" messages. This way, the game wouldn't start until all player info was received.

I'm going to end this post, as it's getting late, but next I'll talk about my implementation of the UDP message dependency graph.

Realtime binaural audio

If you haven't heard of binaural recording, put on a good pair of stereo headphones and watch this video (or rather, listen to it). Pretty striking difference in terms of immersion from the audio we're used to hearing in games and movies. The idea behind it is to record using two microphones, one placed at each ear (perhaps even in ear-shaped molds to mimic precisely how sound travels through the ear canal), and when playing back the sound, play the left ear recording through the left stereo channel and the right ear recording through the right channel.

Part of the reason binaural recordings sound so much more realistic than standard stereo is that they capture the slight difference between time the sound takes to travel to each ear. For example, if a sound is coming from your right, it probably won't sound much louder in your right ear, but it will arrive at your right ear a tiny bit sooner. This slight difference is how your brain determines where the sound is coming from.

I decided to take a stab at implementing this effect in software. (I wonder if there will ever be "programmable audio shaders".) I started by playing a (looping) mono sound. I'll call the array of samples input, and the stream of samples I ultimately send to the sound card will be called left and right. If t is our time, in terms of the sample rate, then the regular way to play the sound would be

 left[t] = right[t] = input[t]

In order to get the binaural effect, we want to offset each output channel based on the distance that "ear" is from the source. This is because each ear is hearing the sound slightly "in the past". So how much do we offset by? To figure that out, we need to know a few things, such as the position of the source, the position of each ear, and the speed of sound, which is 340.29 meters/sec. So to figure out how long the sound took to travel from the source to the ear, we compute

 offset_seconds = distance(ear_position, source_position) / 340.29

To convert this into number of samples, we just multiply by the sample rate:

 offset_samples = offset_seconds * samples_per_second

So our code would look something like

 left_offset = (distance(left_ear_position, source_position / 340.29) * samples_per_second  

 right_offset = (distance(right_ear_position, source_position / 340.29) * samples_per_second  

 left[t] = input[t - left_offset]  

 right[t] = input[t - right_offset]  

Example: if the source is directly to your right and the ears are 15cm apart, left_offset would be 0.15 / 340.29 = 0.00044 seconds larger than right_offset. At 44.1kHz, left_offset is behind right_offset by about 19.5 samples.

Of course, there are a lot of other details I left out (which I don't know much about) such as interpolation between samples and interpolation of distances, but this is the basic idea. And as a bonus, you get the doppler effect for free, since as you move around, the offsets are changing, causing pitch shifts.

Here's my implementation. Controls are ASDW and move mouse to look around (quit with Alt-F4, since the mouse sticks in the center). I put in basic linear interpolation for samples and distance changes, which sounds absolutely awful, but it's a lot better than no interpolation.

It looks like there's been some research on this in the last few years. This video is pretty impressive... sounding!

Blog!

I figure I might as well do the standard "intro post" to get started. So, welcome to my humble ablog! The topic: game and graphics programming, and probably some other various topics from time to time. I'll be posting ideas, implementation challenges, and project progress updates.

I'm currently working on an indie game project (which I will refer to as "DR") which I am planning to release on tablet platforms. Unfortunately since I'm the only programmer, progress can be a bit slow at times, but I'll try to keep reasonably regular updates. I'm writing DR in C++ and OpenGL, using the engine I spent the last year building, which I've named "Crunch Game Engine". If you want to take a look, you can browse or download the repository on bitbucket.

Anyway, enough introductions, time to get onto some real posts.