Maze Game with Dynamic Paths

In the chapter on indirectly accessing values we started to build out a maze game. The idea of this was to have rooms that were connected by different paths. This is a great way of working with pointers, as the player could point to the room they were in, and paths can point to their destinations.

One of the limitations of the maze game at that point was that we didn’t yet have arrays. Now that we have arrays, and our own dynamic array, we can return to the maze and add the paths into each room. In this way, each room can have its own paths that lead to other locations in the maze.

Recap

The maze game involved locations (rooms) connected by paths. For this we created the following structs:

typedef struct room_data *room_ptr;

struct path_data
{
  string    description;
  room_ptr  destination;
};

struct room_data
{
  string title;
  string description;
};

Each room had a title and description, and each path had a description and destination. The location of the player and the path destinations were all handled by using pointers to rooms.

Now that we have a dynamic array, we can expand our solution to include multiple paths within each room.

Note

We could also redo the solution to embed member functions within the room and path structs. For now, we will not change the rooms to use member functions, but just embed the dynamic array we have created.

Adding Paths

Adding multiple paths to a room is as simple as adding a paths field to the room_struct. Doing this will mean that we then need to update the new_room code to make sure it initialises the result with an empty dynamic array.

The following code shows how you can create an empty dynamic array. The {} can be used to create empty path data to be used as the default if needed.

room_data new_room(string title, string description)
{
  room_data result = {
    title,
    description,
    dynamic_array<path_data>(0, {})
  };

  return result;
}

In main we had created a number of rooms and paths. You can now move the paths into a room. In my case, I am going to put my existing paths into room 1. Then I can add some more paths to the other rooms.

The code to add a path to a room would look like this:

path_data p1 = new_path("A large sliding door", &r2);
// becomes
r1.paths.add(new_path("A large sliding door", &r2));

At this stage we have rooms that now contain a variable number of paths that lead to other rooms in the maze.

Printing the room

With paths in a room we now need to change the code for printing a room so that it prints all the paths in the room as well.

We already have the code to print a path. So you can code this with a for loop where you access each path from room->paths, and pass it to the print_path procedure we previously created.

Tip

Remember you can use room->paths.size to get the number of paths to be printed.

I suggest you add a message above this list of paths saying something like “There are paths leading:”. This will let the user know what the list refers to.

Now you can remove the printing of paths from main, as this is all done in print_room now.

Exploring the maze

The player will be in the current_room. Now that the room has paths, we can ask the user which path they want to take. As they move around they will see the different paths in the different rooms.

To code this, let’s create an explore procedure. This can take a parameter for the room_ptr where the player is located. As we want to update this, we need to pass this pointer by reference in the same way we have with move_player. This will mean we can update the passed in room pointer.

Pointer by reference?

Yes, you can pass a reference to a pointer. As you recall, a reference is just a pointer itself. So this is now, in a way, a pointer to a pointer.

If you want to work with the pointers yourself, you can create a pointer to a pointer using room_data **.

Within explore, we can print the room, then read in the path the user wants to take. The index they provide us can then be used to access the path that the player should move through.

If the room pointer is in a current_room variable, and we read the path the user chooses into an option variable, then we can achieve this move using:

move_player(current_room, current_room->paths[option]);

Notice here we get the paths from the current_room. This will mean the user only has access to the room they are currently in. When they move to a new room, they will only have access to the paths in that room.

The main logic

In main, make sure you have a few rooms to play with. Set the current room, and then let the user keep exploring while there are exists in the current room. When they do reach the end, you can print a farewell message and show the details of the final room.

I achieved this with the following code.

  while(current_room->paths.size > 0)
  {
    explore(current_room);
  }

  printf("You have reached the end of the maze!\n");
  print_room(current_room);

Compile and run the program, and you should be able to explore your maze. Make sure you have a room with no paths, that is reachable via paths from other rooms. Explore your maze and make sure it works as expected.

• New Maze Game Code

  The maze game is a great way to start exploring the world of graphs. In this iteration of the program, we added the ability for each room to have a number of paths that lead to other rooms. This enabled us to allow the user to explore the maze, until they found the room with no exists.

  #include <string>
  #include "dynamic-array-2.hpp"
  
  using std::string;
  
  typedef struct room_data *room_ptr;
  
  struct path_data
  {
    string    description;
    room_ptr  destination;
  } path_data;
  
  struct room_data
  {
    string title;
    string description;
    dynamic_array<path_data> paths;
  } room_data;
  
  /**
   * New path populates the data in a path struct and returns it.
   *
   * @param description the description of the path
   * @param destination the destination of the path - a pointer to the room it goes to
   * @return path_data with the indicated details
   */
  path_data new_path(string description, room_ptr destination)
  {
    path_data result = { description, destination };
  
    return result;
  }
  
  /**
   * New room populates the data in a room struct and returns it.
   *
   * @param title         The title of the room
   * @param description   The description of the room
   * @returns             The new room data
   */
  room_data new_room(string title, string description)
  {
    room_data result = { title, description, dynamic_array<path_data>(0, {})};
  
    return result;
  }
  
  /**
   * Outputs the path's description to the terminal. Showing the index of the path
   * and the description, but no details of where it goes.
   *
   * @param idx   the index of the path - used to select it from the list
   * @param path  the path to print (const reference)
   */
  void print_path(int idx, const path_data &path)
  {
    printf("%d - %s\n", idx, path.description.c_str());
  }
  
  /**
   * Output the room's title and description to the terminal.
   *
   * @param room a pointer to the room to print
   */
  void print_room(room_ptr room)
  {
    printf("%s\n-----\n%s\n", room->title.c_str(), room->description.c_str());
  
    if ( room->paths.size > 0 )
    {
      printf("There are paths leading:\n");
      for (int i = 0; i < room->paths.size; i++)
      {
        print_path(i, room->paths[i]);
      }
    }
  }
  
  /**
   * Move the player through the selected path, setting the player's current room
   * to the destination of the path.
   *
   * @param current_room a reference to the player's current room (a pointer to the room_data)
   * @param path a constant reference to the path to move through
   */
  void move_player(room_ptr &current_room, const path_data &path)
  {
    current_room = path.destination;
  }
  
  /**
   * Reads an integer value from the user. If the user enters a non-integer value,
   * the function will continue to prompt the user until they enter a valid value.
   *
   * @param prompt the prompt message to display to the user
   * @return int the integer value entered by the user
   */
  int read_integer(const string &prompt)
  {
    int result = 0;
  
    printf("%s", prompt.c_str());
    while (scanf(" %d", &result) != 1) // Read value, and try to convert to int
    {
      // Convert failed, as input was not a number
      scanf("%*[^\n]"); // Read past the end of the current line
      printf("Please enter a whole number.\n");
      printf("%s", prompt.c_str());
    }
  
    return result;
  }
  
  void explore(room_ptr &room)
  {
    int option = 0;
  
    print_room(room);
  
    option = read_integer("Which path do you want to take? ");
  
    while(option < 0 || option > room->paths.size - 1)
    {
      printf("Choose a value between 0 and %d\n", room->paths.size - 1);
      option = read_integer("Option: ");
    }
  
    move_player(room, room->paths[option]);
  }
  
  int main()
  {
    room_data r1 = new_room("Room 1", "You are in a happy place");
    room_data r2 = new_room("Room 2", "This is room 2");
    room_data r3 = new_room("Room 3", "This is room 3");
  
    r1.paths.add(new_path("A large sliding door", &r2));
    r1.paths.add(new_path("An open corridor", &r3));
    r1.paths.add(new_path("A small door", &r1));
  
    r2.paths.add(new_path("A large sliding door", &r1));
    r2.paths.add(new_path("A small door", &r1));
  
    room_ptr current_room = &r1;
  
    while(current_room->paths.size > 0)
    {
      explore(current_room);
    }
  
    printf("You have reached the end of the maze!\n");
    print_room(current_room);
  }

Graphs

Have you noticed how the structure of the maze is similar to a linked list?

You can think of the maze as a graph, and the player is able to traverse that graph exploring the data along the way. While we used a game style theme here, the skills you develop by thinking and working through this will help you in other contexts that use graphs. For example, exploring connections in a social media graph, finding files in a file system, and many other applications.