Building Game Worlds: Data Structures

Why Linked Lists for a Game World?

Your game world—its rooms, items, and characters—is dynamic. A player might drop an item, an enemy might be defeated, or a new area might become accessible. While arrays are excellent for fixed-size collections, they become cumbersome when you need to frequently add or remove elements. Resizing an array (as we'll see in a later module with realloc) can be an expensive operation.

Linked lists offer a natural solution. Each element, or node, is an independent piece of memory that simply holds a pointer to the next one in the sequence. This structure allows for efficient insertion and deletion of elements anywhere in the list, making it ideal for managing inventories, quest logs, or, as we'll do today, the contents of a room.

The following video provides an excellent introduction to the concept of a singly linked list and how to define the necessary data structures in C.

Designing Your World's Data Structures

To build our game world, we need to represent two primary entities: Items and Rooms. Let's apply the linked list concept to create a flexible structure for them. A great practical example of this approach can be found in the blog post "Implementing Solitaire in C," which uses linked lists to manage piles of cards.

Inspired by these examples, we can define our own structures in a new header file, world.h:

1. struct Item: A simple struct to hold data about an item, like its name and description. This is our "payload".
2. struct ItemNode: This is the linked list node. It's a self-referential struct that contains a pointer to an Item and a next pointer to the next ItemNode.
3. struct Room: This struct represents a location. It will have a name, a description, pointers to adjacent rooms (e.g., north, south, east, west), and, crucially, a pointer to the head of a linked list of items currently in that room.

Here is what these definitions will look like in world.h:

// In world.h

#ifndef WORLD_H
#define WORLD_H

// The data payload for an item
typedef struct Item {
    char* name;
    char* description;
} Item;

// A node in the linked list of items
typedef struct ItemNode {
    Item* item;
    struct ItemNode* next;
} ItemNode;

// A room in our world
typedef struct Room {
    char* name;
    char* description;
    ItemNode* items; // Head of the list of items in the room
    struct Room* north;
    struct Room* south;
    struct Room* east;
    struct Room* west;
} Room;

#endif // WORLD_H

Notice how Room contains an ItemNode* items pointer. If items is NULL, the room is empty. Otherwise, it points to the first item in the room, which in turn points to the next, and so on.

This diagram shows a LinkedList struct with a head pointer, analogous to our Room struct's items pointer. The head points to the first node, which contains data and a pointer to the second node. The final node's next pointer is NULL.

Implementing Core Linked List Operations

With our structs defined, we need functions to manage them. The most fundamental operation is adding a new item to a room's item list. This is often called "appending" or "pushing" to the list. The logic involves two main cases:

1. The list is empty: The new node becomes the head of the list.
2. The list is not empty: We must traverse the list until we find the last node, and then link the new node after it.

Mike Shah's video provides a fantastic, step-by-step implementation of this exact logic.

Traversing and Freeing the List

Once items are in a list, you'll need to traverse it to see what's there. This is how you'll implement the look command—by printing the room's description, then iterating through its item list and printing each item's name.

Even more importantly, since you are dynamically allocating memory for each node with malloc, you are responsible for freeing it. Failing to do so results in a memory leak. Freeing a linked list requires a careful traversal where you don't free a node before you've retrieved its next pointer. A common, safe technique uses two pointers: one to the current node to be freed, and one to the next node to preserve the link.

Your Implementation Task

Now it's time to integrate these concepts into your capstone project. You will create a small, two-room world.

1. Create new files: world.h and world.c.

   • Add the struct definitions from above into world.h. Also add function declarations for the functions you will write in world.c.
   • In world.c, you will #include "world.h" and implement the functions.

2. In world.h, add these function declarations:

   // Function declarations
   Room* createRoom(const char* name, const char* description);
   Item* createItem(const char* name, const char* description);
   void addItemToRoom(Room* room, Item* item);
   void linkRooms(Room* room1, Room* room2, const char* direction);
   void freeWorld(Room* currentRoom);
   

3. In world.c, implement the functions:

   • createRoom and createItem: These functions should malloc memory for the respective struct, use strcpy (after allocating memory for the strings too!) to copy the name and description, and initialize pointers to NULL. They should return a pointer to the newly created struct.
   • addItemToRoom: Implement the append logic discussed in the video. You'll need to malloc an ItemNode, set its item pointer, and then link it into the room's items list.
   • linkRooms: A helper function to connect two rooms. For example, linkRooms(room1, room2, "east") would set room1->east = room2; and room2->west = room1;.
   • freeWorld: This is your cleanup function. It needs to be clever. To free the entire world, not just one room, you'll need to traverse all linked rooms. A simple approach for now: assume your world is a simple chain. It should first free the list of items in the current room (using the two-pointer method), then free the room's string data, then free the Room struct itself, and finally move to the next room in the chain to repeat the process.

4. Update game.h and game.c:

   • In game.h, add #include "world.h". Modify parseAndExecute to take the current room: bool parseAndExecute(char* input, Room** currentRoom);. We use a double pointer Room** so the function can change which room the player is in.
   • In game.c, update the look command to call a describeRoom helper function that prints the room's name, description, and then iterates through and prints the names of all items in its items list. Update the go command to change the *currentRoom pointer (e.g., if (strcmp(noun, "north") == 0 && (*currentRoom)->north != NULL) { *currentRoom = (*currentRoom)->north; }).

5. Update main.c:

   • Create a Room* currentRoom pointer.
   • Before the main loop, create two rooms and an item. Link the rooms and add the item to one of them. Set currentRoom to point to the starting room.
   • Inside the loop, call describeRoom(*currentRoom) at the start of each turn.
   • Pass &currentRoom to parseAndExecute.
   • Crucially, after the loop finishes, call freeWorld() on your starting room to clean up all allocated memory.

Run make and execute your program. You should be able to look and see the room and its item, and go between the two rooms. Finally, run valgrind ./adventure. The goal is to see the message: "All heap blocks were freed, no leaks are possible."

Conclusion

You have now laid the structural foundation of your game world. By using linked lists, you've created a dynamic and scalable system for managing game entities.

Key Takeaways:

• A linked list is a dynamic data structure composed of nodes, where each node contains data and a pointer to the next node.
• A non-intrusive list design separates the data payload (e.g., Item) from the list mechanics (ItemNode), leading to cleaner code.
• Appending to a list requires checking if the list is empty (head == NULL) or traversing to the end to add the new node.
• Safely deallocating a linked list requires a two-pointer traversal to avoid accessing freed memory.
• Valgrind is an essential tool for verifying that your program has no memory leaks.

In the next lesson, we will build upon this foundation. With a world of interconnected rooms now in place, we will refine the player movement logic and expand the look command to inspect not just the room, but specific items within it, bringing your game one step closer to interactive life.