Generating Random Dungeons (part 7)


Introduction

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.

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

Algorithm Step 8

Repeat step 7 sparseness times (i.e. if sparseness is 5, repeat step 7 five times).

Step 8 of the algorithm is very simple. All we need to do is to repeat the previous step for the amount of times as indicated by our “sparseness” factor. This sounds cool, but I would like to improve the requirement a bit by having the sparseness factor imply a result that is a function of the size of our map.

If we repeat step 7 a few times with our current map size (10×10) we might not have any empty cells left at all. To me “sparseness” should be a percentage of the available map cells. If my “sparseness” is 100(%) then I expect all the cells to be “rock”, if my “sparseness” is 0(%) then I expect the maze to remain “dense” i.e. no rock areas.

The test that satisfies this requirement is as follows.

        [Test]

        public void TestMinSparsenessFactor()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            Generator.CreateDenseMaze(map, 50);

            Generator.SparsifyMaze(map, 0);

 

            // Assert that no cells were turned into rock

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

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

                    Assert.IsTrue(map[x, y].WallCount < 4);

        }

 

        [Test]

        public void TestMaxSparsenessFactor()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            Generator.CreateDenseMaze(map, 50);

            Generator.SparsifyMaze(map, 100);

 

            // Assert that all cells were turned into rock

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

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

                    Assert.IsTrue(map[x, y].WallCount == 4);

        }

 

        [Test]

        public void TestMidSparsenessFactor()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            Generator.CreateDenseMaze(map, 50);

            Generator.SparsifyMaze(map, 50);

 

            int targetRockCellCount = (int)Math.Ceiling((decimal)50 / 100 * (map.Width * map.Height));

            int currentRockCellCount = 0;

 

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

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

                    if (map[x, y].WallCount == 4) currentRockCellCount++;

 

            // Assert that 50% of the cells were turned into rock

            Assert.AreEqual(targetRockCellCount, currentRockCellCount);

        }

In the above code listing we test three conditions of our sparseness factor. The first test checks that no cells are turned into rock when we specify a sparseness factor of 0%. The second test checks that all cells are turned into rock when we specify a sparseness factor of 100%. The third test calculates the number of cells we would need to turn into rock if we specified a sparseness factor of 50%. It then compares the actual count of rock cells with the target count to make sure that the right amount of cells were turned into rock.

To make the above tests compile we need to add a sparsenessModifier parameter to our SparsifyMaze method and a new WallCount property to the Cell class. The new code is as follows.

        public bool IsDeadEnd

        {

            get { return WallCount == 3; }

        }

 

        public int WallCount

        {

            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;

            }

        }

For the WallCount property on the Cell class I moved this code out of the IsDeadEnd property and changed it to use the new WallCount property.

        public static void SparsifyMaze(Map map, int sparsenessModifier)

        {

            // Calculate the number of cells to remove as a percentage of the total number of cells in the map

            int noOfDeadEndCellsToRemove = (int) Math.Ceiling((decimal)sparsenessModifier / 100 * (map.Width * map.Height));

 

            IEnumerator<Point> enumerator = map.DeadEndCellLocations.GetEnumerator();

 

            for (int i = 0; i < noOfDeadEndCellsToRemove; i++)

            {

                if (!enumerator.MoveNext()) // Check if there is another item in our enumerator

                {

                    enumerator = map.DeadEndCellLocations.GetEnumerator(); // Get a new enumerator

                    if (!enumerator.MoveNext()) break; // No new items exist so break out of loop

                }

 

                Point point = enumerator.Current;

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

            }

        }

The SparsifyMaze method changed quite a bit to enable us to specify the sparsenessModifier parameter. We first calculate the number of dead-end cells to remove by using the sparsenessModifier parameter as a percentage of the total number of cells in the map. We then loop for each dead-end cell to remove and process each location in our DeadEndCellLocations enumerator. We retrieve a new enumerator if all locations were processed in the current enumerator and break out the loop if no new locations exist.

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

Below is a screen shot showing an example of our algorithm using the parameters width = 25, height = 25, changeDirectionModifier = 30 and sparsenessModifier = 70.

exampleoutput

Conclusion

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

The requirement was to repeat the previous step 7 for a certain amount of times as specified by a sparseness parameter. We refined this requirement a bit by having the sparseness parameter as a percentage of the total number of cells in the map.

In order to implement this requirement we modified our SparsifyMaze method to calculate the number of dead-end cells to remove by using the new sparsenessModifier parameter. The method then looped for each cell to remove and removed the cell as per step 7 of the algorithm.

In part 8 of this article series we will look at removing dead-ends by adding some loops to our maze.

Advertisements

3 thoughts on “Generating Random Dungeons (part 7)

  1. I am going through your code, very nice btw, and converting it to Java. While running the TestSparsifyMazeRemovesDeadEnds() method, using 100 for sparseness, I was receiving an Exception. What is/was happening was the corridor was reduced to a single corridor with 2 cells, after the 2nd to last was turned into a wall, it still tried to convert the last “dead end” (which now had 4 walls) to a non-dead end. I resolved this issue by adding a check at the bottom of the loop. If it is the last dead end in the current iterator, then I make a check to make sure it is still a dead end. This resolves the issue.

    Point point = deadEnds.next();
    if (deadEnds.hasNext() == false) {
    if (map.getCell(point).isDeadEnd()) {
    map.createWall(point, map.getCell(point).calculateDeadEndCorridorDirection());
    }
    } else {
    map.createWall(point, map.getCell(point).calculateDeadEndCorridorDirection());
    }

    • Thanks Mike

      I’ll have to check my code.

      My current version of the dungeon generator has had a few improvements and rewrites. So it might not apply.

      If you’re interested in a later version then I suggest you download the source to my last man standing game.

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