Over the course of the 2018 r/roguelikedev Tutorial Tuesday Challenge I decided to invest some time learning some fundamental programming concepts that I probably should have learned years ago. The fun (and challenging) part of being a hobby programmer is that most of my learning comes from books, and then random tutorials on the internet. Somewhere in the course of my “education” I never learned about basic data structures and how they can be used.

Around week three of the challenge I decided to implement a scheduling system for Barbarian - which led me to learn about creating lists and priority queues. STL has std::priority_queue, but like many STL classes never seems to want to play nicely with my code. Again, likely a byproduct of me learning C++ from a book and probably not the fault of STL.

This is my very first attempt at writing a tutorial - expect some errors and feel free to comment with any corrections. I will absolutely guarantee that there is probably a better way of doing what I’ve written here, so don’t read this as gospel.

Making a List

A list is a fantastic data structure - and is so simple to implement I’m not sure why it was never included in the beginning programming books I have read. A list is an ordered collection of nodes, where each node has some data and a pointer to the next node. The list has a head and a tail - the very first and very last nodes in the list. That’s it! That’s all they are.

Head
 A ---> B ---> C  <- Node
 1      2      3  <- Data
              Tail

Definining a node is simple, and using the power of C++ templates you can make a node hold any data you can imagine!

template <typename T>
class Node
{
    public:
        Node(T d) : data(d) { next = NULL; prev = NULL; }
         
        T data;
        Node * next; 
        Node * prev;
};

Then to create the list all we need is a couple of functions - one to add nodes and one to remove nodes.

template <typename T>
class List
{
    public:
        List(); // Default constructor
        List(T data); // Alternate constructor
        List(const List<T> & other); // Copy constructor
        List<T> operator =(const List<T> & other) // Copy assignment using copy/swap idiom
        {
            swap(*this, other);
            return *this;
        }
        friend void swap(List<T> & first, List<T> & other)
        {
            List<T> * temp = first.head;
            first.head = other.head;
            other.head = temp;
        }
        ~List(); // Custom destructor
        
        
        void push(T data); // Add a node
        T pop(); // Remove head

        Node<T> * head;
}; 

Now, the definition of List<T> has a copy constructor, copy assignment, and custom destructor following the C++ rule of 0/3/5 - yet another very important thing that seemed to be glossed over or missed in the books I read. Basically, it’s a good idea if you have to assign memory (or use smart pointers) to have a custom destructor to make sure that memory is freed appropriately. If you have a custom destructor, the program needs a way to make a copy of your object from another object and a way to figure out what ListA = ListB means. The constructors look something like the following.

template <typename T>
List<T>::List()
{
    // Create an empty list
    head = NULL;
}   

template <typename T>
List<T>::List(T data)
{
    // Create a list, with T data
    push(data);
}   

template <typename T>
List<T>::List(const List<T> & other)
{
    // Copy constructor
    // Iterate through the other list, adding that list's data to this list
    for(Node<T> * node = other.head; node != NULL; node = node->next)
    {
        push(node->data);
    }
}

Easy enough! One cool thing to notice here is the way we iterate through the list. The for loop is initialized by creating a Node<T> * variable that is initialized to the head of the list, and while that variable does not equal NULL we execute the following and then set the variable to the next node.

The destructor loops through the list in a slightly different way, removing nodes as it goes.

template <typename T>
List<T>::~List()
{
    Node<T> * node = head;
    Node<T> * next;
    
    while(node != NULL)
    {
        next = node->next;
        delete node;
        node = next;
    }
}

With all that settled, all that’s left is adding the functions to add and remove nodes from the list!

template <typename T>
void List<T>::push(T data)
{
    Node<T> * newNode = new Node<T>(data);
    if(head != NULL)
    {
        newNode->next = head;
        head->prev = newNode;
    }
    head = newNode;
}

template <typename T>
T List<T>::pop()
{
    T result = T();
    if(head) // if head is NULL this returns false, same as 'head != NULL'
    {
        result = head->data; // Get result 
        Node<T> * temp = head; // Store a pointer to the current (old) list head
        head = head->next; // Set the list head to the next item
        head->prev = NULL; // The head has no previous node
        delete temp; // Delete the old list head
    }
    return result;
}

Again, nothing too complicated - and that’s all that’s needed for a basic list! As is, however, this list is not very useful… so lets add a couple of more functions! (Don’t forget to add the declarations in the class definition)

// It's pretty common to want to remove a specific node from the list,
//  here's an idea of how that can be accomplished:
template <typename T>
void List<T>::remove(Node<T> * node)
{
    // If for some silly reason this function is called with NULL
    // this prevents an annoying segfault.
    if(!node) return; 
    if(!head) return; // If there's nothing in the list, we can't remove a node from it
    if(head == node)
    {
        // If we delete the head, we need to set the head to the next item in the list
        head = node->next;
        if(head) head->prev = NULL; // If head still exists, it has no previous node
    }
    if(node->next != NULL)
    {
        // The next item's previous has to point to this item's previous 
        // Eg: A->B->C
        // Remove B, so C's previous has to be A
        node->next->prev = node->prev;
    }
    if(node->prev != NULL)
    {
        // The previous item's next has to point to this item's next
        // Eg:: A->B->C
        // Remove B, so A's next has to be C
        node->prev->next = node->next;
    }
    delete node;
}

// A few other common things that are pretty useful
//  and simple to implement:
// - Determining the size of a list
// - Determining if the list is empty
// - Getting a specific item from a list
template <typename T>
int List<T>::size()
{
    int result = 0;
    for(Node<T> * node = head; node != NULL; node = node->next)
    {
        result++;
    }
    return result;
}

template <typename T>
bool List<T>::isEmpty()
{
    return (head == NULL);
}

template <typename T>
Node<T> * List<T>::at(int index)
{
    Node<T> * result = NULL;
    
    int count = 0;
    for(Node<T> * node = head; node != NULL; node = node->next)
    {
        if(count == index)
        {
            result = node;
            break;
        }
        ++count;
    }
    return result;
}

With those additions you now have a nice, full featured, doubly-linked list! You could easily change this into a circular list by making the head node’s previous point to the tail, and the tail’s next point to the head. All you would need to do is add in a function to find the tail (ie: iterate through list, return the last node).

How Barbarian! Uses Lists

Since learning about lists and writing a few different implementations, I obviously tried to find any place in the code where a list would be useful. The engine runs through a standard Events-Update-Draw loop, and during each of these functions it’s necessary to run through a list of entities. This was stored in a std::vector<Entity>, but one of the (many) shortcomings of the STL vector is that it can’t arbitrarily remove items. What happens when an entity dies? Do we just create a whole new vector for the engine’s entity list? Heck no. Using a doubly linked list like the one above it’s a simple matter to cull the entity list of dead entities.

Another very useful place that Barbarian uses lists is in path finding - making a list into a priority queue is a simple matter of adding a ‘priority’ to a node, then when pushing a new node onto the stack making sure to add the node in the correct place according to it’s priority. Greedy breadth first search, Dijkstra, and A-star path finding all use a priority queue.

Entity and item placement use weighted lists, which is a list whose nodes have a weight and has a function to pick a random piece of data from a node.

template <typename T>
T WList<T>::pick(RNGState * rng)
{
    T result = T();
    int totalWt = 0;
    for(WNode<T> * node = head_; node != NULL; node = node->next)
    {
        totalWt += node->weight;
    }

    int choiceWt = randomInt(0, totalWt, rng);
    int runningWt = 0;

    for(WNode<T> * node = head_; node != NULL; node = node->next)
    {
        if(runningWt + node->weight >= choiceWt)
        {
            result = node->data;
            break;
        }
        runningWt += node->weight;
    }
    return result;
}

The scheduling/time management system uses a list - it’s not currently used in the game, but the functionality is there. Basically, every time the game updates, entities are granted some energy. When they pass a certain energy threshold they get put on a list. Then, the game makes sure that each entity on that list gets to take a turn before granting energy to any other entity.

The inventory component of an entity is another great place for a list - and one of the places where a STL vector would only work with a bunch of trade-offs and mashing square pegs into round holes. The player has to be able to pick up and add items to their inventory, and remove arbitrary items by using or dropping. Using a list makes those things easier. Heck, a priority queue could be used with each category of item at a different priority to easily sort the inventory screen (and to be honest, I literally just thought of that while typing this post - definitely adding that to the ‘to-do’ pile).

Anywhere in the game where I need a collection of something, I try and use a list. The fun part about that is that I’ve ran into times where my list class doesn’t have some functionality that I want - but it’s a piece of cake to add it.

The game map (and virtual console) could be stored as a list as well, since it’s currently stored as a one dimensional vector. Assuming a Cartesian grid, the (x,y) coordinates correspond to the index of a list by x + (y * width) - map->at(x + (y*width)) for example, or if using a simple array map[x+(y*width)]. I have not changed Barbarian to use lists in this manner, but I see no reason why it would not work. The great part about these lists is that they manage their own memory like a STL vector but have more useful functionality.

Barbarian is a turn based game, and does not need to run at break neck speeds and efficiency - I have no idea how these lists compare in speed to STL offerings. They work quickly and efficiently enough on my older hardware, so with modern systems they would work just as well.

Hopefully this gives an idea of how neat this simple little data structure can be. Give them a try! See how they work in your own project, at the very least you’ll learn something useful and have the satisfaction of having built an incredibly useful tool yourself.