Linked List Has a Visible Form in Game Development

A linked list is a data structure in which a programmer can store data and references. If you are a developer, you indeed used linked lists for your purposes, but in game development, you can give it a form. For the sake of clarity, let me give a brief explanation of what is a linked list and what is it useful for.

To explain a linked list, people usually use an array as a benchmark, I believe it is a good practice and makes things easier to understand. Using an array or a linked list may have various consequences, each of must a developer be aware of.

The game with the linked list in this post.

Using a linked list may have advantages over using an array. One aspect a developer should consider would be how much you require a get method. If you are accessing the elements so often, using an array should be better since the array is indexed and you may access an element in constant time, i.e. O(1).

Another aspect to consider should be how often you perform insertion to your data. Appending an element to a linked list is O(1) since you just create a node with your data, link it to the head node, and make the new node the head node. A similar approach goes for prepend method. As for inserting a node into central nodes, we have two options. If we insert a particular position, we may spend O(n) for finding the node and O(1) for insertion whereas if we just insert, we spend O(1) in terms of time complexity. Deletion is exactly the same.

In terms of space complexity, again there shall be a trade-off. An array is fixed in size and all elements of an array are occupied beforehand into adjacent blocks in memory. This means easy to reach, but you cannot expand it during runtime if you require more memory. Whereas a linked list keeps the data and the pointer which points to where the next element is saved in the memory, you can expand as long as you can during runtime unless you don’t have enough memory. Again this sounds good but it actually requires some more space on the memory to save a pointer to the next node. This means if you use a linked list for small data, you may waste your memory since the memory spent to point to the next node shall not be worth it.

So, how can we use a linked list or any data structure for our purposes? In this game, a node consists of a value, a gameobject, and a pointer to point to the next node.

We first decide what we will carry in our node. In this case, we carry a value, a game object, and a reference.

[SerializeField]

public class Cube //Or any name you want, Node is used very often.

{

     public int value;

     public GameObject body;

     public Cube next;

     //Decide your data and add over here.

     public Cube(int newvalue, GameObject newbody)

     {

         value = newvalue;

         next = null;

         body = newbody;

     }
}
//This is the constructor, once we initialize an object fromt his class, it will be initialized with these setup.

We will now use this smallest unit of cubes to combine them in a pattern. You may call it a Node, but I call it a Cube due to the context.

public class CubeList // We named that way since it is a list of cubes.

{

   public Cube head;

   public Cube tail;

   public int length;

   public CubeList(int value, GameObject cube)

   {

      Cube newcube = new Cube(value, cube);

      head = newcube;

      tail = newcube;

      length = 1;

   }
}

I have initialized the list with the head on the scene since I want to attach a camera and make some arrangements. At the start method, create an instance from CubeList class by

cubeList = new CubeList(0, headCube); //0 is chosen as a starting value. Now we can append the CubeList with

public void append_cube(int value, GameObject cube)

{

   Cube newcube = new Cube(value, cube);

   if(head == null){

      head = newcube;

      tail = newcube;

   } else {

      tail.next = newcube;

      tail = newcube;

   }

   length++;

}

Now we need to spawn cubes in a random area and detect hits so that we can append our CubeList instance every time we hit a cube.

private void SpawnCubesToAppend()

{

   GameObject randomCube =  GameObject.CreatePrimitive(PrimitiveType.Cube);

   randomCube.AddComponent<HitDetector>(); 

   //Define positions to spawn

   //Define text on cube

   //Define other attributes

}

And detect hits with

private void OnCollisionEnter(Collision collision)

{

   if (collision.gameObject.tag == “Head”)

   {

      Destroy(this.gameObject);

      Main.instance.AppendCubesWithHit(Main.instance.value);

      Main.instance.cubeOnStage = false;

   }

}

As it detects a hit, it calls the AppendCubesWithHit method.

public void AppendCubesWithHit(int value)

{

   GameObject cube = GameObject.CreatePrimitive(PrimitiveType.Cube);

   GameObject myText = new GameObject();

   cube.transform.position = cubeList.tail.body.transform.position;

   cubeList.append_cube(value, cube);

   //Define other desired attributes

}

I wanted to keep things separate in the body and soul of the list. Therefore used my C# implementation in monobehavior class separately.

You can implement remove, pop, etc. methods and apply them to monobehavior class similarly.

We created nodes, list now we define how to move the list. In our case, we have two fundamental movements. Head moves and tail follows.

For the movement of the head node, we use MoveTowards method.

cubeList.head.body.transform.position = Vector3.MoveTowards(cubeList.head.body.transform.position, cubeList.head.body.transform.position + moveDirection, 0.1f);

In this setting, we need to rotate the moveDirection vector to rotate the head movement. Somehow we need to find a generalized method that is robust. Every time we press the key to turn right, we rotate 90 Degrees.

And rotating to left is similar. So we can implement it as follows:

float a = moveDirection.x;

float b = moveDirection.y;

float c = moveDirection.z;

moveDirection = new Vector3(c, b, -a);

And we shift the tail with

private void TranslationMethodForTail()

{

   Cube tmp = cubeList.head;

   if (cubeList.head.next != null){

   Cube follower = tmp.next;

   while (follower != null)

      {

         if (Vector3.Distance(follower.body.transform.position,    tmp.body.transform.position) > 1.2)

         {

   follower.body.transform.position =    Vector3.MoveTowards(follower.body.transform.position,  tmp.body.transform.position, 0.1f);

         }

      tmp = tmp.next; 

      follower = follower.next;

      }

   }

}

So that as the head moves, our temporary variables tmp and follower traverse through the list, and makes follower node move towards the tmp if the euclidian distance is greater than a predefined constant; 1.2 in our case, ensuring the follower and current node is as close as 1.2 meters in each traverse, seemed to me a pretty expensive setup in terms of computational resources but this will give us a smooth movement, directly towards the next node, different than Nokia 3310 snake game.

We are done with the rotation of our head node, but we also would want the camera position to change every time we rotate the head of the snake. We have four camera positions to change sequentially, how can we solve this problem? An expensive but fancy solution would be using a circular doubly linked list.

To use it, again first we decide what data we will carry in our Node. In this case, we carry a vector to carry the local position for camera placement and two pointers for the next and previous nodes that are linked to a specific node.

Now we follow the same approach for the solution to this problem

[SerializeField]

public class DNode

{

   public Vector3 vector3D;

   public DNode next;

   public DNode prev;

   public DNode(Vector3 i)

   {

      vector3D = i;

      next = null;

      prev = null;

   }

}

public class CircularDoublyLinkedList

{

   // Start is called before the first frame update

   public DNode head;

   public DNode tail;

   public int length;

   public CircularDoublyLinkedList(Vector3 value)

   {

      DNode newnode = new DNode(value);

      head = newnode;

      tail = newnode;

      length = 1;

   }

}

at this point, you may create an instance of this class either manually or write an append method.

public void AppendFromHead(Vector3 value)

{

   DNode tmp = new DNode(value);

   if (head == null)

   {

      head = tmp;

      tail = tmp;

   }

   tail.next = tmp;

   tmp.next = head;

   head.prev = tmp;

   tmp.prev = tail;

   head = tmp;

   length++;

}

And declare

private CircularDoublyLinkedList circularCameraLocalPositions;

circularCameraLocalPositions = new CircularDoublyLinkedList(new Vector3(-2, 2, 0));

circularCameraLocalPositions.AppendFromHead(new Vector3(0, 2, 2));

circularCameraLocalPositions.AppendFromHead(new Vector3(2, 2, 0));

circularCameraLocalPositions.AppendFromHead(new Vector3(0, 2, -2));

tmpCamera = circularCameraLocalPositions.head;

Every time you hit the right button, use

tmpCamera = tmpCamera.next;
mainCamera.transform.localPosition = tmpCamera.vector3D

and the left is similar

tmpCamera = tmpCamera.prev;
mainCamera.transform.localPosition = tmpCamera.vector3D;

So that camera moves smoothly every time we press the right and the left buttons.

This is what the solution with a circular doubly linked list looks like.

I believe this post gives a clue as that what can we do with a linked list in game development and how can we implement it. Please feel free to write for any kind of discussion and comments, so that I can improve myself, correct my mistakes and hopefully learn from you.

Best wishes.