Generating Random Dungeons (part 2)

Introduction

In part 1 of this series I mentioned the source of the algorithm I’m using for the random dungeon generator, the development tools I’ll be using, the development methodology and then began to describe the first step of the algorithm.

In this second part I plan to describe the next few steps in the dungeon generation algorithm and hope to show how the new requirements further refine the code design.

Algorithm Step 2

Pick a random cell in the grid and mark it visited. This is the current cell.

The next step in the algorithm requires the ability to pick a random cell. We’re going to need to make use of some kind of random number generator functionality. Once the cell has been identified we’ll need to mark it as visited. Then we need to record that cell as the current cell.

Marking a cell as visited is no problem. We just set a cell in the Map (our array) to “True”. Random numbers will require some new functionality and storing the randomly selected cell as the current cell might require a new variable somewhere.

We can use the .NET random number generator, but for fun I’m going to use a .NET implementation of the Mersenne Twister algorithm which can be found at http://www.centerspace.net/resources.php.

The test to pick a random cell and mark it as visited is as follows.

        [Test]

        public void TestPickRandomCellAndMarkItVisited()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            map.PickRandomCellAndMarkItVisited();

 

            int visitedCellCount = 0;

 

            for (int x = 0; x < map.Width; x++)

                for (int y = 0; y < map.Height; y++)

                    if (map[x, y]) visitedCellCount++;

 

            Assert.IsTrue(visitedCellCount == 1);

        }

In the above test we instantiate our Map as before and then invoke the PickRandomCellAndMarkItVisited method. The test loops through all the cells and counts the amount of cells that have been flagged as visisted. The test passes if only one cell has been marked as visited. Of course this test does not compile as we need to implement the new method we’ve added. The code for the PickRandomCellAndMarkItVisited is as follows.

        public void PickRandomCellAndMarkItVisited()

        {

            int locationX = Random.Instance.Next(Width – 1);

            int locationY = Random.Instance.Next(Height – 1);

            this[locationX, locationY] = true;

        }

In the above code we proceed to pick a random x location within the range 0 to Map.Width – 1 and a random y location within the range 0 to Map.Height – 1. We then mark the cell at that location as visited by setting the boolean value to “True”.

The Random.Instance functionality is a singleton wrapper around the Mersenne Twister implementation. I won’t be dicussing its implementation as it is rather trivial and functions as a support class to the dungeon generation application.

I compile the code and it fails. I didn’t create a setter for my indexer, so I add the setter, recompile and run the test and it passes. The last part of step 2 of the algorithm requires that we keep track of the current cell.

At the moment we don’t have the concept of a “Cell”, we have the x-y coordinates of all the cells in the Map and each cell’s visited state. We also don’t have a class that contains the actual random dungeon generation algorithm. So lets write a test to instantiate the “Generator” and invoke the “Generate” method.

        [Test]

        public void TestGeneratorInstantiation()

        {

            Generator generator = new Generator();

            Map map = generator.Generate();

 

            int visitedCellCount = 0;

 

            for (int x = 0; x < map.Width; x++)

                for (int y = 0; y < map.Height; y++)

                    if (map[x, y]) visitedCellCount++;

 

            Assert.IsTrue(visitedCellCount == 1);

        }

I compile the test and it fails as expected. The next step is to implement the Generator class which will have a Generate() method we will use to host our dungeon generation algorithm.

The code to make the above test pass is as follows.

        public Map Generate()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            map.PickRandomCellAndMarkItVisited();

 

            return map;

        }

The next part of the algorithm requires that we keep track of the randomly picked cell and to make it the current cell. At the moment we don’t have a concept of a cell, but we do use x and y location variables.

Our PickRandomCellAndMarkItVisited method doesn’t expose the cell it picked. We have to decide which class will keep track of the current cell location. In my mind the Generate method should hold that information as its part of the generation algorithm and not really part of the Map itself. To add this functionality we will have to return two variables from the PickRandomCellAndMarkItVisited and store them within our Generate method. This change would be a bit clumsy and there must be a better way.

I don’t like the fact that we’re using two separate variables to keep track of cell locations. We can make use of the System.Drawing.Point struct to get rid of the two location variables. The new Point data structure can further simplify access to the map if we overload the Map indexer. This will also simplify our requirement to return the randomly selected cell location. After these code changes the PickRandomCellAndMarkItVisited and Generate methods are now as follows.

        public Point PickRandomCellAndMarkItVisited()

        {

            Point randomLocation = new Point(Random.Instance.Next(Width – 1), Random.Instance.Next(Height – 1));

            this[randomLocation] = true;

            return randomLocation;

        }

 

        public Map Generate()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            Point currentLocation = map.PickRandomCellAndMarkItVisited();

 

            return map;

        }

I rerun the unit tests just to make sure everything is OK and find that it is. By changing the code to use a Point struct I was able to refactor the PickRandomCellAndMarkItVisited method to be more meaningful and less cumbersome.

And that’s it, we’ve now implemented the requirements for step 2.

Conclusion

In part 2 of the Generating Random Dungeons article we implemented the functionality to meet the requirements of step 2 of the random dungeon generation algorithm.

During this process we added additional functionality to select a random “Cell” within the Map and to flag it as visited. We also stored the randomly selected location as our current location which will be used in the following steps of the algorithm.

The new requirements caused the code to become a bit bloated and by using a Point struct to store locations we were able to reduce the amount of code required to perform the same functionality.

In part 3 of this series of articles we will implement the code required to meet the requirements of step 3 of the algorithm.

Advertisements

Generating Random Dungeons (part 1)

Introduction

I have been toying around with the idea of coding a random dungeon generator for some time now. A Google search for “Dungeon Generation Algorithms” yields quite a few interesting articles on the topic. Reading about it is one thing and doing it yourself is a completely different story.

The goal of this series of articles is to describe the development process of a random dungeon generator. I also hope to touch on some agile development principles, patterns and practices.

The algorithm I will attempt to implement was developed by Jamis Buck and can be found at http://www.myth-weavers.com/generate_dungeon.php. The dungeons generated by this algorithm reminded me of my old D&D days drawing out maps using pen and paper. Please check out http://www.myth-weavers.com/generate_dungeon.php to generate some sample dungeons to get a feel for what I’m trying to achieve.

I will be limiting the scope of my first release to generating rooms, corridors and doors. I want to try and get something resembling a dungeon out quickly so that I can actually walk around in it and hopefully evolve it into a RogueLike in the future (a completely different set of articles).

I will be using Microsoft Visual Studio 2005 Professional, C#, and NUnit as my development environment, programming language and unit testing framework. I will follow the algorithm step by step describing my understanding, assumptions and design decisions. I will then dive into the actual coding and try to use a Test-driven development approach.

Algorithm Step 1

Start with a rectangular grid, x units wide and y units tall. Mark each cell in the grid unvisited.

The first step in the algorithm requires a “grid” data structure containing “cells” with an “unvisited” state. Agile development methodology states “Consider the simplest thing that could possibly work”.

Immediately I’m thinking a 2-dimensional array storing some kind of value indicating an “unvisited” state. Let’s assume that we can store the visited state using a Boolean. (I know this is really naive but that’s kind of the point). I like the idea of using a “Map” class to contain my 2-D array providing a starting point for the dungeon generator.

I start of by creating a unit test to create a map and mark each cell as unvisited. The code that satisfies this requirement would look something like this.

        [Test]

        public void TestMarkCellsUnvisited()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            for(int x = 0; x < map.Width; x++)

                for(int y = 0; y < map.Height; y++)

                    Assert.IsFalse(map[x, y]);

        }

 

I compile the test and it fails as expected. We need to implement some new functionality.

First we need to implement the Map class by providing a constructor that takes as input a width and height property used to initialize an array of type boolean.

The “MarkCellsUnvisited()” method is quite straight forward to implement. All I need to do is loop through all the cells in the map (our array) and mark each location as unvisited by setting the boolean flag to “False”.

The actual test assertion yielded a requirement I did not anticipate before. I need some way of accessing the various cells in my map and I need to be able to retrieve the width and height. Using an indexer I easily hook up the required functionality to access the map cells. Get properties for Width and Height provide the last functionality required to make the test pass.

The source code for the new Map class is as follows.

    public class Map

    {

        private readonly bool[, ] cells;

 

        public Map(int width, int height)

        {

            cells = new bool[width, height];

        }

 

        public void MarkCellsUnvisited()

        {

            for (int x = 0; x < Width; x++)

                for (int y = 0; y < Height; y++)

                    cells[x, y] = false;

        }

 

        public bool this[int x, int y]

        {

            get { return cells[x, y]; }

        }

 

        public int Width

        {

            get { return cells.GetUpperBound(0) + 1; }

        }

 

        public int Height

        {

            get { return cells.GetUpperBound(1) + 1; }

        }

    }

Conclusion

The section above describes the process of evolving the design of the random dungeon generator using Test-driven development techniques. We were able to, through the unit tests; implement the simplest design that satisfies the requirements of the first step in the random dungeon generation algorithm.

In part 2 of this article series we will deal with the next few steps in the algorithm.