Using Linked Lists to Represent Game Objects

Using Linked Lists to Represent Game Objects
by Jackson Allan

One of the first problems I ever encountered as a beginning programmer was this: "How can I store an undefinable, ever changing number of objects that I must create and destroy at unknown moments throughout the game play?" By objects, I mean 'game objects' – enemies, bullets, weapons etc. At the time, I was totally newb and had no idea what a pointer really was, let alone a linked list. So I googled it, reviewed the results, and started on a template that I still use in just about every application I create to this day.

What amazed me at the time was that of all the tutorials I came across, of all the explanations I looked up upon, not a single one showed me how to put these alien 'linked lists' to practical use. The purpose of this article is not so much to explain the workings of a linked list, but to teach exactly how they can be used in a game environment. The only requirement is a good understanding of pointers, and some experience with C++.

I will begin by explaining the basics of a linked list. It is a chain of data that can be added to / taken from at any point throughout the program. Think of a linked list as a train (common example): a head carriage at both ends, and numerous cars connected in between. Perhaps it is better to describe with a diagram:

As shown, a linked list is a string of data snippets, connected by standard pointers (represented by the lines connecting the boxes) – thus the name 'linked list', a list of data that is linked together. The head and tail are pointers that allow access to the chain. Each individual snippet of data is normally called a 'node'. Take a look at this:

struct node
{
  int x;
  int y;
  node* next;
};

node* head=NULL;
node* tail=NULL;

This is a potential link-list. Picture a train of nodes, of which we can enter using the 'head', and then travel down until the last node reached. Before we begin dealing with the list, we must first insert a few nodes onto the chain. This is done using the 'new' keyword (MSVC++):

head = new node; //this tells the program to make the head pointer
                 //point to a new node
head->x=0; //the new node's x value is 0
head->y=0; //the new node's y value is 0
head->next=NULL; //NULL indicates that there are no nodes beyond this node
tail= head; //there is only one node on our list, so tail must equal
            //the head

Below I have illustrated the scene:

As indicated, both head and tail pointers point to a single node. Add this code to the snippet above, and a linked list begins to take form.

head->next = new node;
tail = head->next;
tail->x=0;
tail->y=0;
tail->next=NULL;

And a diagram:

The head points to our original node, and that node is now connected to another node via the 'next' pointer. This second node becomes the tail. Add this code to the collection, and we have four nodes on our list:

tail->next = new node;
tail = tail->next;
tail->x=5;
tail->y=9;
tail->next = new node;
tail = tail->next;
tail->next=NULL;
tail->x=24;
tail->y=50;

This diagram represents our list (drawn with greater detail than before):

The linked list now holds four nodes, and on we can continue to add new nodes on at our desire. However, once a piece of memory is allocated using the 'new' keyword, it must be deleted after use (often on application shutdown) using the 'delete' keyword. I will not go into this just yet, for I will show exactly how it is done a little later in this article.

Do not worry too much if you are a little lost at this point. It is not necessary that you fully understand the concept of linked lists – the understanding will come as you begin to use them. I have breezed through this section, simply because I wish to get into the gut of this article – explaining how linked lists can be used to represent objects in a game.

I should mention the abilities/flexibilities of a linked list, as well as the common alternative – the array. A linked list can be used for anything and everything inside your game world – characters, monsters, projectiles, particles, items, trees… whatever you wish. Adding new objects is exceptionally easy once we have a function set-up to do it for us, as is organising, updating and rendering the objects to the screen. More on that later.

Arrays are a good way to store data when you know exactly how much data you will need to store. For example, if you were to build a platform-style game where, in every single level, exactly ten monsters exist, you might find an array suitable enough. But would it not be better if you could simply add/delete monsters to your liking? Arrays are messy in situations like this, and should be avoided.

Before constructing a set of functions that can deal with our game objects, we must first consider and decide what functions we will want. Here is a standard set that deal with 'bullets':

Bullet* NewBullet(int x, int y); //Add a bullet
void UpdateBullet(); //Update all bullets
void RenderBullet(); //Draw our bullets
void DeleteAllBullet(); //Clear out the entire list of bullets

"Where is the DeleteBullet(Bullet* blt) function?" you may ask. It doesn't exist. I find that the best and easiest way of removing nodes from the list is to do it in the RenderBullet() function (ie combining the rendering function with the deleting function), but once again, I will explain it more fully further into this text. For now, I will describe the use of each function:

Bullet* NewBullet(int x, int y)
Creates a new 'Bullet' at x,y.

As shown, the return type is a pointer to the Bullet created. This is not exactly necessary because the new Bullet will always be the tail of the list (where we can access it from), but when dealing with lists inside classes using the returned pointer simplifies things a little.

void UpdateBullet()
The update function is called every game-loop. This is where one would put the main code defining a Bullet's behaviour.

void RenderBullet()
As you might have guessed, this function is called at the end of the game-loop, rendering all the bullets to the screen. Also, this is where we delete any bullets that have expired/are no longer needed etc.

void DeleteAllBullet()
This function will remove every bullet (node) on the list. One would call it when the game ends/a new level is reached… any time we want to clear our linked-list.

So lets revise those functions – you will use a set similar to these in most cases:

Object* NewObject(parameters etc)
void UpdateObject()
void RenderObject()
void DeleteAllObject()

'Object' is to be replaced with whatever… monster, bullet, character… any of your game objects. So far you have only seen the prototypes. I will now list the body of each function, and describing how they operate. In these examples I give, I am using a 'bullet' as basis for the linked list, as seen in a 2D vertical scrolling game (the reason being the simplicity of the Update function for an object like this). Also note that I am using a doubly linked list, meaning that each node has not only a 'next' pointer (which directs to the next node in the list), but also a 'previous' pointer, directing backwards to the node before the one we are dealing with. I believe this eases the process of deleting nodes. Here is the base code:

struct Bullet
{
  float x; //The x position of the bullet
  float y; //The y position of the bullet
  bool dead; //'dead' is a variable I that each object should have.
             //When set to true, the Render loop know that this bullet
             //needs to be deleted
  Bullet* next; //The next bullet (node) on the list
  Bullet* previous; //The previous node on the list
};

Bullet* firstBullet=NULL; //The head of the list
Bullet* lastBullet=NULL; //The tail

'Bullet' is a structure (I normally use structures when designing linked lists), but as an alternative, it could be a class (with a few adaptations to the rest of the code). The 'x' and 'y' variables hold the coordinates of each bullet. 'next' and 'previous' are the pointers that link the nodes together. And finally, 'dead' is a bool that we would set true whenever we want to destroy a particular bullet.

The 'firstBullet' and 'lastBullet' pointers are the head and tail – this is where the linked list is stored.

Here is the add function:

Bullet* NewBullet(float x,float y)
{
  if(firstBullet==NULL) //In this case we are adding the first node
                        //to the list
  {
    firstBullet=new Bullet; //Make a new node and assign the head to it
    lastBullet=firstBullet; //There are no other nodes on the list,
                            //therefore the tail must equal the head
    lastBullet->next=NULL; //Next must point to nothing
    lastBullet->previous=NULL; //There are no nodes behind us, so previous
                               //also points to nothing
  }
  else
  {
    lastBullet->next=new Bullet; //Add a new node onto the end of the list
    lastBullet->next->previous=lastBullet; //The new node's previous pointer
                                           //should point the node before it
    lastBullet=lastBullet->next; //Shift the tail to the end of the list
    lastBullet->next=NULL; //Next must point to nothing
  }
  lastBullet->x=x; //X shall equal the parameter passed into the function
  lastBullet->y=y; //Likewise, so should y

  lastBullet->dead=false; //This is false… we only set it true when we
                          //want the bullet destroyed
  return lastBullet; //Finally, return a pointer to the new bullet
}

The 'NewBullet()' function is to be called whenever we wish to create a new bullet during game-play. Here is the update function:

void UpdateBullet()
{
  Bullet* thisBullet=firstBullet; //thisBullet is a pointer used to access
                                  //the list. We set it to firstBullet
                                  //(list head), and then move it through
                                  //the list, updating each node as we go
  while(thisBullet!=NULL)  //While we are not at the end of our list
  {
    thisBullet->y-=2;  //Move this bullet up the screen
    if(thisBullet->y<0)
      thisBullet->dead=true; //If this bullet is off the screen then it
                             //must be destroyed (deleted from list)

    thisBullet=thisBullet->next; //NEVER FORGET THIS LINE
  }
}

We transverse through the linked list using the 'thisBullet' pointer to access and update the data stored in each individual node.

"thisBullet=thisBullet->next" – try not to ever forget this line of code. Do so and you will freeze your computer with a never-ending 'while' loop. As you would assume, this line pushes the 'thisBullet' pointer forward to the next node.

This is the 'RenderBullet()' function:

void RenderBullet()
{
  Bullet* thisBullet=firstBullet; //We will be needing this again
  Bullet* deadBullet=NULL; //The 'deadBullet' pointer is used when we
                           //delete a node from the list
  while(thisBullet!=NULL)
  {
    if(thisBullet->dead) //If this node is 'dead' (dead is set to true)
                         //then we will want to remove it from the list
    {
      deadBullet=thisBullet; //Set deadBullet to thisBullet
      thisBullet=thisBullet->next; //Move thisBullet forward to the
                                   //next node

      if(firstBullet==deadBullet) //Allow for special circumstances
      {
        firstBullet=thisBullet;
        if(thisBullet!=NULL)
        {
          thisBullet->previous=NULL;
        }
      }
      else //And re-link the list
      {
        deadBullet->previous->next=thisBullet;
        if(thisBullet!=NULL)
        {
          thisBullet->previous=deadBullet->previous;
        }
      }
      if(lastBullet==deadBullet)
      {
        lastBullet=deadBullet->previous;
      }
      delete deadBullet; //Finally, the delete keyword is used to free
                         //this node from memory, thereby deleting the
                         //bullet from our list
    }
    else
    {
      //This is where one would insert his/her rendering code, drawing
      //the bullet to the screen (normally a backbuffer) using whatever
      //graphics library…
      thisBullet=thisBullet->next; //Do not forget this
    }
  }
}

What you see here is really two functions combined into the one. Basically, for each bullet, the function first checks to see if the bullet is actually alive (ie does not need to be removed), and if it is, the function renders the bullet into the game world. However, if the bullet is 'dead', then the function first re-links the surrounding nodes so as not to create a gap in the list, then it safely deletes the bullet from memory. By combining a delete function with a render function, you are thereby solving the problem (that you likely will never face) when you find that the update function conflicts with itself. What I am meaning is that sometimes certain game objects will refer to each other inside the update loop, and as soon as you begin to delete objects from within the loop certain pointers may become invalid and this is always messy. The cleanest, most straightforward way of avoiding this problem (which I first experienced while programming squad-based AI) is to simply not delete anything until the information stored in each node is unpdated. Therefore, the deleting is executed by the render function, which will normally be called at the end of the game loop. Got that? Not to worry, you need not understand a single word of it. However, it is important to understand that whenever you wish to delete a node, you must set it's 'dead' bool true, and the render function will take care of it for you.

Finally, the 'DeleteAllBullet()' function to clear out the list:

void DeleteAllBullet()
{
  Bullet* thisBullet=firstBullet;
  Bullet* deadBullet=NULL; //Seen these before
  while(thisBullet!=NULL)
  {
    deadBullet=thisBullet; //Dead is the current node
    thisBullet=thisBullet->next; //Move thisBullet forward
    delete deadBullet; //Delete dead
  }
  firstBullet=NULL; //Reset the head
  lastBullet=NULL; //And reset the tail
}

Simple. Call this function whenever the need arises to delete every bullet.

That said, I will stress the fact of this:

All memory allocated must be deleted.

This means that whenever you create a new game object you must remove it at some point. Failing to do so will result in a memory leak (bad). However, ensuring that all nodes created are deleted is a relatively simple process – just call the delete-all function as your program shuts-down. Make a habit of it.

So that is it… the basic template of which you can build your game objects upon. And more. Linked lists can be used so widely that I will not even begin to give examples outside of a game environment. Whenever you need to store an undefined, ever changing amount of data the linked list option is about the best you can do. However, I believe I should mention that linked lists are not appropriate for anything and everything. Here are two examples describing what not to use linked lists for (normally in favour of arrays):

Terrain, trees, plants, 2D tiles etc in an overhead game (such as an RPG or RTS)…

Normally you will want to store data like this in an array. Arrays allow ultra-fast access and are normally better in a case like this.

Player information…

Unless programming a multiplayer LAN or Internet game, it is most likely that you will not need to account for more than one or two players. Therefore, a linked list in a situation like this would be a pointless effort.

As a closing feature, I will add the mere shell-forms of the functions above, of which I suggest you copy and paste into your projects (as opposed to rewriting the code, although that said I suppose by typing it all out yourself you will learn the most from it all):

struct Object
{
  bool dead;
  Object* next;
  Object* previous;
};

Object * firstObject =NULL;
Object * lastObject =NULL;

Object* NewObject()
{
  if(firstObject==NULL)
  {
    firstObject=new Object;
    lastObject=firstObject;
    lastObject->next=NULL;
    lastObject->previous=NULL;
  }
  else
  {
    lastObject->next=new Object;
    lastObject->next->previous=lastObject;
    lastObject=lastObject->next;
    lastObject->next=NULL;
  }

  lastObject->dead=false;
  return lastObject;
}

void DeleteAllObject()
{
  Object* thisObject=firstObject;
  Object* deadObject=NULL;
  while(thisObject!=NULL)
  {
    deadObject=thisObject;
    thisObject=thisObject->next;
    delete deadObject;
  }
  firstObject=NULL;
  lastObject=NULL;
}

void RenderObject()
{
  Object* thisObject=firstObject;
  Object* deadObject=NULL;
  while(thisObject!=NULL)
  {
    if(thisObject->dead)
    {
      deadObject=thisObject;
      thisObject=thisObject->next;
      if(firstObject==deadObject)
      {
        firstObject=thisObject;
        if(thisObject!=NULL)
        {
          thisObject->previous=NULL;
        }
      }
      else
      {
        deadObject->previous->next=thisObject;
        if(thisObject!=NULL)
        {
          thisObject->previous=deadObject->previous;
        }
      }
      if(lastObject==deadObject)
      {
        lastObject=deadObject->previous;
      }
      delete deadObject;
    }
    else
    {
      //Add you code here
      //This is where your objects are rendered into the game world

      thisObject=thisObject->next;
    }
  }
}

void UpdateObject()
{
  Object* thisObject=firstObject;
  while(thisObject!=NULL)
  {
    //Add your code here
    //This is where you define the behaviour of your objects

    thisObject=thisObject->next;
  }
}

//And a quick addition:
int CountObject()
{
  Object* thisObject=firstObject;
  int count=0;
  while(thisObject!=NULL)
  {
    count++;
    thisObject=thisObject->next;
  }
   return count;
}
//This function return the number of nodes currently on the list.
//However, a more efficient way to keep track of this information
//is to use a global int and add to it every time a object is
//created, and remove from it every time an object is deleted

If you have any questions or inquiries regarding this article please contact me. My email is currently: jack_1313@optusnet.com.au

Discuss this article in the forums

Date this article was posted to GameDev.net: 1/13/2004
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Data Structures
Sweet Snippets