A Network Protocol for Movement (Part 3)

Posted on March 14, 2008 by Chris at 5:00 pm

A quick recap before we begin. In Part 1, I described a network protocol for moving objects around in 3d space. In Part 2, I wrote a server application that recieved connection requests and mob updates, and forwarded mob positions on to all other clients.

In this entry I’ll be writing about the Client Application that goes with the movement server. The application will basically be a 2d ships flying around type application, which looks like the screenshot to the right. The red blob on the screen is the Mob that is controlled by this client, while the green blobs are controlled by other clients. The blobs are supposed to look like turtles, but you can see my mspaint skills at work here :)

The server application is basically the same one that we used last time, with one or two bug fixes. As with the last entry, you can download the acompanying code to play with. I’ve also added the compiled binaries if you would prefer to just play with them.

Warning: Math Content

The only problem with working with 3d (even if you are displaying it in 2d), is that you need to know a little extra math to get things working properly. If you know how all this math works, congratulations. If not, here are some helpful hints and links that will assist you in reading my ugly math ridden code.

A Vector is basically a 3 dimentional {X,Y,Z} coordinate that can determine an objects position in 3d space, or be used for a variety of other porpoises (yes, they can be used for dolphins! who said they cant?). In fact we are also using Unit Vectors (vectors with a magnitude/length of 1 unit), to determine where Up, Right and Forward are.

The Cross Product of two vectors can be used to determine a third mutually orthogonal (right angled) vector. You will notice that we are only sending the Up and Right vectors using our movement protocol. To create our position matrix, we need to calculate a Forward or LookAt vector, which is simply done using the cross product of our Up and Right vectors.

The Dot Product of two vectors can be used to detrmine the cosine of the angle between them. This is how we figure out which way our little space ships are pointing. Given that our coordinate system is a right-handed y-up, z-facing one, we perform the dot product of {0,0,-1} and the Forward Vector. Finally, if the Forward.X value is less than 0, we make an adjustment, realising that the angle we are looking at is a reflex angle (greater than 180).

We use a Matrix to store the current Up, Right, Forward, and Location vectors. We can then use Matrix Multiplication against another matrix (such as a Translation, or Rotation Matrix) to move the object around the 3d space.

To create our position matrix can be made up using our Right (R), Up (U), Forward (F), and Position (P) vectors in the following 4×4 array

[R.X, R.Y, R.Z, 0.0]

[U.X, U.Y, U.Z, 0.0]

[F.X, F.Y, F.Z, 0.0]

[P.X, P.Y, P.Z, 1.0]

Note: I did kind of come up with the positioning matrix by myself from what I knew of 3d math, and how matrices worked.. so if I’ve got it wrong please do post a comment, so I can beat myself with a large stick.

Show Me the Coding!!!

Ok, now we have done the obligatory foray into the math behind the workings of the er.. game.. thingame (which is incedently the hardest part), we can now look at the client side networking code, which is actually what this entry is all about.

The general process that the client performs is as follows

  • Connect to the server using a LOC_Connect message
  • Recieve a LOC_AcceptConnection message, and store the given MobID for future use
  • Every 100ms or so update the location, orientation, and velocity of the current MobID using the LOC_UpdateMobLocation message
  • Every so often check for new LOC_MobLocation messages and update the relevant mob from the list
  • Attempt to update the screen to maintain a 30fps frame rate

Connecting to the Server

Connecting to thw server is done in two parts. First, the client will send a LOC_Connect message to the server, using the code below:

public void Connect(String address, int port)
{
   MemoryStream stream = new MemoryStream((int)LOC_ConnectMessage.MessageSize);
   BinaryWriter writer = new BinaryWriter(stream);

   if (m_Connection != null) return;

   // connect to the server
   m_Connection = new Socket(AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp);
   m_Connection.NoDelay = true; // disable nagle algorithm
   m_Connection.Connect(address, port);

   // send the connect message
   Random r = new Random();
   writer.Write((Byte)ProtocolCommand.LOC_Connect);
   // just send a random session id, the server doesnt use this right now
   writer.Write((int)r.Next());
   m_Connection.Send(stream.GetBuffer());
}

Note: On line 1 I am specifying the size of the stream to create, in the MemoryStream constructor (new MemoryStream((int)LOC_ConnectMessage.MessageSize);). If you don’t do this, the buffer size that you end up with when you pull it out using the GetBuffer method will be too large, which will screw up both the client and server communications. This is also one of the bugs that were fixed in the server app.

Next, the client will recieve the LOC_AcceptConnection message and store the MobID for use in future location update messages.

if (m_Connection.Available >= (LOC_ConnectMessage.MessageSize))
{
   buffer = new byte[LOC_ConnectMessage.MessageSize];
   m_Connection.Receive(buffer);

   reader = new BinaryReader(new MemoryStream(buffer));
   reader.ReadByte();
   m_MyMobId = reader.ReadInt32();

   m_NextMessage = 0x00;
   bProcessed = true;
   Connected(this, new EventArgs());
}

After the read loop (see next section) determins that the next message being recieved is a LOC_AcceptConnection message, the available data is checked, and the AcceptConnection message is pulled off the socket. We then read a single byte (with which we do nothing, because it is the actual command), and store the MobID in m_MyMobId. After this, the Connect event is fired so that other parts of the program (such as the main form) can react accordingly.

The Read Loop

The read loop of the client is slightly different to the server’s one. This is actually more due to the fact that I found a part of the Socket.Recieve method that allowed me to peek (look at, without consuming) the incoming data.

if (m_Connection.Poll(100, SelectMode.SelectRead))
{
   bProcessed = true;
   bNextMessage = 0; // no message
   // keep looping until no more messages can be processed
   while (bProcessed)
   {
      bProcessed = false;

      if (m_Connection.Available > 0)
      {
         buffer = new byte[1];

         // peek at the invcoming data using SocketFlags.Peek
         m_Connection.Receive(buffer, 0, 1, SocketFlags.Peek);
         bNextMessage = buffer[0];
      }

      // check which message is being recieved and react accordinly
      switch ((ProtocolCommand)bNextMessage)
      {
         case ProtocolCommand.LOC_AcceptConnection:
            ...
         case ProtocolCommand.LOC_MobLocation:
            ...
      }
   }
}

The code above can be found in the MovementClient.Iterate method. Each time the Iterate method is called (about once every 500ms), this code checks if there is any data available on the socked using the Socket.Poll method, then attempts to peek at the first byte that’s available. The first byte should always be either a LOC_AcceptConnection message, or a LOC_MobLocation message.

Updating the Locations

There are two parts to the locations being updated. One is sending updates for your mob to the server, and the other is recieving the updates for all the other mobs.

The MovementClient.SendMobData method takes care of sending the updates to the server. It’s a simple package and send sort of function, similar to what you saw befor with the Connect method, but bigger.

public void SendMobData(MobData data)
{
   MemoryStream stream = new MemoryStream((int)LOC_UpdateMobLocationMessage.MessageSize);
   BinaryWriter writer = new BinaryWriter(stream);

   writer.Write(Convert.ToByte(ProtocolCommand.LOC_UpdateMobLocation));
   writer.Write(data.MobId);
   writer.Write(data.Location.X);
   writer.Write(data.Location.Y);
   writer.Write(data.Location.Z);
   writer.Write(data.UpVector.X);
   writer.Write(data.UpVector.Y);
   writer.Write(data.UpVector.Z);
   writer.Write(data.RightVector.X);
   writer.Write(data.RightVector.Y);
   writer.Write(data.RightVector.Z);
   writer.Write(data.Velocity.X);
   writer.Write(data.Velocity.Y);
   writer.Write(data.Velocity.Z);

   try
   {
      m_Connection.Send(stream.GetBuffer());
   }
   catch (Exception) { ;}
}

You have probably noticed that the Socket.Send function is enclosed in a try/catch routine. This is mainly because I’ve not bothered about good programming, and making sure that I actually have a good connection prior to sending. I’ve made it so that it just fails silently, not bothering me or anyone else in the process. This is actually a problem with my coding style, where I indend on getting back to it and fixing it, but in the mean time, I want it to work without bothering me :)… then it never bothers me again.. then something screws up.. then it takes many days to find where the problem is… when I can be bothered I’ll write some lines for my sins.. “I will use caution when programming. I will use caution when programming. I will use caution when programming. I will use caution when programming.”

The next bit handles incoming location updates from the other clients. You may have noticed the case ProtocolCommand.LOC_MobLocation in the read loop section. This is where we handle the incoming location updates. Again, it is a simple unpack / alert routine that you are seeing.

if (m_Connection.Available >= (LOC_UpdateMobLocationMessage.MessageSize))
{
   buffer = new byte[LOC_UpdateMobLocationMessage.MessageSize];
   m_Connection.Receive(buffer);

   reader = new BinaryReader(new MemoryStream(buffer));

   message = new LOC_UpdateMobLocationMessage();
   message.Command = reader.ReadByte();
   message.MobId = reader.ReadInt32();
   message.Location.X = reader.ReadDouble();
   message.Location.Y = reader.ReadDouble();
   message.Location.Z = reader.ReadDouble();
   message.UpVector.X = reader.ReadDouble();
   message.UpVector.Y = reader.ReadDouble();
   message.UpVector.Z = reader.ReadDouble();
   message.RightVector.X = reader.ReadDouble();
   message.RightVector.Y = reader.ReadDouble();
   message.RightVector.Z = reader.ReadDouble();
   message.Velocity.X = reader.ReadDouble();
   message.Velocity.Y = reader.ReadDouble();
   message.Velocity.Z = reader.ReadDouble();

   bNextMessage = 0;
   bProcessed = true;
   UpdateMobLocation(message);
}

Similar to the accept connection routine, it simply pulls the appropriate amount of data out of the socket using the Recieve method, then reads the information in the correct order, just like if we stored the data in a binary file. Finally the UpdateMobLocation event is fired so that the main form can keep track of the unit in question.

It’s probably worth having a look at the code from the main form in this circumstance, as some of the logic is also performed here. Below you will find the function that is called when the MovementClient.UpdateMobLocation event is fired.

void OnUpdateLocation(LOC_UpdateMobLocationMessage message)
{
   MobileUnit mob = null;
   Vector3d vUp, vRight, vLoc, vVel; 

   // only make changes if the mob is not the current client
   if (message.MobId != m_Client.MobId)
   {
      if (m_UnitList.ContainsKey(message.MobId))
      {
         mob = m_UnitList[message.MobId];
      }
      else
      {
         mob = new MobileUnit();
         m_UnitList.Add(message.MobId, mob);
      }

      // get the new vector sets
      vUp = new Vector3d(message.UpVector.X, message.UpVector.Y, message.UpVector.Z);
      vRight = new Vector3d(message.RightVector.X, message.RightVector.Y, message.RightVector.Z);
      vLoc = new Vector3d(message.Location.X, message.Location.Y, message.Location.Z);
      vVel = new Vector3d(message.Velocity.X, message.Velocity.Y, message.Velocity.Z);

      mob.UpdateMatrix(vUp, vRight, vLoc, vVel);
   }
}

Basically, I’m storing all of the mobs that aren’t the current client in a Dictionary object. This way I can pull a MobileUnit object, given a single key. The reason we dont want to store the current client’s info in this list, is that each client is actually the authority on where their own mobs are, so we would not want to overwrite this information with older or inaccurate data.

Please Stop! My Eyes Hurt!

So, we’ve come to the end of my little foray into the dephts of network programming. What’s next? you may ask. What could possibly make this code better?

There are a good number of things that have been left un-done, mainly due to laziness on my own part. Here’s a list of what could be done in the future, and you may notice that I’ve copied stuff from my last post (muy perezoso! wtf?! spanish?)

  • Handle Client disconnects better, rather than just ignoring them
  • Send a message to the clients when someone disconnects, so that they know to remove a mob (LOC_Disconnect)
  • Perform more checks on the api calls to ensure that there are no errors, such as socket already in use
  • Allow users to specify the port that they want to run the server on
  • Allow users to specify the port that they want to connect to the server on (from the client)
  • Add a Rotation vector to the LOC_MobLocation and LOC_UpdateMobLocation messages, so that we can track turning smoothly
  • Re-write the server so that is better, stronger, faster

Source Code: Download

Binaries: Download

Filed under: Articles, Game Development Tags: , , , ,

A Network Protocol for Movement (Part 2)

Posted on March 4, 2008 by Chris at 11:01 am

The Server Application

In Part 1 I discussed that the creation of the server a application that would accept connection requests and broadcast mob locations to other users. This article will explain in detail exactly how to set up the server, and you will be able to download a copy of my (somewhat messy) source code that performs the task.

Having not yet written a client application to perform tests against the server with, I came up with a nifty, simple method of testing that the server is doing what we expect. Because we are using standard TCP/IP, we can simply use the telnet program that comes with windows to simulate our client.

Problems with the initial design

While I was working though the server creation process, I noticed that there were a few problems with the protocol messages and structure. Here’s an updated table:

Byte - Message Type
   01 - LOC_Connect
      Int32     4 bytes   SessionID
   02 - LOC_AcceptConnection
      Int32     4 bytes   MobID
   03 - LOC_MobLocation
      Int32     4 bytes   MobID
      Vec3     24 bytes   Location
      Vec3     24 bytes   UpVector
      Vec3     24 bytes   RightVector
      Vec3     24 bytes	  Velocity
   04 - LOC_UpdateMobLocation
      Int32     4 bytes   MobID
      Vec3     24 bytes   Location
      Vec3     24 bytes   UpVector
      Vec3     24 bytes   RightVector
      Vec3     24 bytes	  Velocity

The main changes are the removal of the LOC_GetMobLocation. I changed the Velocity items to vectors, so that we could specify a velocity in all planes (x,y,z). Finally, I gave myself a slap across the forehead for thinking that Doubles were 64-byte values, they are in fact 64-bit, which is 8 bytes.

Drawing the User Interface

The user interface is fairly simple and looks like the screen below.

The Start / Stop button will call the server’s Start or Stop routine, depending on it’s current status.

The LstMessages window will show all of the log messages that the MovementServer class throws.

The MovementServer Class

Here’s a basic outline of the MovementServer class

public class MovementServer
{
	public delegate void LogEntryEventHandler(String Message);
	public event LogEntryEventHandler LogEntry;

	public int ServerStatus {get;}
	public void Start();
	public void Stop();
	public void Iterate();
}

Basically what happens when you start the application is as follows:

  1. A new MovementServer class is created
  2. Form1 allocates a handler for the LogEntry event
  3. Form1 creates a new Timer, and allocates it’s Tick event to an internal function
  4. Every time the Timer ticks, the Movement Server’s Iterate() function is called.

When the user clicks on the Start / Stop button for the first time, the MovementServer’s Start() function will be called. Here’s the code for this below.

IPEndPoint endPoint;

LogEntry("Server Starting");

// set up the internal variables
m_BufferedData = new Dictionary();
m_MobData = new Dictionary();
m_SocketMobs = new Dictionary();

// set up the connection to listen for new TCP connections
m_Listener = new Socket(AddressFamily.InterNetwork, SocketType.Stream, ProtocolType.Tcp);
m_Listener.NoDelay = true; // disable nagle algorithm
endPoint = new IPEndPoint(IPAddress.Any, ListeningPort);
m_Listener.Bind(endPoint);
m_Listener.Listen(ConnectionBacklog);

// add a log entry, and set the server status to connected
LogEntry("Listening on port " + ListeningPort.ToString());
m_Status = 1;

// create the client pool
m_ClientPool = new List();

This simply tells the socket to listen for new connections on the requested port, which in this case is 12654. Note the LogEntry routine being called. This will tell the UI to put another message on the LstMessages list.

The remaining work occurs in the Iterate() function, which is called at set intervals by the user interface.

First the Iterate() function will check if there are any new clients attempting to connect.

// check for new connections
// if there are new connections available, accept the
// connection and add it to the available list
IList list = new List();
list.Add(m_Listener);

// Socket.Select will check for incoming data on the list,
// and remove any items that do not have data available
Socket.Select(list, null, null, 100);
if (list.Contains(m_Listener))
{
	// accept the first available connection
	// Socket.Accept - Accepts the connection and
        //   creates a new socket that you can communicate
        //   with the client on
	newSocket = m_Listener.Accept();
	m_ClientPool.Add(newSocket);

	// get the client address and post a log entry
	clientAddress = ((IPEndPoint)newSocket.RemoteEndPoint).Address.ToString();
	LogEntry(clientAddress + " Connected");

	// select again, to check if there are any further connections
	Socket.Select(list, null, null, 100);
}

Next, Iterate() checks for any new data on the sockets in the client pool

// check for new data on existing connections
if (m_ClientPool.Count > 0)
{
	// copy the client pool list
	list = new List();
	foreach (Socket client in m_ClientPool) list.Add(client);

	// select the items with data available
	Socket.Select(list, null, null, 100);
	foreach (Socket client in list)
	{
		buffer = new byte[client.Available];
		if (client.Connected)
		{
			try
			{
				client.Receive(buffer);

				// process the new buffer
				ProcessBuffer(client, buffer);
			}
			catch (Exception)
			{
			}
		}
	}
}

You can see that the ProcessBuffer() function has been called at this point, this function will determine which message has been called, and process it as required. Download the source code for more details.

Running some tests

Testing the LOC_Connect message:

  1. Open telnet using “telnet localhost 12654″
  2. Type the following into the screen that is shown: (Ctrl + A)TEST.
  3. This will result in the following bytes being sent to the server 0×01 0×54 0×45 0×53 0×54
  4. The server should now respond with some cryptic binary gobbledegook, and show a message in it’s log.

Next, connect another client using the same steps above. Remember to keep both telnet clients open so that we can test the broadcast functionality as well. You should recieve some additional gobbledegook on this one. The server is just sending you the current location of all mobs, so you should be recieving around double the amount.

Now, we want to test sending a message to update the mob location.

  1. Using one of the open telnet clients, send the following message: (Ctrl + D)(100 other bytes)
  2. This will send a LOC_UpdateMobLocation message, which should then be broadcast to all other users.

And to that I would say TEST_SUCCESSFUL.

ToDo List

Let me say again that I am very green at the whole network programming thing, which is part of the reason for this blog entry. If I were to revisit this server application, I would have a look at doing the following things:

  • Handle Client disconnects better, rather than just ignoring them
  • Send a message to the clients when someone disconnects, so that they know to remove a mob
  • Perform more checks on the api calls to ensure that there are no errors, such as socket already in use
  • Allow users to specify the port that they want to run the server on

I’m sure that there are other things that could be improved on, but this seems like enough for now.

Source Code: Download

Filed under: Articles, Game Development Tags: , , ,

A Network Protocol for Movement (Part 1)

Posted on January 17, 2008 by Chris at 8:03 am

Introduction

This is a first-draft attempt at making a network protocol that will allow the effective communication of a mobile unit (mob) in a 3D world. This kind of protocol is no doubt required to make any network game that requires movement movement in 3d space, which is most network games these days. It can be easily adapted to be a 2d protocol by ignoring z coordinates.

I’ve decided to go with the TCP for this protocol, as the packets automatically show up in the order that they were sent. While UDP would probably be a better option considering it won’t wait for lost packets to come through, we would need to add more controls to ensure that we were working with the latest information. UDP packets can turn up at any time or not at all, and while we could handle the not at all, packets that turn up out of order could send a mob back to a previous location which would not be beneficial.

I’m planning on having two more parts to this in the future.

  • Part 2 - Will cover the creation of the server application
  • Part 3 - Will cover the creation of a sample client application

The Protocol

  • Each message will start with a single byte that indicates what type of message is being recieved
  • The Vec3 datatype will contain three Double values indicating the x,y,z coordinates
  • If you know much about 3D maths, the UpVector and RightVector should make sense. These values indicate precicely which way the mob is facing.
  • For this protocol to work properly in implementation we will probably need to turn off the Nagle algorithm using TCP_NODELAY

    •  

The table below shows the structure of the messages that we will be handling in the protocol. I may need to make changes to this structure in the future, if a required function is not covered.

Byte - Message Type 01 - LOC_Connect Int32 4 bytes SessionID 02 - LOC_AcceptConnection Int32 4 bytes MobID 03 - LOC_GetMobLocation Int32 4 bytes MobID 04 - LOC_MobLocation Int32 4 bytes MobID Vec3 196 bytes Location Vec3 196 bytes UpVector Vec3 196 bytes RightVector Double 64 bytes Velocity 05 - LOC_UpdateMobLocation Int32 4 bytes MobID Vec3 196 bytes Location Vec3 196 bytes UpVector Vec3 196 bytes RightVector Double 64 bytes VelocityWhat the sever will do

  • Accept a LOC_Connect message from a new client
  • Send a LOC_AcceptConnection message with the unique MobID new player
  • While the connection is still active, accept LOC_UpdateMobLocation messages, and store the most recent detials for each Mob
  • For each LOC_UpdateMobLocation message recieved, send an equivalant LOC_MobLocation message to each connected client

What the client will do

  • Send a LOC_Connect message to the server
  • Wait for a LOC_AcceptConnection message, and store the MobID value for future use
  • Periodically send a LOC_UpdateMobLocation message to the server, indicating the current location of the client’s unit
  • Accept LOC_UpdateMobLocation messages, keeping and displaying the locations of each MobID.

Notes

  • The current location of each mob, along with the speed that they are moving is controlled by the client. Additional controls could be added later to ensure that the client is using allowable values in it’s location messages, and rejecting or modifying the values as required.
  • The SessionID value passed in the LOC_Connect message can be used to integrate with other services. For example, a login server may accept authentication information, then pass a unique session id indication authentication was successful.
  • Using the location, vectors, and velocity values a simple dead reconing system can be implemented.
Filed under: Articles, Game Development Tags: , , ,