Unity C#: Dictionaries

A dictionary is similar to a list but with a few advantages and a disadvantages, where the dictionary is not displayed in the editors inspector windows (although this can be overcome through Unity packages like the Odin Inspector or by writing your own custom inspector). A dictionary is a list of pairs, where each pair is made up of a key and a value. This is where the dictionary becomes faster than a list. In order to find a value within a list, you have to loop through all of the elements. However with a dictionary, you just give it the key that is associated with the value you want.

[System.Serializable]
public class Item()
{
string name;
ItemType itemType;
int itemId;
string itemDescription
}


public class TestClass : MonoBehaviour
{
// Defining a dictionary
private Dictionary<int, Item> itemDictionary = new Dictionary<int, Item>();

private void Start()
{
// Create new item
Item shield = new Item();
shield.name = "Shield";
shield.itemType = ItemType.Shield;
shield.itemId = 0;
shield.itemDescription = "Something to block attacks with";

// Add the first item to our dictionary
itemDictionary.Add(0, shield);

// Access the first item and display the name of the item in the console log
Debug.Log("First Item: " + itemDictionary[0].name);
}
}

Adding values to a dictionary is similar to a list but with one minor change, you have to provide a key with the value that you want to add. Accessing an value is also similar to a list but instead of using an index, you use the key associated with the value you want.

Looping Through A Dictionary

You can loop through a dictionary using a foreach loop, but there are three ways you can write that loop. The first being as a KeyValuePair, the second being just the keys and the third being just the values. Below are examples of all three loops.

[System.Serializable]

public class Item()

{

string name;

ItemType itemType;

int itemId;

string itemDescription

}

public class TestClass : MonoBehaviour

{

// Defining a dictionary

private Dictionary<int, Item> itemDictionary = new Dictionary<int, Item>();

private void Start()

{

// Create new item

Item shield = new Item();

shield.name = "Shield";

shield.itemType = ItemType.Shield;

shield.itemId = 0;

shield.itemDescription = "Something to block attacks with";

// Add the first item to our dictionary

itemDictionary.Add(0, shield);

// Create new item

Item sword = new Item();

sword.name = "Sword";

sword.itemType = ItemType.Sword;

sword.itemId = 1;

sword.itemDescription = "Something to attacks with";

// Add the second item to our dictionary

itemDictionary.Add(3, sword);

// Create new item

Item helmet = new Item();

helmet.name = "Helmet";

helmet.itemType = ItemType.Armour;

helmet.itemId = 2;

helmet.itemDescription = "Something to put on your head";

// Add the third item to our dictionary

itemDictionary.Add(6, helmet);

// Loop through dictionary using KeyValuePair

foreach(KeyValuePair<int, Item> entry in itemDictionary)

{

Debug.Log("Key: " + entry.key);

Debug.Log("Value: " + entry.value);

}

// Loop through dictionary using Key

foreach(int key in itemDictionary.keys)

{

Debug.Log("Key: " + key);

}

// Loop through dictionary using values

foreach(Item item in itemDictionary.values)

{

Debug.Log("Value: " + item.name);

}

}

}

Note that it is possible that all keys are not going to be sequential as demonstrated above. Also all keys should be unique, but there can be duplicate items. You can also check if a dictionary has a key by using the ContainsKey() function, this stops any exception errors due to missing keys.

Unity C#: Static Types

Like with most programming languages, C# has a static keyword that can be used on classes, variables and functions. By using the static keyword, that class, variable or function is available for the lifetime of the game. It's worth noting that if you create a static class, it cannot inherit from the MonoBehaviour class but also that all variables and functions must be static.

Static Members Verses Instance Members

Besides being a member that is available throughout the lifetime of a game, a static member is available to all instances of a class. Instance members on the other hand are different because they are specific to that instance of a class. For example, you have an enemy ship class, that class might have a health member. Generally this type of member would be an instance, as you would want each ship to have a unique amount of health. An example of a static member for an enemy ship class would be a shipCount, which keeps track of how many ships there currently are. With this you don't want each instance of the class to have a unique value for this member, so it would be static.

public class EnemyShip()

{

public EnemyShip()

{

shipCount++;

}

public int health;

public static int shipCount;

}

public class TestClass : MonoBehaviour

{

private void Start()

{

EnemyShip shipOne = new EnemyShip();

shipOne.health = 10;

EnemyShip shipTwo = new EnemyShip();

shipTwo.health = 5;

Debug.Log("Ship Count: " + EnemyShip.shipCount);

}

}

Static Constructor

A static constructor can be used to initialise any static members within a class. This constructor will only be called once unlike the constructors we usually use. It will also be called first before any of the instance constructors.

public class EnemyShip()

{

public EnemyShip()

{

shipCount++;

}

static EnemyShip()

{

shipGroup = "Atlas";

}

public int health;

public static int shipCount;

public static string shipGroup;

}

public class TestClass : MonoBehaviour

{

private void Start()

{

EnemyShip shipOne = new EnemyShip();

shipOne.health = 10;

EnemyShip shipTwo = new EnemyShip();

shipTwo.health = 5;

Debug.Log("Ship Count: " + EnemyShip.shipCount);

}

}

In this example the static constructor is used to set the ship's group to "Atlas", as this is static, all enemy ships will have the same ship group value and is done once before the instance constructors. 

Asymptotic Notations Pt 2

Big O Notation
With the Big Theta notation we bound the growth of a runtime within a constant upper and lower factor. However, there are some times where we want to bound that growth to the upper factor. This is where the Big O notation comes in to play.

With binary search the worst case scenario is 𝛉(log2(n)), however, this is not the case 100% of the time as it is possible to find the target value on the first try which would make the runtime 𝛉(1). Therefore you can say that the runtime of binary search is never worse than 𝛉(log2(n)) but can be better. How would we write this using asymptotic notations, well we would write O(log2(n)).

Like with the big theta notation once n becomes large enough it is less than or equal to k * f(n), the big O notation can be used. Of course the Big O notation can also be used on any function and not just a logarithmic function.

Big Omega Notation

Sometimes we instead want to say that a runtime will take at least a certain amount of time, but without providing an upper bound. This is where the big omega notation comes into play. This means any function where n becomes large enough and is greater than or equal to k * f(n).

The Big Theta notation implies both Big O and Big Omega notations, but both Big O and Big Omega notations are imprecies due to not using both bounds. With this imprecision it is best to use Big Theta when describing a runtime of an algorithm.

Asymptotic Notations Pt 1

The runtime of any algorithm is decided by various factors such as the speed of the computer, the programming languages used, how long it takes for a compiler to translate the programming code into machine code and more.

We can think of the runtime of an algorithm as a function of the size of it's input. The makes sense when you look at linear or binary search algorithms because they take longer as you increase the size of the array that you are searching through.

We also need to think about the growth of the function as the size of the input increases, which is often referred to as the rate of growth. To make things more managable we simplify the function. This means removing the less important parts from the function. For example; we have the function 6n^2 + 100n + 300, where n is the size of the input. At some point the 6n^2 part of the function is going to become greater than 100n + 300 part, this actually happens when n = 20. Therefore we can get rid of the 100n + 300 part. We can also remove the 6 coefficient part of the 6n^2. This is because as long as the coefficient is > 0 then the difference will increase as does n. So we can say that the function grows as n^2.

By dropping the less important parts we can completely focus on the rate of growth of an algorithms runtime. When we do this we use asymptotic notations. Three examples of these types of notations are the big theta (𝛉), big O and big omega (𝛀).

Big Theta
As mentioned before the runtime of an algorithm is made up of various factors (some listed above) this will be denoted as c1. Then we have the input size or number of loop iterations, which is denoted as n. Finally we have the overhead of a function such as initialising the index to 0, this is denoted as c2. Using these values we can calculate the total time for the worst case scenario (which in a linear search is not finding a value). The formula is c1 * n + c2.

Both c1 and c2 don't tell us anything about the rate of growth of the runtime. The important part is n and so because both c1 and c2 are also constants we can drop both of them. Therefore the notation we use for the worst case scenario of a linear search is 𝛉(n).
What this means is when n is large enough, the runtime is greater than k1 * n and less than k2 * n, where k1 and k2 are some constants. This can be seen in the graph below.

We can also use other functions of n, such as n^2 or nlog2. Therefore as long as any runtime that uses some function of n, f(n), is greater than k1 * f(n) and is less than k2 * f(n), it is a big theta notation or in other words 𝛉(f(n)).

Another advantage of using these notations means that we don't have to note the time units being used. So the previous example of 6n^2 + 100n + 300, becomes 𝛉(n^2). When we use this notation we are saying we have a asymptotically tight bound on the runtime. This is because it only matters when n is large enough (this gives us the asymptotically part) but also because the runtime is between the two k constants * f(n) (this gives us the tight bound part).

Growth Characteristics
There are 6 typical types of growth; constant, logarithmic, linear, linearithmic, polynomial and exponential, however, there are other types of growth that might not be covered.

An example of a constant growth is finding the first element within an array. The function would be 1 as element 0 is always the first element. An example of an logarithmic function is Log2(n). This means how many 2 we need to multiply to get n. Linear is where n (the size of the input) is multiplied by some sort of coefficient, for example 3n would have a linear growth. Linearithmic is a combination of logarithmic and linear functions. An example of this is nLog2(n). Polynomial is similar to linear but this time n has a power/indice that follows after it. For example 3n^2 or n^6. Finally there is exponential and this is where some number has an indice of n, for example (3/2)^n or 6^n.

The order of growth is:

1. Constant
2. Logarithmic
3. Linear
4. Linearithmic
5. Polynomial
6. Exponential

Its worth noting that with logarithmic and linearithmic functions the growth speed is dependant on the base, the lower the base value the quicker the growth. For example log2(n) is faster than log8(n). With polynomial and exponential functions, the higher value the power/indice is the quicker the growth. So n^2 is slower than n^4.

Precompiled Headers In C++

Usually when you include a header file in any C++ file, all of the contents of the header file is copied and compiled into the C++ file. This isn't so bad for a single header file, but if the header file also included several other header files, they also have to be compiled. So if you have a large project, you can expect the compile times to be very long without using precompiled headers. By precompiling headers, it converts a set of headers into a single file that uses the binary format in which the compiler can read and this is only done once. This however doesn't work if you add header files that you will be constantly or even occasionally changing as it means that the precompiled header now has to be recompiled every time a change is made.

Precompiled headers are usually used for headers that are going to be used often throughout the project such as the standard libary or any external libraries that you might be using. This is because they aren't going to change (unless there is a major issue with a version of an external library, which causes you to update that library). You can also use it for your own libraries but as mentioned above it is only worth doing if that library you have created is complete and isn't going to change or isn't likely to change.

There is a disadvantage to using precompiled headers and that is that it can hide the dependancies of a C++ file. Normally by just including whatever header files in a C++ file, you can easily tell what it requires. This means that if you were to reuse that C++ file within another project, you already know what else you will need if you don't already have it within that project. However, this is not the case with precompiled headers as it most likely has a ton of header files that are being used throughout the project but not specifically for the C++ file that you want to reuse. Therefore, if you did reuse that file you would have to figure out the header files that the file depends on.

Also if you are only going to use a header file in a single C++ file then it is not worth adding to the precompiled headers file. This is because that header file is more than likely going to be abstracted into your own api for you to use. An example of this would be the GLFW header file.

Below is a useful video on the subject, in which these notes are based on, but also the set up needed to use precompiled headers within a C++ project.

Enums Vs Enum Classes Pt 1

Enums and enum classes are essentially the same thing, however, using enum classes can avoid a compiler error as well as some other issues that maybe discussed in later posts.

enum AEnum
{
    OK,
    FAILED,
}

enum BEnum
{
    READY,
    FAILED,
}

The above enums will cause a compiler error and this is because within both enums the value FAILED has been declared twice as both values are within a global scope. By using enum classes instead avoids this problem as each value declared is now within its own enum class scope. A enum class is also known as a strongly typed enum. The below code shows the correct usage of enum classes. NB: Enum Classes are available in C++ 11+.

enum class AEnum
{
    OK,
    FAILED,
}

enum class BEnum
{
    READY,
    FAILED,
}

The Const Keyword: Const Functions

Const is generally used to state that something will not be changed or modified. However, this is dependant on where const is placed. For example if you place the const keyword after a member/class function declaration, you will not be allowed to modify any member variables within that function.

int GetMaxTries() const;

int GetMaxTries() const 
{
    return maxTries; 
}

The above function and function declaration will not produce any compiler errors as it doesn't modify any of the class's member variables. However, the below example would, because even with the const someone has tried to modify the maxTries variable. The const keyword in this situation acts as a guard so that you or anyone else working on the codebase doesn't accidentally modify any member variables within a specific function.

int GetMaxTries() const;

int GetMaxTries() const 
{
    maxTries += 12;
    return maxTries; 
}