#13 game dev stuff | mapping the dungeon

Greetings, fellow game developers! Today, I want to share with you an exciting development in my current project: the creation of a dungeon map. In order to implement things like puzzles, I needed to have some kind of memory helping the game understand the intricate connections between different rooms within the dungeon. In this blog post, I’ll want to discuss how I implemented said memory with help of a DFS algorithm.

Wait, what is a DFS algorithm?

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It is an excellent choice for traversing connected structures, such as a dungeon, as it ensures comprehensive coverage of all accessible areas.

Okay, I get it but what’s next?

Let’s assume that we have our dungeon structure given a set of rooms and corridors. First lets select a random starting point. From here we iterate over all the corridors and select all rooms that connect to our starting point via any corridor. We repeat this process with each new room until there are no more connections.

Sounds pretty easy. How about some code?

Sure. This will be our dungeon node which keeps track of the current room and all connected rooms and its parent room.

public DungeonNode(Room parent, Room current)
{
   this.parent = parent;
   this.current = current;
   this.children = new List<Rooms>();
}

And this will be the algorithm which creates the map structure.

public static DungeonNode GenerateMap(Room parent, Room start, List<Corridor> corridors)
{
   DungeonNode root = new DungeonNode(parent, start);
   foreach(Corridor c in corridors)
   {
      if (c.RoomA == start && root.Parent != c.RoomB)
      {
         root.Children.Add(GenerateMap(start, c.RoomB, corridors);
      }
      if (c.RoomB == start && root.Parent != c.RoomA)
      {
         root.Children.Add(GenerateMap(start, c.RoomA, corridors);
      }
   }
   return root;
}

And after running this script you are likely to get a map starting from your initial room which connects via the correct corridor to the other rooms of your dungeon.

Bottom Line

By employing this algorithm, I have gained a comprehensive understanding of the room connections within the dungeon. The power of this algorithm lies in its simplicity.

Thank you for joining me on this journey through dungeon mapping. Stay tuned for more updates on my game development progress, as I continue to delve into the depths of creativity and innovation. Happy mapping and happy developing!