Generating Random Dungeons (part 6)


Introduction

In part 5 of the Generating Random Dungeons article series we implemented functionality to allow us to specify a “randomness” factor which influenced how often our corridor directions changed. This allowed us to either create mazes with long winding corridors or with corridors that change at every turn or a combination of both. 

This is all fine and well, but our maze is not really a dungeon as generated by the algorithm we are implementing. A dungeon typically has some winding corridors, corridors intersecting with each other, corridors looping around on themselves, and of course some rooms (we’ll get to this I promise). The implication is that our map should have some areas filled with rock i.e. not completely filled with corridors.

The author of the algorithm calls this the “sparseness” factor of the dungeon. Let’s see how we’ll add this feature.

Algorithm Step 7

Look at every cell in the maze grid. If the given cell contains a corridor that exits the cell in only one direction (in other words, if the cell is the end of a dead-end hallway), “erase” that cell by removing the corridor.

The first part of this step requires that we evaluate each cell in the maze (or map) and then check if that cell is a dead end. We can determine if a cell is a dead-end by evaluating how many of its sides are walls. Cells with 3 wall sides will therefore be dead-end cells.

Let’s write a test to check if a cell is a dead-end.

        [Test]

        public void TestIfCellIsDeadEnd()

        {

            Cell cell = new Cell();

            cell.NorthSide = SideType.Empty;

            Assert.IsTrue(cell.IsDeadEnd);

 

            cell = new Cell();

            cell.WestSide = SideType.Empty;

            Assert.IsTrue(cell.IsDeadEnd);

 

            cell = new Cell();

            cell.SouthSide = SideType.Empty;

            Assert.IsTrue(cell.IsDeadEnd);

 

            cell = new Cell();

            cell.EastSide = SideType.Empty;

            Assert.IsTrue(cell.IsDeadEnd);

        }

 

        [Test]

        public void TestIfCellIsNotDeadEnd()

        {

            Cell cell = new Cell();

            Assert.IsFalse(cell.IsDeadEnd);

 

            cell = new Cell();

            cell.NorthSide = SideType.Empty;

            cell.EastSide = SideType.Empty;

            Assert.IsFalse(cell.IsDeadEnd);

 

            cell.WestSide = SideType.Empty;

            Assert.IsFalse(cell.IsDeadEnd);

 

            cell.SouthSide = SideType.Empty;

            Assert.IsFalse(cell.IsDeadEnd);

        }

In the above tests we added a property to the Cell class which returns a Boolean value indicating if the cell is a dead-end or not. Our first test checks that the property will return “True” when only one of either side is not a wall (or empty). The second test ensures that for a cell with 4, 2, 1 and no walls the property will return a “False” value.

The code to make these tests compile is as follows.

        public bool IsDeadEnd

        {

            get

            {

                int wallCount = 0;

                if (northSide == SideType.Wall) wallCount++;

                if (southSide == SideType.Wall) wallCount++;

                if (westSide == SideType.Wall) wallCount++;

                if (eastSide == SideType.Wall) wallCount++;

                return wallCount == 3;

            }

        }

The above code checks each side of the cell and increments a wallCount variable for each side that is a wall. It then checks if there were 3 walls in the cell and returns a “True” result (otherwise it returns “False”).

I compile the code and run the tests and they all pass.

We can now determine if a cell is a dead-end or not. The next step is to evaluate each cell in the map and check if it’s a dead-end or not. It’s the dead-end cells that we are interested in. I think it would be cool if we could have a function that would return all the dead-end cells in the map for us.

The test to return all the dead-end cells in a map is as follows.

        [Test]

        public void TestCanRetrieveAllDeadEndCellsInMap()

        {

            Generator generator = new Generator();

            Map map = generator.Generate(10, 10, 100);

 

            // Loop through each cell and increment counter for each dead end

            int deadEndCellCount1 = 0;

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

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

                    if (map[x, y].IsDeadEnd) deadEndCellCount1++;

 

            // Loop through each dead end cell location in map

            int deadEndCellCount2 = 0;

            foreach (Point location in map.DeadEndCellLocations)

            {

                // Assert the location is a dead end

                Assert.IsTrue(map[location].IsDeadEnd); 

                deadEndCellCount2++;

            }

 

            // Assert that DeadEndCellLocations returns the same amount of

            // dead-end cell locations as manual process

            Assert.AreEqual(deadEndCellCount1, deadEndCellCount2);

        }

In the above test we first generate our dense maze. We then manually loop through each cell in the maze and check if it’s a dead-end. We keep a counter of how many dead-end cells we found.

We then try to enumerate all the dead-end cell locations in the map. First we test if the cell at the location is really a dead-end and then we increment our second counter. The last step is to compare the two counters to ensure that we had the same dead-end cell count for each process.

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

        public IEnumerable<Point> DeadEndCellLocations

        {

            get

            {

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

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

                        if (this[x, y].IsDeadEnd) yield return new Point(x, y);

            }

        }

In the above code I implemented a property on the map class that returns an IEnumerable of type Point. The code loops through each cell in the map and then yield returns the location if it is a dead-end.

I recompile the code, run the tests and they all run with no problems.

Our next task is to remove the dead-end corridor (Cell). A corridor is defined by two adjacent cells not having walls between them. To remove our dead-end cell we need to create a wall at its empty side. Then we need to add a wall on the opposite side of the adjacent cell.

The first thing we need is to determine the direction of the corridor leading out of the dead-end cell. The test to retrieve this direction is as follows.

        [Test]

        public void TestCanGetDeadEndCorridorDirection()

        {

            Cell cell = new Cell();

            cell.NorthSide = SideType.Empty;

            Assert.AreEqual(DirectionType.North, cell.CalculateDeadEndCorridorDirection());

 

            cell = new Cell();

            cell.SouthSide = SideType.Empty;

            Assert.AreEqual(DirectionType.South, cell.CalculateDeadEndCorridorDirection());

 

            cell = new Cell();

            cell.WestSide = SideType.Empty;

            Assert.AreEqual(DirectionType.West, cell.CalculateDeadEndCorridorDirection());

 

            cell = new Cell();

            cell.EastSide = SideType.Empty;

            Assert.AreEqual(DirectionType.East, cell.CalculateDeadEndCorridorDirection());

        }

 

        [Test]

        [ExpectedException(typeof(InvalidOperationException))]

        public void TestInvalidCallOfGetDeadEndCorridorDirection()

        {

            Cell cell = new Cell();

            cell.CalculateDeadEndCorridorDirection();

        }

In the above tests we check that the CalculateDeadEndCorridorDirection method returns the direction of the empty side of our dead-end cell.

The code to make the above tests compile is as follows.

        public DirectionType CalculateDeadEndCorridorDirection()

        {

            if (!IsDeadEnd) throw new InvalidOperationException();

 

            if (northSide == SideType.Empty) return DirectionType.North;

            if (southSide == SideType.Empty) return DirectionType.South;

            if (westSide == SideType.Empty) return DirectionType.West;

            if (eastSide == SideType.Empty) return DirectionType.East;

 

            throw new InvalidOperationException();

        }

The CalculateDeadEndCorridorDirection method checks each side to determine if it’s empty. The method returns the direction of the first empty side. The method will throw an exception if the cell is not a dead-end cell.

I compile the code and run the tests and they all pass.

Now that we have the direction of the dead-end corridor we need to create a wall in that direction. This task is very similar to the CreateCorridor task we used to actually create the maze. We can reuse the CreateCorridor algorithm by factoring out the SideType being created. Let’s start by refactoring the CreateCorridor method as follows.

        public Point CreateCorridor(Point location, DirectionType direction)

        {

            return CreateSide(location, direction, SideType.Empty);

        }

 

        private Point CreateSide(Point location, DirectionType direction, SideType sideType)

        {

            Point target = GetTargetLocation(location, direction);

 

            switch (direction)

            {

                case DirectionType.North:

                    this[location].NorthSide = sideType;

                    this[target].SouthSide = sideType;

                    break;

                case DirectionType.South:

                    this[location].SouthSide = sideType;

                    this[target].NorthSide = sideType;

                    break;

                case DirectionType.West:

                    this[location].WestSide = sideType;

                    this[target].EastSide = sideType;

                    break;

                case DirectionType.East:

                    this[location].EastSide = sideType;

                    this[target].WestSide = sideType;

                    break;

            }

 

            return target;

        }

In the above code I created a new method called CreateSide. This method is identical to the old CreateCorridor method, but takes as input an additional parameter sideType which is used to specify the SideType that will be created between two adjacent cells.

Next I updated the CreateCorridor method to call the CreateSide method by passing in a SideType of “Empty”. Now we have an easy way of reusing the CreateSide functionality to remove our dead-end cell. Before continuing I rerun the unit tests to make sure I didn’t break anything.

The test to create a wall between two adjacent cells is as follows.

        [Test]

        public void TestCreateWallBetweenAdjacentCells()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            // Loop through each cell and make all the sides empty

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

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

                {

                    map[x, y].NorthSide = SideType.Empty;

                    map[x, y].SouthSide = SideType.Empty;

                    map[x, y].WestSide = SideType.Empty;

                    map[x, y].EastSide = SideType.Empty;

                }

 

            // We now have map with no walls.

            // Test creating walls in each direction

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

 

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

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

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

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

 

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

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

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

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

        }

In the above test I loop through each cell and remove all the walls. The reason for this is that our cells are always initialised with four walls. Next I call the new CreateWall method with a given location and direction and then test each side to make sure the walls are created in the right directions. I have excluded the tests for the other directions in this code listing, but the full test is implemented in the source code.

We now have enough functionality to implement the requirements of step 7 of the algorithm. First I am going to refactor the Generator class and add a CreateDenseMaze method and change the Generate method to call the CreateDenseMaze method. (This encapsulates all the functionality we implemented before step 7 of the algorithm). I rerun the unit tests to make sure the changes didn’t break anything.

The test to implement the requirements of step 7 of the algorithm is as follows.

        [Test]

        public void TestSparsifyMazeRemovesDeadEnds()

        {

            Map map = Generator.Generate(10, 10, 100);

 

            // Enumerate all the current dead-end locations

            // Add them to a list

            List<Point> deadEndLocations = new List<Point>();

            foreach (Point point in map.DeadEndCellLocations)

                deadEndLocations.Add(point);

 

            Generator.SparsifyMaze(map);

 

            // Enumerate all the new dead-end locations

            // Assert that they aren’t in the original list

            foreach (Point point in map.DeadEndCellLocations)

                Assert.IsFalse(deadEndLocations.Contains(point));

        }

In the above test I generate a dense maze as per our original functionality. I then enumerate all the dead-end locations in the maze and add them to a list. Next I invoke the SparsifyMaze method to remove the current set of dead-ends. I then enumerate all the new dead-end locations and compare them with the original set to ensure that all the original dead-ends were removed.

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

        public static void SparsifyMaze(Map map)

        {

            foreach (Point point in map.DeadEndCellLocations)

                map.CreateWall(point, map[point].CalculateDeadEndCorridorDirection());

        }

The actual code to implement step 7 in our generator is quite simple. We enumerate all the dead-end locations and create a wall in the direction of the dead-end corridor.

Next I add the SparsifyMaze method to our Generate method to include it in the main algorithm. I rerun the unit tests to make sure they are all valid. The new Generate method is now as follows.

        public static Map Generate(int width, int height, int changeDirectionModifier)

        {

            Map map = new Map(width, height);

            map.MarkCellsUnvisited();

 

            CreateDenseMaze(map, changeDirectionModifier);

            SparsifyMaze(map);

 

            return map;

        }

Below is a screen shot of our maze after incorporating the SparsifyMaze method. I updated the drawing algorithm to draw “rock” cells as black blocks.

exampleoutput1

Conclusion

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

The requirement was to be able to identify all the dead-end corridor cells in the map and to “erase” them. In doing so we would be able to remove corridor cells from the map and create impassible “rock” cells.

These new requirements added functionality to the Cell class to allow us to determine if it is a dead-end or not. We also added a method to determine the direction of the corridor leading out of the dead-end cell.

Next we added a property to the Map class to allow us to enumerate all the dead-end cells in the map. We also refactored our CreateCorridor method into a more generic CreateSide method. We used this new CreateSide method to implement a CreateWall method to allow us to remove the dead-end cells from the map.

We did not actually get to implement the “sparseness” factor described in the introduction section of this article. This addition will be handled in part 7 of this article series.

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