Generating Random Dungeons (part 4)

Introduction

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 for both step 4 and 5 of the algorithm.

Algorithm Step 4

Let’s call the cell in the chosen direction C. Create a corridor between the current cell and C, and then make C the current cell. Mark C visited.

Step 4 of the algorithm requires us to make use of the valid direction picked in step 3 to create a corridor between the current cell and C which is the cell in the new direction. At this point we have no concept of what a corridor is and how to represent it in code. We’ve been talking about “cells” for the past three articles, but haven’t had the need to create a “Cell” class.

To represent corridors we would need some kind of wall construct. If we look at the example dungeons generated by the algorithm at http://www.aarg.net/~minam/dungeon.cgi we notice that the map is made up of squares. Each square (or cell) has four sides and each side can either have a wall, a doorway or some other interesting feature.

For our purposes we need the sides to have either have a wall or nothing. A corridor would then be represented by having two adjacent cells with no walls between them, but with walls on either side (I hope that makes sense).

Lets refactor our code to make use of the following Cell class.

    public class Cell

    {

        private bool visited;

 

        public bool Visited

        {

            get { return visited; }

            set { visited = value; }

        }

    }

Our Map class now needs to store a 2-dimensional array of Cell objects instead of booleans. At this point we haven’t gained any new functionality by using the Cell class, our visited state is now stored within the Cell and we need to change all the methods which assumed the visited state was stored directly in the array.

After making these changes I rerun the unit tests and they all pass. I expected this as we didn’t change any fundamental part of the implementation, just our method of accessing information.

The next step is to write a test that will test the requirement of creating a corridor between two cells. The test for this is as follows.

        [Test]

        public void TestCreateCorridorBetweenAdjacentCells()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

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

 

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

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

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

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

 

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

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

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

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

        }

In the above test I added a new CreateCorridor method that would take a location and direction as input parameters. I am assuming that each cell in the map will be defaulted to having a wall on every side. This simplifies things a bit since I would only need to remove walls to create a corridor in a certain direction. The assertions of the test check that the there are no walls between the starting cell and the adjacent cell in the provided direction. We should also test the other directions, but for brevity sake I am leaving them out of article (the full test will be included in the source code).

This test also introduced the concept of a SiteType enum which is used to indicate whether a certain side is either a Wall or Empty. I compile the test and it fails, time to implement the new functionality to make the test pass.

The changes to the Cell class are quite simple, I just added four new properties of type SideType and named them NorthSide, SouthSide, EastSide and WestSide respectively. The code for the CreateCorridor method is a bit more interesting.

        public void CreateCorridor(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:

                    this[location].NorthSide = SideType.Empty;

                    this[location.X, location.Y – 1].SouthSide = SideType.Empty;

                    break;

                case DirectionType.South:

                    this[location].SouthSide = SideType.Empty;

                    this[location.X, location.Y + 1].NorthSide = SideType.Empty;

                    break;

                case DirectionType.West:

                    this[location].WestSide = SideType.Empty;

                    this[location.X – 1, location.Y].EastSide = SideType.Empty;

                    break;

                case DirectionType.East:

                    this[location].EastSide = SideType.Empty;

                    this[location.X + 1, location.Y].WestSide = SideType.Empty;

                    break;

            }

        }

The CreateCorridor method was quite simple to implement. First it validates that there is a valid cell in the provided direction. Then based on the direction specified sets the appropriate side of the current location as empty and the opposite side of the target location as empty. I recompile the code and run the tests with no problems.

The next part of the algorithm requires us to make the target location the current location and to flag it as visited. That means our CreateCorridor method will need to return the target location and should be refactored.

        public Point CreateCorridor(Point location, DirectionType direction)

        {

            Point target = GetTargetLocation(location, direction);

 

            switch(direction)

            {

                case DirectionType.North:

                    this[location].NorthSide = SideType.Empty;

                    this[target].SouthSide = SideType.Empty;

                    break;

                case DirectionType.South:

                    this[location].SouthSide = SideType.Empty;

                    this[target].NorthSide = SideType.Empty;

                    break;

                case DirectionType.West:

                    this[location].WestSide = SideType.Empty;

                    this[target].EastSide = SideType.Empty;

                    break;

                case DirectionType.East:

                    this[location].EastSide = SideType.Empty;

                    this[target].WestSide = SideType.Empty;

                    break;

            }

 

            return target;

        }

 

        private Point GetTargetLocation(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 new Point(location.X, location.Y – 1);

                case DirectionType.West:

                    return new Point(location.X – 1, location.Y);

                case DirectionType.South:

                    return new Point(location.X, location.Y + 1);

                case DirectionType.East:

                    return new Point(location.X + 1, location.Y);

                default:

                    throw new InvalidOperationException();

            }

        }

I created a new method GetTargetLocation which encapsulates the functionality of checking the location and if there is a adjacent cell. It then returns the target location based on the direction provided. The CreateCorridor method is now a bit cleaner and returns our target location to be used by our Generate method.

Using the new functionality we are able to implement the required functionality as per step 4 of the algorithm.

        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

                }

            }

 

            currentLocation = map.CreateCorridor(currentLocation, direction);

            map.FlagCellAsVisited(currentLocation);

 

            return map;

        }

I recompile the code and run our unit tests. They all pass except the Generator test. The reason for this is that we were testing if one cell of the map had been marked as visited which is no longer the case. I change the test to check if two cells are visited and it passes.

Algorithm Step 5

Repeat steps 3 and 4 until all cells in the grid have been visited.

Step 5 of the algorithm basically requires that we repeat steps 3 and 4 until all the cells in the map have been flagged as visited. In order to determine if all cells have been visited we can expose a property on the Map class which compares the count of visited cells to the total cells in the map.

        public bool AllCellsVisited

        {

            get { return visitedCells.Count == (Width * Height); }

        }

The above code multiplies the width and height of the map to get to total number of cells and compares that to the count of visited cells in the map. The next step is to change the Generate method to implement the requirements of step 5.

        public Map Generate()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            Point currentLocation = map.PickRandomCellAndMarkItVisited();

 

            while(!map.AllCellsVisited)

            {

                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

                    }

                }

 

                currentLocation = map.CreateCorridor(currentLocation, direction);

                map.FlagCellAsVisited(currentLocation);

            }

 

            return map;

        }

The implementation is quite simple, we just wrap the code for steps 3 and 4 into a while loop which loops until all the cells have been visited. I recompile the code and run the unit tests. Once again the Generate test fails, we were testing if 2 cells had been visited and should now test that all cells have been visited. I update the test, recompile and it passes.

We have now successfully implemented the first section of the algorithm which creates a maze. I attach a screen shot of some sample output rendered using GDI+. I won’t be discussing the rendering code as it falls outside the scope of the dungeon generation algorithm.

Example Output

Conclusion

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 we added was a 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.

Advertisements

Lessons learnt…

The past three articles have been quite a learning experience.

I posted the articles on http://angband.oook.cz/rgrd.php for review, and the responses I received were not exactly what I expected (to say the least).

I don’t know what I was hoping for, maybe comments on the structure, thought processes, algorithm, implementation, etc.

Mostly it was a case of people commenting on the quality of the unit tests I was writing in order to test the new functionality. The sad thing is that they were exactly right. Those first tests were total junk, the current ones are maybe only slightly better. And that’s my conundrum, I have no idea how to write better tests. I find it difficult to write a test when I have to write the test before I write the code.

Is this an artifact of TDD that I didn’t anticipate, am I not taking enough time to think about the tests before writing them, or am I just a dumb ass (probably).

Take for example the following test. In this test I’m trying to test the requirement of picking a random cell and flagging it as visited.

        [Test]

        public void TestPickRandomCellAndMarkItVisited()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            int xLocation = Random.Instance.Next(map.Width – 1);

            int yLocation = Random.Instance.Next(map.Height – 1);

 

            map[xLocation, yLocation] = true;

 

            Assert.IsTrue(map[xLocation, yLocation]);

        }

The comments on this test was that I’m just testing the .NET framework’s ability to set a value to “True”. I agree this isn’t really testing functionality of the application. However, when I wrote the test i.e. before any code existed I was trying to write a test (taking into account TDD) that would satisfy the requirement of picking a random cell and flagging it as visited.

In hindsight this test should probably have been written to call a method such as map.PickRandomCellAndFlagItVisited() then the test should have enumerated all the cells in the map to test if one had been flagged as visited.

The next test is even more pointless.

        [Test]

        public void TestGeneratorInstantiation()

        {

            Generator generator = new Generator();

            Map map = generator.Generate();

 

            Assert.IsNotNull(map);

        }

Why did I write it? To force myself to implement a Generator class and to add a Generate method. Am I not getting TDD? One suggestion was to enumerate all the cells in the map and again test if one had been flagged as visited as per the first test. Sounds good, basically I’m testing that the Generate method satisfies the current requirements of the algorithm. This is probably good enough for now and more meaningful than its current state.

I just wonder what happens as I continue to implement the algorithm. The test will fail at some point. Does that invalidate the test or is it just time to refactor it. We can refactor the test to pass in this case, but then that initial test is lost. Maybe that’s OK and exactly in the spirit of TDD.

Time to update the articles.

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.

Generating Random Dungeons (part 2)

Introduction

In part 1 of this series I mentioned the source of the algorithm I’m using for the random dungeon generator, the development tools I’ll be using, the development methodology and then began to describe the first step of the algorithm.

In this second part I plan to describe the next few steps in the dungeon generation algorithm and hope to show how the new requirements further refine the code design.

Algorithm Step 2

Pick a random cell in the grid and mark it visited. This is the current cell.

The next step in the algorithm requires the ability to pick a random cell. We’re going to need to make use of some kind of random number generator functionality. Once the cell has been identified we’ll need to mark it as visited. Then we need to record that cell as the current cell.

Marking a cell as visited is no problem. We just set a cell in the Map (our array) to “True”. Random numbers will require some new functionality and storing the randomly selected cell as the current cell might require a new variable somewhere.

We can use the .NET random number generator, but for fun I’m going to use a .NET implementation of the Mersenne Twister algorithm which can be found at http://www.centerspace.net/resources.php.

The test to pick a random cell and mark it as visited is as follows.

        [Test]

        public void TestPickRandomCellAndMarkItVisited()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            map.PickRandomCellAndMarkItVisited();

 

            int visitedCellCount = 0;

 

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

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

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

 

            Assert.IsTrue(visitedCellCount == 1);

        }

In the above test we instantiate our Map as before and then invoke the PickRandomCellAndMarkItVisited method. The test loops through all the cells and counts the amount of cells that have been flagged as visisted. The test passes if only one cell has been marked as visited. Of course this test does not compile as we need to implement the new method we’ve added. The code for the PickRandomCellAndMarkItVisited is as follows.

        public void PickRandomCellAndMarkItVisited()

        {

            int locationX = Random.Instance.Next(Width – 1);

            int locationY = Random.Instance.Next(Height – 1);

            this[locationX, locationY] = true;

        }

In the above code we proceed to pick a random x location within the range 0 to Map.Width – 1 and a random y location within the range 0 to Map.Height – 1. We then mark the cell at that location as visited by setting the boolean value to “True”.

The Random.Instance functionality is a singleton wrapper around the Mersenne Twister implementation. I won’t be dicussing its implementation as it is rather trivial and functions as a support class to the dungeon generation application.

I compile the code and it fails. I didn’t create a setter for my indexer, so I add the setter, recompile and run the test and it passes. The last part of step 2 of the algorithm requires that we keep track of the current cell.

At the moment we don’t have the concept of a “Cell”, we have the x-y coordinates of all the cells in the Map and each cell’s visited state. We also don’t have a class that contains the actual random dungeon generation algorithm. So lets write a test to instantiate the “Generator” and invoke the “Generate” method.

        [Test]

        public void TestGeneratorInstantiation()

        {

            Generator generator = new Generator();

            Map map = generator.Generate();

 

            int visitedCellCount = 0;

 

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

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

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

 

            Assert.IsTrue(visitedCellCount == 1);

        }

I compile the test and it fails as expected. The next step is to implement the Generator class which will have a Generate() method we will use to host our dungeon generation algorithm.

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

        public Map Generate()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            map.PickRandomCellAndMarkItVisited();

 

            return map;

        }

The next part of the algorithm requires that we keep track of the randomly picked cell and to make it the current cell. At the moment we don’t have a concept of a cell, but we do use x and y location variables.

Our PickRandomCellAndMarkItVisited method doesn’t expose the cell it picked. We have to decide which class will keep track of the current cell location. In my mind the Generate method should hold that information as its part of the generation algorithm and not really part of the Map itself. To add this functionality we will have to return two variables from the PickRandomCellAndMarkItVisited and store them within our Generate method. This change would be a bit clumsy and there must be a better way.

I don’t like the fact that we’re using two separate variables to keep track of cell locations. We can make use of the System.Drawing.Point struct to get rid of the two location variables. The new Point data structure can further simplify access to the map if we overload the Map indexer. This will also simplify our requirement to return the randomly selected cell location. After these code changes the PickRandomCellAndMarkItVisited and Generate methods are now as follows.

        public Point PickRandomCellAndMarkItVisited()

        {

            Point randomLocation = new Point(Random.Instance.Next(Width – 1), Random.Instance.Next(Height – 1));

            this[randomLocation] = true;

            return randomLocation;

        }

 

        public Map Generate()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            Point currentLocation = map.PickRandomCellAndMarkItVisited();

 

            return map;

        }

I rerun the unit tests just to make sure everything is OK and find that it is. By changing the code to use a Point struct I was able to refactor the PickRandomCellAndMarkItVisited method to be more meaningful and less cumbersome.

And that’s it, we’ve now implemented the requirements for step 2.

Conclusion

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.

Generating Random Dungeons (part 1)

Introduction

I have been toying around with the idea of coding a random dungeon generator for some time now. A Google search for “Dungeon Generation Algorithms” yields quite a few interesting articles on the topic. Reading about it is one thing and doing it yourself is a completely different story.

The goal of this series of articles is to describe the development process of a random dungeon generator. I also hope to touch on some agile development principles, patterns and practices.

The algorithm I will attempt to implement was developed by Jamis Buck and can be found at http://www.myth-weavers.com/generate_dungeon.php. The dungeons generated by this algorithm reminded me of my old D&D days drawing out maps using pen and paper. Please check out http://www.myth-weavers.com/generate_dungeon.php to generate some sample dungeons to get a feel for what I’m trying to achieve.

I will be limiting the scope of my first release to generating rooms, corridors and doors. I want to try and get something resembling a dungeon out quickly so that I can actually walk around in it and hopefully evolve it into a RogueLike in the future (a completely different set of articles).

I will be using Microsoft Visual Studio 2005 Professional, C#, and NUnit as my development environment, programming language and unit testing framework. I will follow the algorithm step by step describing my understanding, assumptions and design decisions. I will then dive into the actual coding and try to use a Test-driven development approach.

Algorithm Step 1

Start with a rectangular grid, x units wide and y units tall. Mark each cell in the grid unvisited.

The first step in the algorithm requires a “grid” data structure containing “cells” with an “unvisited” state. Agile development methodology states “Consider the simplest thing that could possibly work”.

Immediately I’m thinking a 2-dimensional array storing some kind of value indicating an “unvisited” state. Let’s assume that we can store the visited state using a Boolean. (I know this is really naive but that’s kind of the point). I like the idea of using a “Map” class to contain my 2-D array providing a starting point for the dungeon generator.

I start of by creating a unit test to create a map and mark each cell as unvisited. The code that satisfies this requirement would look something like this.

        [Test]

        public void TestMarkCellsUnvisited()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

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

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

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

        }

 

I compile the test and it fails as expected. We need to implement some new functionality.

First we need to implement the Map class by providing a constructor that takes as input a width and height property used to initialize an array of type boolean.

The “MarkCellsUnvisited()” method is quite straight forward to implement. All I need to do is loop through all the cells in the map (our array) and mark each location as unvisited by setting the boolean flag to “False”.

The actual test assertion yielded a requirement I did not anticipate before. I need some way of accessing the various cells in my map and I need to be able to retrieve the width and height. Using an indexer I easily hook up the required functionality to access the map cells. Get properties for Width and Height provide the last functionality required to make the test pass.

The source code for the new Map class is as follows.

    public class Map

    {

        private readonly bool[, ] cells;

 

        public Map(int width, int height)

        {

            cells = new bool[width, height];

        }

 

        public void MarkCellsUnvisited()

        {

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

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

                    cells[x, y] = false;

        }

 

        public bool this[int x, int y]

        {

            get { return cells[x, y]; }

        }

 

        public int Width

        {

            get { return cells.GetUpperBound(0) + 1; }

        }

 

        public int Height

        {

            get { return cells.GetUpperBound(1) + 1; }

        }

    }

Conclusion

The section above describes the process of evolving the design of the random dungeon generator using Test-driven development techniques. We were able to, through the unit tests; implement the simplest design that satisfies the requirements of the first step in the random dungeon generation algorithm.

In part 2 of this article series we will deal with the next few steps in the algorithm.