Generic OrderedDictionary implemented in C# DotNet

The Dictionary class in .NET does not have a defined ordering when iterating through it. It can seem to maintain order until you start to remove objects from the collection. In order to maintain determinism, when ever we loop through a collection it needs to be in a deterministic order. There does already exist a OrderedDictionary, however there is not a Generic version.

This implementation uses two underlying collections. A Dictionary and a LinkedList. The Dictionary maintains a mapping from the Key to a LinkedListNode in the LinkedList. The LinkedList maintains a list of KeyValuePairs and keeps them in insertion order. A LinkedList is used instead of a List as it provides constant time removal (assuming you have a reference to a node).

private Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> mDictionary;
private LinkedList<KeyValuePair<TKey, TValue>> mLinkedList;

This implementation was inspired by the OrderedHashSet found at:

HASHSET THAT PRESERVES INSERTION ORDER OR .NET IMPLEMENTATION OF LINKEDHASHSET

The source code can be found at:

Generic OrderedDictionary on BitBucket

Lockstep Implementation in Unity3D

In the lockstep network model each client application runs the entire game simulation. The benefits of this approach is that it reduces the amount of information that needs to be sent over the wire. Only the user inputs need to be sent to each other, as opposed to an authoritative server model where for example every units position will need to be sent as often as possible.

For example imagine you want to move a character in the game world. In an authoritative model, the physics simulation will be ran only on the server. The client will communicate to the server where the character should move to. The server will perform the path finding and start to move the character. The server will then send to each client the characters position as frequently as possible so that the clients will have the most updated location. This must be done for every character in the game world. In a real time strategy game you can have thousands of units so the authoritative model would not be feasible.

In a lockstep model, once the user decides to move a character, that is communicated to every client. Every client will then perform path finding and update the characters position. Only the first communication will need to be sent over the internet as every client will have their own physics simulation and can update the characters position themselves.

This model does present some challenges. Each client must run their simulation in sync with each other. This means for example, that the physics simulation must perform the exact same number of updates and in the same order for each action. If this was not the case, then one client could get ahead or behind of the others and when a new command is sent, the path would be different for the client that got ahead or behind. These differences would build up and very different games would be played for each client.

Another issue is determinism across different machines and platforms. Small differences in calculations can cause butterfly effects building up to very different games. This issue will be covered in more detail in a future article.

The implementation presented here is inspired by the 1500 Archers article. Each players command is processed two turns in the future. Having a delay between when the action is sent and when it is processed helps the game from seeming choppy and laggy. This implementation also leaves room for us to add dynamic controls to adjust the turn length based on latency and machine performance. This part is not covered here and will come in a future article.

For this implementation we have the following definitions:

Lockstep turn
A lockstep turn will be made up of multiple game turns. One action per player will be processed in one lockstep turn. The length of the lockstep turn will be adjusted based on performance. At this time it is just hard coded as 200ms.
Game turn
A game turn is when the game logic and physics simulation will be updated. The number of game turns per lockstep turn will be adjusted based on performance. At this time it is hard coded to 50ms, or 4 per lockstep. This means there would be 20 game turns per second.
Action
An action is a command issued by a player. For example select units in a specified area, or move the selected units to the target location.

Note: we will not be using unity3d’s physics engine. A custom engine that is deterministic will be used. It’s implementation will be covered in a future article.

The main game loop

Unity3d’s loop is ran in a single thread. There are two functions that can be implemented to insert our custom code:

  • Update()
  • FixedUpdate()

Unity3d’s main loop will call Update() once per iteration. This will happen as fast as possible, or will attempt to run at a specific fps rate depending on the settings. FixedUpdate() will be ran so that it is called a predictable number of times per second depending on the settings. During the main loops iteration, it can be called zero or multiple times depending on how long the last iteration took. FixedUpdate() has the behavior we want as we need our code to run an exact number of times per lockstep turn. However, FixedUpdate() rate can only be set before run time. We want to adjust our game frame rate based on performance.

The Game Frame Turn

This implementation has similar logic as the FixedUpdate() inside our Update() function. The main difference is that we can adjust it’s rate. This is achieved by having an “accumulative” time. The time of the last iteration will be added to it each Update() call. This is the Time.deltaTime. If the accumulative time is greater than our fixed game frame rate (50ms) then we will make a gameframe() call. We will continue to call gameframe() and subtract from accumulative time by 50ms until accumulative time is less than 50ms.

	private float AccumilatedTime = 0f;

	private float FrameLength = 0.05f; //50 miliseconds

	//called once per unity frame
	public void Update() {
		//Basically same logic as FixedUpdate, but we can scale it by adjusting FrameLength
		AccumilatedTime = AccumilatedTime + Time.deltaTime;

		//in case the FPS is too slow, we may need to update the game multiple times a frame
		while(AccumilatedTime > FrameLength) {
			GameFrameTurn ();
			AccumilatedTime = AccumilatedTime - FrameLength;
		}
	}

We keep track of the number of game frames for the current lockstep turn. When we reach the number of game frames per lockstep turn, we update the lockstep turn on the next game frame. If the lockstep is not ready to advance to the next turn then we will not increment the game frame, and we will perform the lockstep check again on the next frame.

	private void GameFrameTurn() {
		//first frame is used to process actions
		if(GameFrame == 0) {
			if(LockStepTurn()) {
				GameFrame++;
			}
		} else {
			//update game

			//...
			
			GameFrame++;
			if(GameFrame == GameFramesPerLocksetpTurn) {
				GameFrame = 0;
			}
		}
	}

During the game frame turn, the physics simulation is updated and our game logic is updated. Game logic is added by implementing an Interface (IHasGameFrame) and adding that object to a collection that we can iterate through.

	private void GameFrameTurn() {
		//first frame is used to process actions
		if(GameFrame == 0) {
			if(LockStepTurn()) {
				GameFrame++;
			}
		} else {
			//update game
			SceneManager.Manager.TwoDPhysics.Update (GameFramesPerSecond);
			
			List<IHasGameFrame> finished = new List<IHasGameFrame>();
			foreach(IHasGameFrame obj in SceneManager.Manager.GameFrameObjects) {
				obj.GameFrameTurn(GameFramesPerSecond);
				if(obj.Finished) {
					finished.Add (obj);
				}
			}
			
			foreach(IHasGameFrame obj in finished) {
				SceneManager.Manager.GameFrameObjects.Remove (obj);
			}
			
			GameFrame++;
			if(GameFrame == GameFramesPerLocksetpTurn) {
				GameFrame = 0;
			}
		}
	}

The IHasGameFrame interface has a method called GameFrameTurn that takes as an argument the current number of game frames per second. An implementing object that has game logic should base any calculations on the GameFramesPerSecond. For instance if one unit is attacking another and it has an attack rate of 10 damage per second, you would apply the damage by dividing it by GameFramesPerSecond. The GameFramesPerSecond will be adjusted based on performance.

The IHasGameFrame interface also has a property to indicate when it is finished. This allows the implementing object to inform the main game frame loop it is no longer needed. An example of this would be an object that follows a path and once it reached it’s destination, the object is no longer needed.

The Lockstep Turn

In order to stay in sync with the other clients, each lockstep turn we must ask the following questions:

  • Did we recieve every client’s action for the next turn?
  • Did every client confirm that they recieved our action?

We have two objects, ConfirmedActions and PendingActions. Each of these have a collection for each possible message they may receive. We check both of these objects if we are ready to advance to the next turn.

	private bool NextTurn() {		
		if(confirmedActions.ReadyForNextTurn() && pendingActions.ReadyForNextTurn()) {
			//increment the turn ID
			LockStepTurnID++;
			//move the confirmed actions to next turn
			confirmedActions.NextTurn();
			//move the pending actions to this turn
			pendingActions.NextTurn();
			
			return true;
		}
		
		return false;
	}

Actions

Actions or commands are communicated by implementing the IAction interface. This has one method with no arguments called ProcessAction(). The class must also be Serializable. This means any fields of the object should also be Serializable. When a user interacts with the UI, an instance of the action is created, and sent to our lockstep manager in a queue. The queue is used in case the game is too slow and the user is able to send more than one command within a single lockstep turn. Only one command will be sent at a time, but none of them will be ignored.

When sending the action to the other players, the action instance will be serialized to an array of bytes, and then deserialized by those players. A default “NoAction” object will be sent when the user did not perform any actions that turn. The other actions will be specific to the game logic. Here is an example of an action to create a new unit:

using System;
using UnityEngine;

[Serializable]
public class CreateUnit : IAction
{
	int owningPlayer;
	int buildingID;
	
	public CreateUnit (int owningPlayer, int buildingID) {
		this.owningPlayer = owningPlayer;
		this.buildingID = buildingID;
	}
	
	public void ProcessAction() {
		Building b = SceneManager.Manager.GamePieceManager.GetBuilding(owningPlayer, buildingID);
		b.SpawnUnit();
	}
}

This action depends on the SceneManager having a static reference. If you do not like this implementation, the IAction interface could be modified so that the ProcessAction() receives an instance of a SceneManager.

The Sample Source can be found at:
Bitbucket – Sample Lockstep

Part 2