Generating Random Dungeons (part 4)


Introduction

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

During this process we added a method to the Map class to test if an adjacent cell existed in a given direction from a given location within the Map. In addition to this we also added a method to check if an adjacent cell in a given direction had been flagged as visited or not.

We then added a new class to our solution that provides us with the functionality to pick random directions until all four directions were picked. This class also has the ability to tell us if directions were still available to be picked.

There after we added another method to our Map class the pick a random previously visited cell within the Map. This cell had to be different from a cell (typically the current cell) sent in as a parameter. This new method required us to refactor the way we flag cells within our Map as visited causing us to implement a new method on the Map class to perform this functionality.

In part 4 of this series of articles we will implement the code required to meet the requirements for both step 4 and 5 of the algorithm.

Algorithm Step 4

Let’s call the cell in the chosen direction C. Create a corridor between the current cell and C, and then make C the current cell. Mark C visited.

Step 4 of the algorithm requires us to make use of the valid direction picked in step 3 to create a corridor between the current cell and C which is the cell in the new direction. At this point we have no concept of what a corridor is and how to represent it in code. We’ve been talking about “cells” for the past three articles, but haven’t had the need to create a “Cell” class.

To represent corridors we would need some kind of wall construct. If we look at the example dungeons generated by the algorithm at http://www.aarg.net/~minam/dungeon.cgi we notice that the map is made up of squares. Each square (or cell) has four sides and each side can either have a wall, a doorway or some other interesting feature.

For our purposes we need the sides to have either have a wall or nothing. A corridor would then be represented by having two adjacent cells with no walls between them, but with walls on either side (I hope that makes sense).

Lets refactor our code to make use of the following Cell class.

    public class Cell

    {

        private bool visited;

 

        public bool Visited

        {

            get { return visited; }

            set { visited = value; }

        }

    }

Our Map class now needs to store a 2-dimensional array of Cell objects instead of booleans. At this point we haven’t gained any new functionality by using the Cell class, our visited state is now stored within the Cell and we need to change all the methods which assumed the visited state was stored directly in the array.

After making these changes I rerun the unit tests and they all pass. I expected this as we didn’t change any fundamental part of the implementation, just our method of accessing information.

The next step is to write a test that will test the requirement of creating a corridor between two cells. The test for this is as follows.

        [Test]

        public void TestCreateCorridorBetweenAdjacentCells()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            map.CreateCorridor(new Point(0, 0), DirectionType.South);

 

            Assert.IsTrue(map[0, 0].NorthSide == SideType.Wall);

            Assert.IsTrue(map[0, 0].SouthSide == SideType.Empty);

            Assert.IsTrue(map[0, 0].WestSide == SideType.Wall);

            Assert.IsTrue(map[0, 0].EastSide == SideType.Wall);

 

            Assert.IsTrue(map[0, 1].NorthSide == SideType.Empty);

            Assert.IsTrue(map[0, 1].SouthSide == SideType.Wall);

            Assert.IsTrue(map[0, 1].WestSide == SideType.Wall);

            Assert.IsTrue(map[0, 1].EastSide == SideType.Wall);

        }

In the above test I added a new CreateCorridor method that would take a location and direction as input parameters. I am assuming that each cell in the map will be defaulted to having a wall on every side. This simplifies things a bit since I would only need to remove walls to create a corridor in a certain direction. The assertions of the test check that the there are no walls between the starting cell and the adjacent cell in the provided direction. We should also test the other directions, but for brevity sake I am leaving them out of article (the full test will be included in the source code).

This test also introduced the concept of a SiteType enum which is used to indicate whether a certain side is either a Wall or Empty. I compile the test and it fails, time to implement the new functionality to make the test pass.

The changes to the Cell class are quite simple, I just added four new properties of type SideType and named them NorthSide, SouthSide, EastSide and WestSide respectively. The code for the CreateCorridor method is a bit more interesting.

        public void CreateCorridor(Point location, DirectionType direction)

        {

            if (!HasAdjacentCellInDirection(location, direction)) throw new InvalidOperationException(“No adjacent cell exists for the location and direction provided.”);

 

            switch(direction)

            {

                case DirectionType.North:

                    this[location].NorthSide = SideType.Empty;

                    this[location.X, location.Y – 1].SouthSide = SideType.Empty;

                    break;

                case DirectionType.South:

                    this[location].SouthSide = SideType.Empty;

                    this[location.X, location.Y + 1].NorthSide = SideType.Empty;

                    break;

                case DirectionType.West:

                    this[location].WestSide = SideType.Empty;

                    this[location.X – 1, location.Y].EastSide = SideType.Empty;

                    break;

                case DirectionType.East:

                    this[location].EastSide = SideType.Empty;

                    this[location.X + 1, location.Y].WestSide = SideType.Empty;

                    break;

            }

        }

The CreateCorridor method was quite simple to implement. First it validates that there is a valid cell in the provided direction. Then based on the direction specified sets the appropriate side of the current location as empty and the opposite side of the target location as empty. I recompile the code and run the tests with no problems.

The next part of the algorithm requires us to make the target location the current location and to flag it as visited. That means our CreateCorridor method will need to return the target location and should be refactored.

        public Point CreateCorridor(Point location, DirectionType direction)

        {

            Point target = GetTargetLocation(location, direction);

 

            switch(direction)

            {

                case DirectionType.North:

                    this[location].NorthSide = SideType.Empty;

                    this[target].SouthSide = SideType.Empty;

                    break;

                case DirectionType.South:

                    this[location].SouthSide = SideType.Empty;

                    this[target].NorthSide = SideType.Empty;

                    break;

                case DirectionType.West:

                    this[location].WestSide = SideType.Empty;

                    this[target].EastSide = SideType.Empty;

                    break;

                case DirectionType.East:

                    this[location].EastSide = SideType.Empty;

                    this[target].WestSide = SideType.Empty;

                    break;

            }

 

            return target;

        }

 

        private Point GetTargetLocation(Point location, DirectionType direction)

        {

            if (!HasAdjacentCellInDirection(location, direction)) throw new InvalidOperationException(“No adjacent cell exists for the location and direction provided.”);

 

            switch (direction)

            {

                case DirectionType.North:

                    return new Point(location.X, location.Y – 1);

                case DirectionType.West:

                    return new Point(location.X – 1, location.Y);

                case DirectionType.South:

                    return new Point(location.X, location.Y + 1);

                case DirectionType.East:

                    return new Point(location.X + 1, location.Y);

                default:

                    throw new InvalidOperationException();

            }

        }

I created a new method GetTargetLocation which encapsulates the functionality of checking the location and if there is a adjacent cell. It then returns the target location based on the direction provided. The CreateCorridor method is now a bit cleaner and returns our target location to be used by our Generate method.

Using the new functionality we are able to implement the required functionality as per step 4 of the algorithm.

        public Map Generate()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            Point currentLocation = map.PickRandomCellAndMarkItVisited();

 

            DirectionPicker directionPicker = new DirectionPicker();

            DirectionType direction = directionPicker.GetNextDirection();

 

            while (!map.HasAdjacentCellInDirection(currentLocation, direction) || map.AdjacentCellInDirectionIsVisited(currentLocation, direction))

            {

                if (directionPicker.HasNextDirection)

                    direction = directionPicker.GetNextDirection();

                else

                {

                    currentLocation = map.GetRandomVisitedCell(currentLocation); // Get a new previously visited location

                    directionPicker = new DirectionPicker(); // Reset the direction picker

                    direction = directionPicker.GetNextDirection(); // Get a new direction

                }

            }

 

            currentLocation = map.CreateCorridor(currentLocation, direction);

            map.FlagCellAsVisited(currentLocation);

 

            return map;

        }

I recompile the code and run our unit tests. They all pass except the Generator test. The reason for this is that we were testing if one cell of the map had been marked as visited which is no longer the case. I change the test to check if two cells are visited and it passes.

Algorithm Step 5

Repeat steps 3 and 4 until all cells in the grid have been visited.

Step 5 of the algorithm basically requires that we repeat steps 3 and 4 until all the cells in the map have been flagged as visited. In order to determine if all cells have been visited we can expose a property on the Map class which compares the count of visited cells to the total cells in the map.

        public bool AllCellsVisited

        {

            get { return visitedCells.Count == (Width * Height); }

        }

The above code multiplies the width and height of the map to get to total number of cells and compares that to the count of visited cells in the map. The next step is to change the Generate method to implement the requirements of step 5.

        public Map Generate()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            Point currentLocation = map.PickRandomCellAndMarkItVisited();

 

            while(!map.AllCellsVisited)

            {

                DirectionPicker directionPicker = new DirectionPicker();

                DirectionType direction = directionPicker.GetNextDirection();

 

                while (!map.HasAdjacentCellInDirection(currentLocation, direction) || map.AdjacentCellInDirectionIsVisited(currentLocation, direction))

                {

                    if (directionPicker.HasNextDirection)

                        direction = directionPicker.GetNextDirection();

                    else

                    {

                        currentLocation = map.GetRandomVisitedCell(currentLocation); // Get a new previously visited location

                        directionPicker = new DirectionPicker(); // Reset the direction picker

                        direction = directionPicker.GetNextDirection(); // Get a new direction

                    }

                }

 

                currentLocation = map.CreateCorridor(currentLocation, direction);

                map.FlagCellAsVisited(currentLocation);

            }

 

            return map;

        }

The implementation is quite simple, we just wrap the code for steps 3 and 4 into a while loop which loops until all the cells have been visited. I recompile the code and run the unit tests. Once again the Generate test fails, we were testing if 2 cells had been visited and should now test that all cells have been visited. I update the test, recompile and it passes.

We have now successfully implemented the first section of the algorithm which creates a maze. I attach a screen shot of some sample output rendered using GDI+. I won’t be discussing the rendering code as it falls outside the scope of the dungeon generation algorithm.

Example Output

Conclusion

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

During this process we refactored the Map class to make use of a new Cell class. The cell class allowed us to implement functionality to keep track of the sides of each cell. Each side of a cell could either be a wall or empty.

The next piece of functionality we added was a method on the Map class to create a corridor between two adjacent cells. The implementation was quite easy as we just removed the walls between the two adjacent cells to form a corridor.

Next we updated our Generate function to incorporate this new functionality and also implemented the requirements for step 5 of the algorithm which basically created our maze as seen in the screen shot above.

In part 5 of this article series we will look at implementing some additional features to make the maze a little more interesting and start the process of transitioning the maze into more of a dungeon.

Advertisements

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