Generating Random Dungeons (part 5)


Introduction

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 was a new 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.

Algorithm Step 6

Once that process finishes, you’ll have your maze! There are a few variations you can do to make the maze more interesting; for example, my dungeon generator has a parameter called “randomness”. This is a percentage value (0–100) that determines how often the direction of a corridor changes. If the value of randomness is 0, the corridors go straight until they run into a wall or another corridor—you wind up with a maze with lots of long, straight halls. If the randomness is 100, you get the algorithm given above—corridors that twist and turn unpredictably from cell to cell.

Step 6 of the algorithm allows us to customize how often the algorithm chooses a new direction when creating corridors. The author of the algorithm recommends some kind of “randomness” parameter which will influence how often we change directions.

If the parameter value is 0 then the algorithm should use the previous direction for the next cell. We should change the direction if the previous direction is no longer valid. If the parameter value is 100 then we should always change our direction.

In order to implement this requirement we will need a method to calculate if we need to change the direction. The test for this requirement is as follows.

        [Test]

        public void TestMustChangeDirectionAlways()

        {

            DirectionPicker directionPicker = new DirectionPicker();

            Assert.IsTrue(directionPicker.MustChangeDirection(100));

        }

 

        [Test]

        public void TestMustChangeDirectionNever()

        {

            DirectionPicker directionPicker = new DirectionPicker();

            Assert.IsFalse(directionPicker.MustChangeDirection(0));

        }

In the above tests we added a new method to the DirectionPicker class called MustChangeDirection. This new method will take our “randomness” parameter used to test if we should change the direction. The tests check that a “randomness” value of 100 will always require a direction change and a value of 0 will never require a direction change.

The code for the MustChangeDirection method is as follows.

        public bool MustChangeDirection(int changeDirectionModifier)

        {

            // changeDirectionModifier of 100 will always change direction

            // value of 0 will never change direction

            return changeDirectionModifier > Random.Instance.Next(0, 99);

        }

The code above compares the provided changeDirectionModifier to a random value between 0 and 99. A changeDirectionModifier value of 0 will never be greater than any of the random values and will always return “False”. The above returns more “True” values as the changeDirectionModifier increases in value until it reaches 100 where it will always return “True”.

If we look at our current Generate main loop we notice that we depend on the DirectionPicker to select the next direction using the GetNextDirection method. I am going to try and incorporate the MustChangeDirection functionality within the GetNextDirection method. This will allow us to keep our main loop the same, while encapsulating the MustChangeDirection functionality within our DirectionPicker class.

The DirectionPicker class needs to know what the previous direction used was. If MustChangeDirection returns “False” then the DirectionPicker should return the previous direction when GetNextDirection is called. The following test illustrates this behaviour.

        [Test]

        public void TestDirectionPickerChoosesPreviousDirection()

        {

            DirectionType previousDirection = DirectionType.West;

            DirectionPicker directionPicker = new DirectionPicker(previousDirection, 0);

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

        }

 

        [Test]

        public void TestDirectionPickerChoosesDifferentDirection()

        {

            DirectionType previousDirection = DirectionType.West;

            DirectionPicker directionPicker = new DirectionPicker(previousDirection, 100);

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

        }

In the above tests I seed the DirectionPicker instance with a previous direction parameter and a change direction modifier of either 0 or 100. When I specify a change direction modifier of 0 I expect that GetNextDirection will return the same direction as the previous direction. When I specify a change direction modifier of 100 I expect that GetNextDirection will return a different direction as the previous direction.

The code that makes the above tests compile is as follows.

    public class DirectionPicker

    {

        private readonly List<DirectionType> directionsPicked = new List<DirectionType>();

        private readonly DirectionType previousDirection;

        private readonly int changeDirectionModifier;

 

        public DirectionPicker(DirectionType previousDirection, int changeDirectionModifier)

        {

            this.previousDirection = previousDirection;

            this.changeDirectionModifier = changeDirectionModifier;

        }

 

        public bool HasNextDirection

        {

            get { return directionsPicked.Count < 4; }

        }

 

        public DirectionType GetNextDirection()

        {

            if (!HasNextDirection) throw new InvalidOperationException(“No directions available”);

 

            DirectionType directionPicked;

 

            do

            {

                directionPicked = MustChangeDirection ? (DirectionType) Random.Instance.Next(3) : previousDirection;

            } while (directionsPicked.Contains(directionPicked));

 

            directionsPicked.Add(directionPicked);

 

            return directionPicked;

        }

 

        private bool MustChangeDirection

        {

            get

            {

                // changeDirectionModifier of 100 will always change direction

                // value of 0 will never change direction

                return changeDirectionModifier > Random.Instance.Next(0, 99);

            }

        }

    }

I changed the DirectionPicker class to take the previous direction and the change direction modifier as parameters for its constructor. I then refactored the MustChangeDirection method into a private property that evaluates the changeDirectionModifier to determine if we need to change our direction. The GetNextDirection method now checks if it should change the direction otherwise it returns the previous direction.

I rerun the DirectionPicker tests and they all pass without a problem. The next step is to refactor the Generator class to make use of the new DirectionPicker constructor. I update the Generator tests to make use of the new constructor as follows.

        [Test]

        public void TestGeneratorWithNeverChangeDirection()

        {

            Generator generator = new Generator();

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

 

            int visitedCellCount = 0;

 

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

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

                    if (map[x, y].Visited) visitedCellCount++;

 

            Assert.IsTrue(visitedCellCount == (map.Height * map.Width));

        }

 

        [Test]

        public void TestGeneratorWithAlwaysChangeDirection()

        {

            Generator generator = new Generator();

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

 

            int visitedCellCount = 0;

 

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

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

                    if (map[x, y].Visited) visitedCellCount++;

 

            Assert.IsTrue(visitedCellCount == (map.Height * map.Width));

        }

The above Generator tests now pass the width, height and changeDirectionModifier as parameters to the Generate method. The new Generate method is as follows.

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

        {

            Map map = new Map(width, height);

            map.MarkCellsUnvisited();

            Point currentLocation = map.PickRandomCellAndMarkItVisited();

            DirectionType previousDirection = DirectionType.North;

 

            while(!map.AllCellsVisited)

            {

                DirectionPicker directionPicker = new DirectionPicker(previousDirection, changeDirectionModifier);

                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(previousDirection, changeDirectionModifier); // Reset the direction picker

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

                    }

                }

 

                currentLocation = map.CreateCorridor(currentLocation, direction);

                map.FlagCellAsVisited(currentLocation);

                previousDirection = direction;

            }

 

            return map;

        }

The above code makes use of the width and height properties to initialize the Map object. The changeDirectionModifier along with the new previousDirection variable is used to initialize the DirectionPicker object.

I recompile and rerun the tests. Ouch! we seem to have a endless loop somewhere.

The problem seems to be in the GetNextDirection method. When the changeDirectionModifier value is 0 the directionPicked is always the previous direction which causes the endless loop. The fix is quite simple. All we have to do is update our MustChangeDirection property to evaluate whether we have already picked a direction. If we have we should always change the direction. The new code is as follows.

        private bool MustChangeDirection

        {

            get

            {

                // changeDirectionModifier of 100 will always change direction

                // value of 0 will never change direction

                return ((directionsPicked.Count > 0) || (changeDirectionModifier > Random.Instance.Next(0, 99)));

            }

        }

We rerun the Generator tests and they all pass as expected. I rerun all the tests to make sure that nothing else is broken and to my surprise the TestDirectionPickerChoosesDifferentDirection test fails.

The test checks that if we specify a changeDirectionModifier of 100 that we should always get a new direction, but also that the new direction should be different than the previous direction. The current code does not take into account the last part of the requirement, it just selects a random direction and in this case it selected the previous direction causing the test to fail.

I refactor the DirectionPicker tests to test for all possible cases to ensure that we implement the correct behaviour. The new tests are as follows.

        [Test]

        public void TestDirectionPickerChoosesPreviousDirection()

        {

            DirectionType previousDirection = DirectionType.West;

            DirectionPicker directionPicker = new DirectionPicker(previousDirection, 0);

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

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

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

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

        }

 

        [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());

        }

The choose previous direction test now asserts that the first direction picked is always the same as the previous direction. It also ensures that all the directions thereafter a different than the previous direction. The choose different direction test now asserts that the first 3 directions picked a different than the previous direction. It then asserts that GetNextDirection will return the previous direction when no directions are left to pick.

The code to make these tests pass is as follows.

        public DirectionType GetNextDirection()

        {

            if (!HasNextDirection) throw new InvalidOperationException(“No directions available”);

 

            DirectionType directionPicked;

 

            do

            {

                directionPicked = MustChangeDirection ? PickDifferentDirection() : previousDirection;

            } while (directionsPicked.Contains(directionPicked));

 

            directionsPicked.Add(directionPicked);

 

            return directionPicked;

        }

 

        private DirectionType PickDifferentDirection()

        {

            DirectionType directionPicked;

            do

            {

                directionPicked = (DirectionType) Random.Instance.Next(3);

            } while ((directionPicked == previousDirection) && (directionsPicked.Count < 3));

 

            return directionPicked;

        }

In the code above I wrapped the selection of the random direction in the PickDifferentDirection method. This method is responsible for choosing a different random direction than the previous direction. It will return the previous direction (eventually) when 3 directions have already been picked.

I recompile and run all the units tests. They pass with no problems.

We have now successfully implemented step 6 of the dungeon generation algorithm. I attach a screen shot of some sample output with the changeDirectionModifier set to 0 (always change direction).

exampleoutput

Conclusion

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

During this process we added changeDirectionModifier and previousDirection parameters to the constructor of the DirectionPicker class. These new parameters allowed us to specify how often the direction picker should pick a new direction.

In part 6 of this article series we will look at converting our current “dense” maze into a “sparse” maze.

Advertisements

One thought on “Generating Random Dungeons (part 5)

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