Generating Random Dungeons (part 8)


Introduction

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 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 this article we will look at removing dead-ends by adding some loops to our maze.

Algorithm Step 9

Look at every cell in the maze grid. If the given cell is a dead-end cell (meaning that a corridor enters but does not exit the cell), it is a candidate for “dead-end removal.” Roll d% (i.e., pick a number between 1 and 100, inclusive). If the result is less than or equal to the “dead-ends removed” parameter, this dead-end should be removed. Otherwise, proceed to the next candidate cell.

The first part of step 9 is already implemented. All we need to do is to loop through our DeadEndCellLocations property on the Map class. The second part of this step requires us to evaluate some “dead-ends removal” parameter to determine if we should remove a dead-end.

Lets write a test that requires this functionality.

        [Test]

        public void TestShouldRemoveNotDeadend()

        {

            Assert.IsFalse(Generator.ShouldRemoveDeadend(0));

        }

 

        [Test]

        public void TestShouldAlwaysRemoveDeadend()

        {

            Assert.IsTrue(Generator.ShouldRemoveDeadend(100));

        }

The above tests make sure that if our deadEndRemovalModifier is 0 that will never remove a dead-end and if the deadEndRemovalModifier is 100 that we will always remove a dead-end. The idea is that the ShouldRemoveDeadend method should choose a random number between 1 and 99 (inclusive) and test if this number is less than the deadEndRemovalModifier.

I can’t think of a good test for the in-between cases. (Let me know if you have a good way to test for this).

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

        public static bool ShouldRemoveDeadend(int deadEndRemovalModifier)

        {

            return Random.Instance.Next(1, 99) < deadEndRemovalModifier;

        }

The ShouldRemoveDeadend method takes the deadEndRemovalModifier and compares it to a randomly selected value between 1 and 99 (inclusive). The higher the deadEndRemovalModifier the greater the chance that the ShouldRemoveDeadend method will return true.

Step 9 of the algorithm was quite easy to implement. All we needed to add was the ShouldRemoveDeadend method to our Generator class so let’s continue with step 10.

Algorithm Step 10

Remove the dead-end by performing step 3 of the maze generation algorithm, except that a cell is not considered invalid if it has been visited. Stop when you intersect an existing corridor.

Step 3 of the algorithm had to do with the selection of a random direction to visit next. Basically our selection criteria has now changed to only having to select another random direction within the map. It is not explicitly stated, but we should probably also select any direction except the dead-end direction (i.e. the CalculateDeadEndCorridorDirection).

The last phrase in step 10 is a bit worrying. “Stop when you intersect an existing corridor” Stop what? I think the author meant for us to also perform Step 4 of the algorithm i.e. create a corridor in the direction we’ve selected.

Our first requirement is to select a random direction excluding the dead-end direction retrieved using the CalculateDeadEndCorridorDirection method on the Cell class. We’ve already written a test that satisfies this requirement. All we need to do is initialise our DirectionPicker class with the dead-end corridor direction and set the changeDirectionModifier value to 100 to force it to change direction.

        [Test]

        public void TestDirectionPickerChoosesDifferentDirection()

        {

            DirectionType previousDirection = DirectionType.West;

            DirectionPicker directionPicker = new DirectionPicker(previousDirection, 100);

            Assert.AreNotEqual(previousDirection, directionPicker.GetNextDirection());

            Assert.AreNotEqual(previousDirection, directionPicker.GetNextDirection());

            Assert.AreNotEqual(previousDirection, directionPicker.GetNextDirection());

            Assert.AreEqual(previousDirection, directionPicker.GetNextDirection());

        }

Using this functionality we should be able to implement the requirements of step 10. The test for this step is as follows.

        [Test]

        public void TestRemoveAllDeadEnds()

        {

            Map map = new Map(25, 25);

            map.MarkCellsUnvisited();

            Generator.CreateDenseMaze(map, 30);

            Generator.SparsifyMaze(map, 70);

 

            int deadEndCounter = 0;

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

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

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

 

            // Check that we have some dead ends.

            Assert.IsTrue(deadEndCounter > 0, “No dead-ends generated”);

 

            // Remove the dead-ends with a deadEndRemovalModifier of 100

            // We expect the map to have no dead ends when we’re done.

            Generator.RemoveDeadEnds(map, 100);

 

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

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

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

        }

The above test generates a sparse map. It then tests to ensure that some dead-ends were generated. (This might not always be guaranteed causing the test to fail). It then calls a new method on the Generator RemoveDeadEnds which takes as input the map object and the deadEndRemovalModifier. In the test we use a deadEndRemovalModifier value of 100 and expect the method to remove all the dead-ends. Finally we assert that all dead-ends were removed.

The code to make this test compile is as follows.

        public static void RemoveDeadEnds(Map map, int deadEndRemovalModifier)

        {

            foreach (Point deadEndLocation in map.DeadEndCellLocations)

            {

                if (ShouldRemoveDeadend(deadEndRemovalModifier))

                {

                    Point currentLocation = deadEndLocation;

 

                    do

                    {

                        // Initialize the direction picker not to select the dead-end corridor direction

                        DirectionPicker directionPicker = new DirectionPicker(map[currentLocation].CalculateDeadEndCorridorDirection(), 100);

                        DirectionType direction = directionPicker.GetNextDirection();

 

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

                        {

                            if (directionPicker.HasNextDirection)

                                direction = directionPicker.GetNextDirection();

                            else

                                throw new InvalidOperationException(“This should not happen”);

                        }

                        // Create a corridor in the selected direction

                        currentLocation = map.CreateCorridor(currentLocation, direction);

 

                    } while (map[currentLocation].IsDeadEnd); // Stop when you intersect an existing corridor.

                }

            }

        }

The RemoveDeadEnds method loops for each dead-end cell location in the provided Map. It then checks if the dead-end should be removed. It then picks a direction (excluding the direction it came from) and creates a corridor in that direction. The current location is then set to the location of the target corridor cell. It repeats this process until the current location is no longer a dead-end.

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, deadEndRemovalModifier = 100.

exampleoutput

Conclusion

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

The requirement was to evaluate all the dead-end cells in the map. For each dead-end cell, we evaluated a deadEndRemovalModifier to determine if we should remove that particular dead-end.

The process of removing a dead-end was to select a random direction within the map excluding the dead-end corridor direction (i.e. the direction from which we came). We then created a corridor in the selected direction and set our current location to the cell to which we created the corridor. We repeated this process until our current location was no longer a dead-end.

This functionality was implemented in a new RemoveDeadEnds method on the Generator class. As seen above, calling this method with a deadEndRemovalModifier of 100 results in a dungeon with no dead-ends.

In part 9 of this article series we will look at creating and placing rooms within our dungeon.

Advertisements

4 thoughts on “Generating Random Dungeons (part 8)

  1. Hey, I read the original description of the algorithm and can’t help but wonder how one would make it more efficient. I understand that every possible location for a room is rated before one gets chosen. Couldn’t we instead start with the rooms pre-placed, and then run the maze algorithm from there?

  2. Hi Jotaf

    You are right, this is another valid approach. Most roguelikes make use of this method. They place rooms within the map and then “tunnel” out passages to connect the rooms.

    I’m not sure abbout efficiency, this would have to be profiled. For now I’m just trying to get the algorithm implemented in an understandable way 🙂

  3. For the picking of a direction during removing dead end, besides making sure that the direction picked is not the direction of a corridor, I think the rate of changing direction should still be determined by the randomness factor of step 6.

    I’ve made the codes as:

    protected void RemoveDeadEnd(Location location, int randomness)
    {
    Cell cell;
    Direction direction;

    DirectionPicker picker = new DirectionPicker();
    Direction previousDirection = picker.GetNextDirection();

    do
    {
    picker = new DirectionPicker(randomness);
    cell = this.GetCell(location);
    if (!cell.IsDeadEnd)
    throw new InvalidOperationException(“Attempt to remove a non-dead end!”);

    do
    {
    direction = picker.GetNextDirection(previousDirection);
    } while (!this.HasAdjacentCell(location, direction) || direction == cell.DeadEndCorridorDirection);

    this.CreateCorridor(location, direction);
    location = this.VisitNextCell(location, direction);
    previousDirection = direction;

    } while (this.GetCell(location).IsDeadEnd);
    }

    so the previous direction picked is still taken into account, while the end condition checked had added cell.DeadEndCorridorDirection to make sure the corridor direction is not chosen.

    • Thanks for the suggestion.

      Sounds good to me.

      To be honest, I haven’t really looked at the tutorial code in ages.

      My dev code has quite a few enhancements and changes, maybe someday I’ll do an updated series taking into account all the changes.

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