Generating the map is pretty much central to everything else in a roguelike game so we might as well get it out of the way first. It’s also one of the most challenging parts. Before we can do that, we need to come up with the actual steps the program will follow to create the map – the algorithm. In this chapter, we’ll look at how algorithms help to tackle complex problems in code.

This post is part of a series on creating a roguelike game in C#. For the latest chapters and more information, please visit the Official Project Page on ComeauSoftware.com. The current code for this project is also available on Github.

You’re now the teacher

There are 26 dungeon levels.  Each level is depicted from above as a set of up to nine square or rectangular rooms drawn with ASCII graphics.  Each room must have a minimum interior space of 2 x 2 spaces and be connected to at least one other room by a hallway the player can travel through. In later levels, the hallways themselves might get complex and form mazes with blind alleys, etc.. One room in the dungeon must have a stairway that will grant access to the next level. There’s only one stairway per level.

Another way to think about programming is that you are teaching the computer to perform a task. Unfortunately, the computer has no actual intelligence and cannot really “learn”; it can just follow instructions exactly as you present them, whether that’s what you really wanted or not. It does have the ability to instantly adopt a new language as soon as it’s installed and to follow instructions in that language.

Some languages are designed for specific types of applications like business or math and science or graphics so it’s easier to communicate those concepts but you’re still working with a machine that needs everything spelled out because it can’t make connections on its own. It has no other experience to draw from. Understanding that is the first step in being able to write a program.

A good example of this is a WHILE loop – a programming structure that repeats a specific action while a condition is met.

x = 0
while(x < 10){
  Console.WriteLine("Hello")
}

The code above is intended to print “Hello” to the program’s console 10 times and then stop but it actually shows a common programming mistake. In fact, it will run continuously and possibly lock up the machine until the programmer intervenes and stops the program because the value x is never updated so x will always be less than 10. Now, a human student might be expected to call that out but the computer won’t because it does exactly what it is told and no more.

Teachers often use outlines or lesson plans when trying to present information to students; programmers use algorithms. Algorithms are not code, they are the specific steps that the code follows in order to instruct the computer to perform a task. Like lesson plans, they might be developed by the programmer or they might be well-known methods used by many programmers. Algorithms might be outlined beforehand to guide the coding process or they might simply be evident to someone reading the code afterward.

Creating the Map

A map creation algorithm is especially challenging because now you’re trying to teach the computer to “see” a system of rooms and passages and understand them well enough to draw and manage them. We can do it easily, by sight, but the computer needs it spelled out step by step because its only working with the numbers. We’ll get into the code in the following chapters but, for now, we’ll just look at the algorithmic steps.

The algorithm I use is probably not the same as the original Rogue game or other roguelikes out there. The original source code is available but I haven’t looked closely at it because I don’t like reading large amounts of other people’s code and working out the solution on my own is more fun.

First, remember that the original game was made for a 80 x 25 display and this game is doing the same. If you play it for any amount of time, you might notice that the dungeon rooms stick to a 3 x 3 arrangement within that space

This means that the program needs some way of defining the space as a series of 80 x 25 spaces, dividing that space into nine regions, plotting a room with exits into each region and then drawing hallways between them. Each room needs at least one exit and each exit needs a hallway coming off of it, even if the hallway goes into a dead end which they sometimes do. Notice that none of the rooms in the two examples on this page have exits on the sides facing the edge of the map. Any element on the map can be hidden.

After the map is drawn, the program needs a way to recognize what parts of the map are inside and outside of playable space so that it can place things like gold and the stairway and so that the player and monsters don’t wander outside of the rooms and corridors. After items are placed, the program needs to know where they are so it can respond appropriately when the player encounters them. When I programmed on one of these displays back in the day, there was a function to actually read the screen at a specific point to determine what was there but we’ll be doing it a little differently here.

The algorithm that we can start with is very high-level:

1. Define a set of spaces, 80 across by 25 down, as the map.
2. Make each space identifiable and able to hold two characters, one visible and the other the actual value of the space to allow for hidden items. These two characters can be identical.
3. Divide the map into a 3 x 3 set of equal regions that can be worked with separately.
4. For each region, decide at random if that region will contain a room. Calculate the probability to ensure that there will be at least six rooms per map.
5. Calculate the random external size for a room, allowing for 2 x 2 spaces within. Walls take up one space each so this will be 4 x 4 to the maximum size allowed by the region, minus one space to allow hallways to run between rooms.
6. For each room created, place an exit on at least one of the walls and start a hallway from the exit. Walls facing the edge of the map must not receive exits.
7. After the rooms have been created, grow each hallway until it finds another room exit or another hallway to connect to or hits the edge of the map.
8. Verify that all rooms have exits and that no rooms or sections of the map are isolated.
9. After rooms and hallways are complete. Randomly place one stairway, items, monsters and the player on the map.
10. Display the map on the form.

These steps will cover many functions and other programming elements. There will be other lower-level operations within these steps that will have their own algorithms. In the next chapter, I’ll start getting into some of the C# code.

Exploring Further

• Algorithms can also be expressed as flowcharts or in other formats and I’ll be doing some of this later with specific functions. If you have any experience with flowcharts, try making one based on the algorithm steps I laid out in the last section and try to think of some that I missed based on your own knowledge of the game so far.
• Try writing out the algorithm for another common activity, like making coffee. Don’t forget to look for any decision points and options that have to be included.
• The hallway generation procedure is really challenging because you have to write instructions on how to search for exits and hallways that can’t actually be seen – only detected by searching in a specific direction. What steps would you take to “dig” hallways between these rooms?

While Iteration Statement – Microsoft Learning