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

4 thoughts on “Generating Random Dungeons (part 2)

  1. So I’m trying to follow, but seems defining preprocessors don’t work well in Unity so I’m going to have to approach your Asserts in another way. Can you explain what there doing?

  2. Im trying to follow along but seems defining preprocessors don’t work well in unity I cannot use Assert, can you explain what there doing so I can make another solution?

    Thanks

    • He is writing the function to test the functionality of his class structures. It is not required, but if you want you can use an IF statement, and throw a run time error that way.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s