Generating Random Dungeons (part 3)


Introduction

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

During this process we added additional functionality to select a random “Cell” within the Map and to flag it as visited. We also stored the randomly selected location as our current location which will be used in the following steps of the algorithm.

The new requirements caused the code to become a bit bloated and by using a Point struct to store locations we were able to reduce the amount of code required to perform the same functionality.

In part 3 of this series of articles we will implement the code required to meet the requirements of step 3 of the algorithm.

Algorithm Step 3

From the current cell, pick a random direction (north, south, east, or west). If (1) there is no cell adjacent to the current cell in that direction, or (2) if the adjacent cell in that direction has been visited, then that direction is invalid, and you must pick a different random direction. If all directions are invalid, pick a different random visited cell in the grid and start this step over again.

Step 3 of the algorithm is loaded with functionality. First we need to select a random direction and then determine if its a valid direction. We do this in two steps, firstly by checking if there is a cell adjacent to our current location in the direction we picked and secondly if the adjacent cell has not been visited.

The test to check if there is a adjacent cell for a given location in a given direction is as follows. For good measure I add some tests to handle boundary conditions and a out-of-bounds case.

        [Test]

        public void TestMapHasAdjacentCellInDirection()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            Assert.IsTrue(map.HasAdjacentCellInDirection(new Point(1, 1), DirectionType.North));

            Assert.IsTrue(map.HasAdjacentCellInDirection(new Point(1, 1), DirectionType.West));

            Assert.IsTrue(map.HasAdjacentCellInDirection(new Point(map.Width – 2, map.Height – 2), DirectionType.South));

            Assert.IsTrue(map.HasAdjacentCellInDirection(new Point(map.Width – 2, map.Height – 2), DirectionType.East));

        }

 

        [Test]

        public void TestMapHasNoAdjacentCellsOnBoundaries()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            Assert.IsFalse(map.HasAdjacentCellInDirection(new Point(0, 0), DirectionType.North));

            Assert.IsFalse(map.HasAdjacentCellInDirection(new Point(0, 0), DirectionType.West));

            Assert.IsFalse(map.HasAdjacentCellInDirection(new Point(map.Width – 1, map.Height – 1), DirectionType.South));

            Assert.IsFalse(map.HasAdjacentCellInDirection(new Point(map.Width – 1, map.Height – 1), DirectionType.East));

        }

 

        [Test]

        public void TestMapHasNoAdjacentCellsOutOfBounds()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            Assert.IsFalse(map.HasAdjacentCellInDirection(new Point(-5, -5), DirectionType.North));

        }

 

To make the above tests compile we’re going to need to implement some new functionality.

To store the directions we need to implement a new Enum called DirectionType. I’m not going to list the definition for DirectionType to save some space.

For the functionality to test for an adjacent cell in a given direction we need to implement a new method on the Map class called HasAdjacentCellInDirection. So lets add the new HasAdjacentCellInDirection method.

        public bool HasAdjacentCellInDirection(Point location, DirectionType direction)

        {

            // Check that the location falls within the bounds of the map

            if ((location.X < 0) || (location.X >= Width) || (location.Y < 0) || (location.Y >= Height)) return false;

 

            // Check if there is an adjacent cell in the direction

            switch(direction)

            {

                case DirectionType.North:

                    return location.Y > 0;

                case DirectionType.South:

                    return location.Y < (Height – 1);

                case DirectionType.West:

                    return location.X > 0;

                case DirectionType.East:

                    return location.X < (Width – 1);

                default:

                    return false;

            }

        }

 

The HasAdjacentCellInDirection method checks if the provided location falls within the bounds of the map. Invalid locations will cause the method to return a “False” result. The method evaluates the direction and based on the direction type determines if there can be an adjacent cell in that direction. Locations on the boundaries of the map will return “False”.

The test to check if the adjacent cell has been visited is as follows.

        [Test]

        public void TestVisitedAdjacentCellInDirectionIsVisited()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            // Set cells around the location we’re going to use as visited

            map[1, 0] = true;

            map[0, 1] = true;

            map[1, 2] = true;

            map[2, 1] = true;

 

            Assert.IsTrue(map.AdjacentCellInDirectionIsVisited(new Point(1, 1), DirectionType.North));

            Assert.IsTrue(map.AdjacentCellInDirectionIsVisited(new Point(1, 1), DirectionType.South));

            Assert.IsTrue(map.AdjacentCellInDirectionIsVisited(new Point(1, 1), DirectionType.East));

            Assert.IsTrue(map.AdjacentCellInDirectionIsVisited(new Point(1, 1), DirectionType.West));

        }

 

        [Test]

        public void TestUnvisitedAdjacentCellInDirectionIsUnvisited()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            Assert.IsFalse(map.AdjacentCellInDirectionIsVisited(new Point(1, 1), DirectionType.North));

            Assert.IsFalse(map.AdjacentCellInDirectionIsVisited(new Point(1, 1), DirectionType.South));

            Assert.IsFalse(map.AdjacentCellInDirectionIsVisited(new Point(1, 1), DirectionType.East));

            Assert.IsFalse(map.AdjacentCellInDirectionIsVisited(new Point(1, 1), DirectionType.West));

        }

 

To make the above tests compile we need to implement the AdjacentCellInDirectionIsVisited method. This method returns the visited state of the adjacent cell in the provided direction. The code for this method is as follows.

        public bool AdjacentCellInDirectionIsVisited(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 this[location.X, location.Y – 1];

                case DirectionType.West:

                    return this[location.X – 1, location.Y];

                case DirectionType.South:

                    return this[location.X, location.Y + 1];

                case DirectionType.East:

                    return this[location.X + 1, location.Y];

                default:

                    throw new InvalidOperationException();

            }

        }

The above method first checks if there is a valid adjacent cell. It then returns the visited state of the cell adjacent to the provided location in the given direction.

Using the two new methods we can now determine if a direction we picked is valid for our current location.

The next step is to add some functionality to pick a random direction. Simple enough, but we also need to keep track of the directions we’ve picked until we’ve picked all four directions. Lets write a test that requires this functionality.

        [Test]

        public void TestGetNextDirectionValidDirection()

        {

            DirectionPicker directionPicker = new DirectionPicker();

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

 

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

            {

                Assert.IsTrue(directionPicker.HasNextDirection);

                DirectionType direction = directionPicker.GetNextDirection();

                Assert.IsTrue(!directionsPicked.Contains(direction));

                directionsPicked.Add(direction);

            }

 

            Assert.IsFalse(directionPicker.HasNextDirection);

        }

 

        [Test]

        [ExpectedException(typeof(InvalidOperationException))]

        public void TestGetNextDirectionThrowsException()

        {

            DirectionPicker directionPicker = new DirectionPicker();

 

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

                directionPicker.GetNextDirection();

        }

In the above test I decided that I would like to use some kind of DirectionPicker class. I wanted this class to be responsible for picking valid directions i.e. not picking the same direction twice. The GetNextDirection method is responsible for picking the next valid direction. The DirectionPicker class should also provide an indication if a next direction is available this will be done through the HasNextDirection property. The GetNextDirection method should throw an exception when no more valid directions are available. The code to make the above tests compile is as follows.

    public class DirectionPicker

    {

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

 

        public bool HasNextDirection

        {

            get { return directionsPicked.Count < 4; }

        }

 

        public DirectionType GetNextDirection()

        {

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

 

            DirectionType directionPicked;

 

            do

            {

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

            } while (directionsPicked.Contains(directionPicked));

 

            directionsPicked.Add(directionPicked);

 

            return directionPicked;

        }

    }

The DirectionPicker class implements the functionality required by our unit tests above. The class keeps an internal list of directions already picked. Each time the GetNextDirection method is invoked the method checks if there are more directions available to pick. An exception is raised if no more directions are available. The method then picks a random direction until it picks one that has not been picked before. This new direction is added to the list of directions picked and then returned.

We now have enough functionality to implement most of the requirements of step 3 of the algorithm. Lets add this functionality to our Generate method in the Generator class.

        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

                    throw new NotImplementedException(“Need to choose a new current location from previously visited locations.”);

            }

 

            // TODO: Use the valid direction picked for next step in algorithm

 

            return map;

        }

In the above code listing we use the DirectionPicker to pick a random direction. We then loop while we either don’t have an adjacent cell or the adjacent cell has already been visited. In the loop we pick a new direction until there are no more directions left to pick.

The next step is to implement the test that will require the functionality to pick a new random location from the previously visited cells. The implication is that we need to keep a list of cells that have been visited. At the moment we mark a cell as visited by using the setter indexer on the map. To add the functionality to keep track of the visited cells I propose to make use of a method that encapsulates this functionality when flagging cells as visited. I refactor the map class by adding a private list of visited Points and a new method called FlagCellAsVisited as follows.

        private readonly List<Point> visitedCells = new List<Point>();

 

        public void FlagCellAsVisited(Point location)

        {

            if (LocationIsOutsideBounds(location)) throw new ArgumentException(“Location is outside of Map bounds”, “location”);

            if (this[location]) throw new ArgumentException(“Location is already visited”, “location”);

 

            this[location] = true;

            visitedCells.Add(location);

        }

 

        private bool LocationIsOutsideBounds(Point location)

        {

            return ((location.X < 0) || (location.X >= Width) || (location.Y < 0) || (location.Y >= Height));

        }

I then update our unit tests and the Generate method to use the new FlagCellAsVisited method and recompile the code. The next step is to implement the functionality to pick a random cell from the previously visited locations. The test that requires this functionality would look as follows.

        [Test]

        public void TestGetRandomVisitedCell()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            map.FlagCellAsVisited(new Point(1, 0));

            map.FlagCellAsVisited(new Point(0, 1));

            map.FlagCellAsVisited(new Point(1, 2));

            map.FlagCellAsVisited(new Point(2, 1));

 

            Point currentCell = new Point(2, 1);

            Point visitelCell = map.GetRandomVisitedCell(currentCell);

 

            // Check that the visited cell is one of the first 3 cells visited and not the current cell

            Assert.IsTrue(((visitelCell == new Point(1, 0)) || (visitelCell == new Point(0, 1)) || (visitelCell == new Point(1, 2))));

            Assert.AreNotEqual(visitelCell, currentCell);

        }

The test above requires a new method GetRandomVisitedCell the purpose of this method is to return a random previously visited cell but not the cell passed in as a parameter. This meets the requirement of the algorithm to pick a different random visited cell. The implementation for GetRandomVisitedCell is as follows.

        public Point GetRandomVisitedCell(Point location)

        {

            if (visitedCells.Count == 0) throw new InvalidOperationException(“There are no visited cells to return.”);

 

            int index = Random.Instance.Next(visitedCells.Count – 1);

 

            // Loop while the current cell is the visited cell

            while (visitedCells[index] == location)

                index = Random.Instance.Next(visitedCells.Count – 1);

 

            return visitedCells[index];   

        }

The GetRandomVisistedCell method checks if there are any visited cells available. It throws an exception if none are found. The method then picks a random index within the bounds of the visited cells list. It picks a new index until the visited cell is different than the cell passed in a input parameter and returns this cell.

We now have the final functionality required to finish this step of the algorithm. The updated Generate method is as follows.

        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

                }

            }

 

            // TODO: Use the valid direction picked for next step in algorithm

 

            return map;

        }

The new functionality allowed us to meet the requirement when no directions are valid for the current location. We then set the current location to a different randomly selected previously visited location. We also instantiate a new direction picker and get the next direction.

Conclusion

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 of step 4 of the algorithm.

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