Connecting Rooms on the Game Map

Completing the hallways on a roguelike map is one of the most challenging parts of the game and it goes back to what I said in an earlier chapter about teaching the computer to do what you take for granted. The program cannot see and interpret the map at a glance; you have to show it how to read the array, how to interpret what it sees and how to react to it. In this chapter, we’ll work out the algorithm for connecting the rooms. You’ll also see a couple examples of the Switch statement in C# and learn about the difference between value and reference types.

The code for the hallway generation is the most complex yet so you can always find it on Github but I do strongly suggest that you continue building your own version and examine every line.

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.

The Algorithm

I purposely did not spend much time looking up the algorithms other programmers have used to connect rooms in their roguelike games; I wanted to work it out for myself, even if it turned out less efficient. The result is not exactly like the original Rogue but I found that I actually like it better. I might add a second option for more traditional hallways later and review some of the other algorithms here.

Original

In the early levels of the original game, the hallways were pretty straightforward as you see in the first image above. There might be some dead ends but it was mostly a 1:1 connection of the different rooms.

After the first 10 levels or so, the hallways would start to get more complex, doubling back on themselves and creating mazes that you had to find your way through. I’ll admit I wasn’t looking forward to coding that. I think what I came up with strikes a nice balance throughout the game.

My algorithm did not come easy and the one you see here wasn’t the first. The trial and error that I went through for this was the reason I wrote the code for displaying the map earlier than I’d planned. I just had to see what on earth the algorithm was doing at each step of the way to give me the bizarre results I was getting at the end. Here’s the basic algorithm:

  1. Iterate backward through the dictionary of hallway “dead-ends” that we created while plotting the rooms.
  2. Check the array coordinate from the list, if there are doors or hallway spaces on more than one side of it, it’s connected so remove it from the list.
  3. Check in three directions – forward and to each side – for hallway characters in the distance. If there is one to be found, create a straight path to it to complete the current hallway.
  4. If there is no hallway in the distance, just add another hallway space in the next empty space available and update the deadEnds dictionary with the new coordinate.
  5. Continue iterating through the coordinates list until all items have been removed from the dictionary.

The Code

Search Functions

First, we need to teach the program to “see”. Let’s add some search functions to the MapLevel class.

Because of the length of some code snippets, I’m using Github Gist to present them. Remember that the current code for the entire application is also available on Github.

In a previous chapter, I showed you how class constructors could be overloaded so there were multiple options for the information a constructor could accept and return. This is another example of overloading where the first function overload looks for a specific character in all four adjacent spaces to the one specified and the second looks for any character. In both cases, the function returns a Dictionary with the Direction enumeration as the key and a MapSpace object as the value. Now the program can see what’s next to any specific space and make decisions based on it.

Here’s a sample of a call to this function that looks for HALLWAY characters on more than one side:

if (SearchAdjacent(HALLWAY, hallwaySpace.X, hallwaySpace.Y).Count > 1)
    deadEnds.Remove(hallwaySpace);

Values vs. References

This is a good point to bring up an very important concept in C# and other languages. It’s something that can seriously affect the decisions you made when coding and something you might be asked about in interviews.

There are two ways that you can pass information to a function like the ones you see above – by value and by reference. When you pass in an argument by value (often stated as ByVal), you’re passing a copy of the original value and any changes you make to that copy don’t have any effect on the original variable.

When you pass by reference (ByRef), you’re only passing a reference to the object which means that any changes you make will affect the original object. Different languages have different default ways of handling this when you don’t specify it yourself. In C#, there’s a little more that goes into the decision.

C# has both value and reference types meaning that the information in these types is stored and passed differently by default. When you declare a variable as a Value type (i.e. integer, double, boolean, char and others), C# stores the actual value of the variable in a specific memory location and the variable points to that location and the information in it. That’s one reason numeric values can be assigned a specific memory size such as 16-bit or 32-bit; the memory is actually allocated to that value based on the type’s maximum possible value and how much space is needed to hold it. If you copy that variable to another variable, you are making a copy of that data and now have two variables that can be changed separately from each other. Value types are also passed by value unless specified otherwise.

int x = 10;
int y = x;

y = 20;

Console.WriteLine(x);
Console.WriteLine(y);

Output:
10
20

A variable for a Reference type such as the MapSpace object, on the other hand, only holds a reference to a memory address where all the information for the object is stored. If you try to copy one object variable to another, you’re only copying that memory address and you’re still editing the original information. Reference types are also passed by reference in C#.

MapSpace first = MapSpace(HALLWAY, 10, 20)
MapSpace second = first

second.X = 25

Console.WriteLine(first.X)
Console.WriteLine(second.X)

Output:
25
25

Other than a dozen or so types such as integers, bytes, etc., most everything in C# is a reference type, including strings which is a surprise to many programmers who come from other languages.

Why am I telling you this now? Let’s take another look at the call to the SearchAdjacent() function.

if (SearchAdjacent(HALLWAY, hallwaySpace.X, hallwaySpace.Y).Count > 1)
    deadEnds.Remove(hallwaySpace);

The function accepts X and Y integer values that are both coming from the same MapSpace object but, as value types, they are passed ByVal. Why don’t I just pass the hallwaySpace object itself and let the function extract the information it needs? There are a couple of reasons.

  1. That would be extra work on the part of the function and functions should be kept as small and maintainable as possible.
  2. The function would now require a MapSpace object so if, for some reason, I wanted it to evaluate a point that wasn’t in a MapSpace object, I’d have to make one.
  3. The function would now have direct access to all the data within the original MapSpace object instead of a couple of values copied over.

Of course, the function only does what I tell it to do anyway but what about on a project where there are other programmers involved who are looking at the code years down the road? Mistakes do happen. Also, if you’re passing information over a network or in an online application and pass an object that contains sensitive information, it can raise security issues. Best practice is to pass what is needed to a function and no more.

Another Search

Let’s add another couple of search functions. These won’t be the last but they’ll do for the mapping process:

I needed a way to search in a straight line on the array for the next character. The SearchDirection() function searches a specific direction until it finds a non-blank character. If it doesn’t find one, it just returns the last one it finds, even if it is blank; I can test for this later.

The first few lines verify that the X and Y values passed in don’t exceed the array boundaries and then we see the C# switch statement for the first time in the code. This is known as the CASE statement in some other languages and simply tests a series of statements against a condition. In this case, it’s testing the direction that was passed in and taking actions depending on the value.

The SearchAllDirections() function simply calls the SearchDirection() function for each of the four directions and then removes any results where the character is EMPTY.

If you made up a reference grid as I suggested in previous chapters, this would be a good time to look back at it and maybe plot some random rooms to simulate what the program has done. It will come in handy as we look at the hallway generation.

Drawing the Hallways

The final stretch of the code brings it all together but it’s a bit long so I’m just going to present it here as a Gist and offer some notes afterward.

HallwayGeneration() starts by iterating backwards through the deadEnds dictionary of hallway spaces. This has to be done backwards if you plan on removing items from a collection as we do here. Otherwise, C# will skip over items as the index numbering of the list items changes. By going backwards, you ensure you’re always working with the portion of the list where the numbering hasn’t changed and you work with every item.

SearchAdjacent() provides the list of spaces on all four sides of the current space being examined. Each hallway ending is the last MapSpace in a hallway that is currently being “dug” in a specific direction. The code also needs a way to look to each side of that direction as it extends the hallway so it can avoid running two hallways parallel to each other when it could just tap into an existing one. In one of my attempts, I had a lot of double-wide hallways going on.

The GetDirection90() and GetDirection270() functions accept a specific direction and then use the numeric values of the Direction enumeration to decide which directions are 90 degrees and 270 degrees from it. Now the code knows where it’s going in the array and can look to the right and left. This is why I chose those numeric values for the enumeration.

 // Return direction 90 degrees from original based on forward direction.
 Direction retValue = 
(Math.Abs((int)startingDirection) == 1) ? (Direction)2 : (Direction)1;

North = 1 and East = 2. The opposite directions are simply negative values of these. The Math.Abs function gets the absolute value of a number and casting an enumeration member to an integer gets its numeric value. The statement above says “If the starting direction is North (1) or South (-1), change it to East (2); otherwise, make it North.”. The Direction270() function does the same and multiples it by -1 to get the opposite direction.

The SearchAllDirections() function then supplies a list of characters it found in the distance. If there’s another HALLWAY character available, the code calls the DrawHallway() method which takes a start and end point and a Direction and just plots MapSpace objects in a straight line between them. The method could determine the direction on its own but there’s no reason to since every hallway already has one assigned to it. After it draws the hallway, it removes that hallway from the deadEnds collection – it’s finished.

The example above shows the hallways that could be drawn just through one iteration of the deadEnds collection, assuming the hallway endings were listed in the same order as the map’s regions. The westbound hallway coming off of region 3 will turn south with the next iteration to connect to that long hallway going across the map. The map will be finished.

Notice the Switch statement in HallwayGeneration() uses a different syntax than you saw before. This example tests multiple conditions until it finds one that’s true. This is useful when you have multiple possible conditions and only want to act on one.

switch (true)
{
   case true when (surroundingChars.ContainsKey(hallDirection) &&
      surroundingChars[hallDirection].MapCharacter == HALLWAY):

Assuming there isn’t another hallway to connect to, I decided to have the program just extend the hallway another space and come back to it on the next iteration of the deadEnds list. By that time, one of the other hallways might have come into view.

Best practice is to include a default option in the Switch statement whenever possible so the code knows what to do if none of the other options apply. This default takes over and calls SearchAdjacent() to look for an empty space ahead or to the sides. It tests the current direction first and then looks 90 degrees and then in the opposite direction. Once it finds an empty space, it creates the new HALLWAY MapSpace there, removes the current deadEnds item and replaces it with a new one showing the updated ending of the hallway.

Verifying the Map

Remember that the map uses two constants to determine the chance of a room being left off the map and the percentage of room walls with exits. It seemed like no matter how much I played with these, I couldn’t guarantee that I wouldn’t come up with a map with rooms that didn’t have exits or rooms lacking connections to the rest of the map. This would render the game unplayable.

Finally my solution was to verify the map and scrap it for a new one if there were any problems. We’ll take a look at that and a few more items in the next chapter.

Next –


Nexus: A Brief History of Information Networks from the Stone Age to AI
  • #1 New York Times Bestseller from the author of Sapiens: A Brief History of Humankind
  • Published September 2024
  • 528 pages
ComeauSoftware.com uses affiliate links through which we earn commissions for sales.

Sign up for our newsletter to receive updates about new projects, including the upcoming book "Self-Guided SQL"!

We respect your privacy and will never share your information with third-parties. See our privacy policy for more information.

×