Line of Sight

I have been looking at Line of Sight algorithms in between all the Christmas preparations. There are currently two options that are looking interesting.

The first algorithm is FOV using recursive shadowcasting by Björn Bergström. The article is presented in an easy to read format and the demo application shows exactly the kind of behaviour I’m looking for.

I’ll probably first do a direct port of the code to c# and then look at rewriting it from scratch. I don’t know why, but that’s how I like to learn new things. I might do another article series if I get inspired.

The second algorithm is something I spotted on r.g.r.d. in the following thread by C Miller. This article is titled Modelling Rays for Line of Sight in an Object-Rich World. Again the algorithm is set out in a understandable manner and the source code provided (java) is simple to convert to c#.

In fact, I’ve already done an implementation using this algorithm. I’ve got my little @ running around on maps generated using the random dungeon generation code.

Out the box the algorithm works fine except for a few tiles that are being displayed even though they shouldn’t be visible. I don’t think that its a problem with the algorithm itself, but rather that I’m not interpreting the results correctly.

I’ll get back to this once I’ve implemented the shadowcasting algorithm. I might design the code so that I can easily swap out the two algorithms, but I’m not sure I’ll ever need too.

In the mean time. Merry Christmas.

Generating Random Dungeons (part 10)

Introduction

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

The requirement was to create random sized rooms and place them within the dungeon. To achieve this we added quite a lot of additional functionality. For instance, we added a new Room class which is very similar to the Map class in its structure and meaning.

In this article I will look at refactoring the Map and Room classes to reduce duplicate code. I hope to also handle placing doors in our rooms and, if there is time, to convert the Map structure from cells to tiles.

Refactoring

Below is a class diagram representation of our current Map and Room classes.

DomainModel1

We can see some commonality in the fields and properties of both the Map and Room classes. To me a Room is also a Map, albeit a special type of Map. I would not just want to inherit Room from Map in its current form as I’d be inheriting a bunch of unnecessary properties and methods used for Dungeon generation. And I guess that’s the key. We need another class that is based on a Map, but encapsulates the functionality for handling dungeon generation.

My first refactoring is therefore renaming the Map class to Dungeon and having the Dungeon class inherit from a new Map class that encapsulates the functionality for working with the Map data structure. The new class diagram is as follows.

DomainModel2 

Our new Map abstract class provides us with functionality to manage the Map data structure. Both Rooms and Dungeons are made up of cells in a rectangular shape and have bounds that need to be checked.

The Room class now only has functionality needed for room creation and placement while the Dungeon class only has functionality needed for creating a dungeon. I find the new structure a bit easier to work with, while the class name Dungeon adds a bit more meaning to what we’re actually trying to achieve.

I added a new CellLocations property which is similar to the old DeadEndCellLocations property on the Dungeon class.  Instead of returning only dead-end cell locations, this IEnumerable will return every location in our Map. The benefit is improved ease of use when having to enumerate each location within a map. Instead of having to write

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

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

we can now enumerate all the locations within our map using the following code.

            foreach (Point cellLocation in dungeon.CellLocations)

I implemented another change to the Map class so that the Map constructor properly initializes our 2-dimensional cell array. In the past the MarkCellsUnvisited and InitializeRoomCells methods performed this function, but I didn’t like the way you could instantiate the Dungeon and Room classes into an invalid state.

I renamed a few of the methods from “Mark” to “Flag” cell as visited. I felt it to be a bit more consistent with the language we’re using within our algorithm.

You will notice that I removed the room placement and scoring functionality from the Dungeon class. I felt that this was a function of Room creation and that the Dungeon class should not be making such decisions.

Just like we have a Dungeon Generator we should also have a Room Generator. The results of these classes should be Dungeons and Rooms respectively. In lieu of this I refactored the Generator class into a more explicit DungeonGenerator class and moved the room creation functionality into a new RoomGenerator class as seen below.

DomainModel3

Our DugeonGenerator is now initialized with the various parameters (these can also be changed via the properties). We offload the room generation functionality through the new RoomGenerator class which is passed to the DungeonGenerator as a parameter.

Our new RoomGenerator class is now responsible for creating and placing rooms. In the future we could possible swap out various RoomGenerators if we wanted to change the way we perform this part of the algorithm. The same holds for our DungeonGenerator class.

While moving the room placement code I found a potential bug. When we create a room we initialize the room with empty cells and cells with walls on the sides of the room boundaries. The problem comes when we place the room by copying the SideTypes of each cell to the map. By copying the SideTypes we aren’t ensuring that the cells adjacent to the room have side of SideType.Wall. The new PlaceRoom code is now as follows.

        public void PlaceRoom(Point location, Room room, Dungeon dungeon)

        {

            // Offset the room origin to the new location

            room.SetLocation(location);

 

            // Loop for each cell in the room

            foreach (Point roomLocation in room.CellLocations)

            {

                // Translate the room cell location to its location in the dungeon

                Point dungeonLocation = new Point(location.X + roomLocation.X, location.Y + roomLocation.Y);

                dungeon[dungeonLocation].NorthSide = room[roomLocation].NorthSide;

                dungeon[dungeonLocation].SouthSide = room[roomLocation].SouthSide;

                dungeon[dungeonLocation].WestSide = room[roomLocation].WestSide;

                dungeon[dungeonLocation].EastSide = room[roomLocation].EastSide;

 

                // Create room walls on map (either side of the wall)

                if ((roomLocation.X == 0) && (dungeon.HasAdjacentCellInDirection(dungeonLocation, DirectionType.West))) dungeon.CreateWall(dungeonLocation, DirectionType.West);

                if ((roomLocation.X == room.Width – 1) && (dungeon.HasAdjacentCellInDirection(dungeonLocation, DirectionType.East))) dungeon.CreateWall(dungeonLocation, DirectionType.East);

                if ((roomLocation.Y == 0) && (dungeon.HasAdjacentCellInDirection(dungeonLocation, DirectionType.North))) dungeon.CreateWall(dungeonLocation, DirectionType.North);

                if ((roomLocation.Y == room.Height – 1) && (dungeon.HasAdjacentCellInDirection(dungeonLocation, DirectionType.South))) dungeon.CreateWall(dungeonLocation, DirectionType.South);

            }

 

            dungeon.AddRoom(room);

        }

The updated PlaceRoom method now includes a step where it uses the CreateWall method to create a wall between the adjacent cells around the room borders.

The above refactoring process resulted in major structural changes to our code base. Fortunately we have a good set of unit tests and I was able to make these changes without any major headaches. Now we can look at adding doors to our dungeon.

Algorithm Step 13

For every place where the room is adjacent to a corridor or a room, add a door. (If you don’t want doors everywhere, add another parameter that determines when a door should be placed, and when an empty doorway [i.e. archway, etc.] should be placed).

For step 13 we need to determine if a room cell has a corridor cell adjacent to it. Obviously we should only evaluate the cells on the boundaries of our room i.e. the cells with walls. Our AdjacentCellInDirectionIsCorridor method on the Dungeon class will give us exactly what we need to meet this requirement.

Next we need some functionality to create a door. We already have two similar methods called CreateWall and CreateCorridor. We can create a similar method called CreateDoor to create our doorways. Let’s write a test to demonstrate this functionality.

        [Test]

        public void TestCreateDoorBetweenAdjacentCells()

        {

            Dungeon dungeon = new Dungeon(10, 10);

 

            // We now have map filled with rock.

            // Test creating doors in each direction

            dungeon.CreateDoor(new Point(0, 0), DirectionType.South);

 

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

            Assert.IsTrue(dungeon[0, 0].SouthSide == SideType.Door);

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

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

 

            Assert.IsTrue(dungeon[0, 1].NorthSide == SideType.Door);

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

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

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

 

        }

The above test makes use of a new CreateDoor method on the Dungeon class to create a Door on the South side at location (0, 0). We perform a test for this checking that the South side at (0,0) and the North side at (0, 1) are now of type SideType.Door. I excluded the other directions from this code listing (they are available in the source code download).

The code to make this test compile is as follows.

        public Point CreateDoor(Point location, DirectionType direction)

        {

            return CreateSide(location, direction, SideType.Door);

        }

The CreateDoor method is very simple. All I needed to add was the new “Door” SideType. I compile and run the test with no problems.

        [Test]

        public void TestCanPlaceDoors()

        {

            RoomGenerator roomGenerator = new RoomGenerator();

            Dungeon dungeon = new Dungeon(3, 3);

 

            // Create corridors in + shape

            Point location = new Point(1, 1);

            dungeon.CreateCorridor(location, DirectionType.North);

            dungeon.CreateCorridor(location, DirectionType.South);

            dungeon.CreateCorridor(location, DirectionType.West);

            dungeon.CreateCorridor(location, DirectionType.East);

 

            // Create and place room

            Room room = new Room(1, 1);

            room.InitializeRoomCells();

            roomGenerator.PlaceRoom(location, room, dungeon);

 

            roomGenerator.PlaceDoors(dungeon);

 

            Assert.AreEqual(SideType.Door, dungeon[1, 0].SouthSide);

            Assert.AreEqual(SideType.Door, dungeon[0, 1].EastSide);

            Assert.AreEqual(SideType.Door, dungeon[1, 1].NorthSide);

            Assert.AreEqual(SideType.Door, dungeon[1, 1].SouthSide);

            Assert.AreEqual(SideType.Door, dungeon[1, 1].WestSide);

            Assert.AreEqual(SideType.Door, dungeon[1, 1].EastSide);

            Assert.AreEqual(SideType.Door, dungeon[2, 1].WestSide);

            Assert.AreEqual(SideType.Door, dungeon[1, 2].NorthSide);

        }

In the above test we initialize a small Dungeon and place a 1×1 room in the middle. We create corridors leading from this room in all four directions. We then call a new PlaceDoors method on the RoomGenerator class and pass in our dungeon. The test then asserts that each of the room walls have a doorway in them.

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

        public void PlaceDoors(Dungeon dungeon)

        {

            foreach (Room room in dungeon.Rooms)

            {

                foreach (Point cellLocation in room.CellLocations)

                {

                    // Translate the room cell location to its location in the dungeon

                    Point dungeonLocation = new Point(room.Bounds.X + cellLocation.X, room.Bounds.Y + cellLocation.Y);

 

                    // Check if we are on the west boundary of our room

                    // and if there is a corridor to the west

                    if ((cellLocation.X == 0) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.West)))

                        dungeon.CreateDoor(dungeonLocation, DirectionType.West);

 

                    // Check if we are on the east boundary of our room

                    // and if there is a corridor to the east

                    if ((cellLocation.X == room.Width – 1) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.East)))

                        dungeon.CreateDoor(dungeonLocation, DirectionType.East);

 

                    // Check if we are on the north boundary of our room

                    // and if there is a corridor to the north

                    if ((cellLocation.Y == 0) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.North)))

                        dungeon.CreateDoor(dungeonLocation, DirectionType.North);

 

                    // Check if we are on the south boundary of our room

                    // and if there is a corridor to the south

                    if ((cellLocation.Y == room.Height – 1) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.South)))

                        dungeon.CreateDoor(dungeonLocation, DirectionType.South);

                }

            }

        }

The CreateDoors method above is not very sophisticated. All it does is loop through each room in the dungeon and then for each room it checks every cell. It first checks if the cell lies on any of the boundaries of the room and then uses the AdjacentCellInDirectionIsCorridor method to check if there is a corridor cell in the given direction.

If the above conditions are true it creates a door in the direction provided. This implementation will create a doorway for every cell that is adjacent to a corridor even if it means that every cell on the boundary of a room will have a door. I recompile the test and it fails.

After some debugging I see that my test case produced a funny result. The test dungeon places a small 1×1 room in the middle of the ‘+’ shape. The new PlaceRoom method now creates a wall between the adjacent outside sides. This is that our definition of a corridor is determined by the number of walls a cell has. Our small 1×1 corridors are being counted as “rock” because they each have 4 walls.

I change the IsCorridor property on the Cell class to an explicit property rather than a calculated result. I updated the CreateCorridor method to explicitly set the IsCorridor property to true and the SparsifyMaze method to set the IsCorridor property to false when it removes a corridor.

I rerun the unit tests and they all pass.

Below is a screen shot of our dungeon generator using the new PlaceDoors functionality.

exampleoutput1

Our new door placement algorithm is definitely creating doors! Too bad the dungeon now looks terrible. The author doesn’t give much leading on how to place doors in his version of the algorithm. I think we can improve our current implementation by only placing one doorway per room wall as follows.

        public void PlaceDoors(Dungeon dungeon)

        {

            foreach (Room room in dungeon.Rooms)

            {

                bool hasNorthDoor = false;

                bool hasSouthDoor = false;

                bool hasWestDoor = false;

                bool hasEastDoor = false;

 

                foreach (Point cellLocation in room.CellLocations)

                {

                    // Translate the room cell location to its location in the dungeon

                    Point dungeonLocation = new Point(room.Bounds.X + cellLocation.X, room.Bounds.Y + cellLocation.Y);

 

                    // Check if we are on the west boundary of our room

                    // and if there is a corridor to the west

                    if ((cellLocation.X == 0) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.West)) &&

                        (!hasWestDoor))

                    {

                        dungeon.CreateDoor(dungeonLocation, DirectionType.West);

                        hasWestDoor = true;

                    }

 

                    // Check if we are on the east boundary of our room

                    // and if there is a corridor to the east

                    if ((cellLocation.X == room.Width – 1) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.East)) &&

                        (!hasEastDoor))

                    {

                        dungeon.CreateDoor(dungeonLocation, DirectionType.East);

                        hasEastDoor = true;

                    }

 

                    // Check if we are on the north boundary of our room

                    // and if there is a corridor to the north

                    if ((cellLocation.Y == 0) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.North)) &&

                        (!hasNorthDoor))

                    {

                        dungeon.CreateDoor(dungeonLocation, DirectionType.North);

                        hasNorthDoor = true;

                    }

 

 

                    // Check if we are on the south boundary of our room

                    // and if there is a corridor to the south

                    if ((cellLocation.Y == room.Height – 1) &&

                        (dungeon.AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.South)) &&

                        (!hasSouthDoor))

                    {

                        dungeon.CreateDoor(dungeonLocation, DirectionType.South);

                        hasSouthDoor = true;

                    }

 

                }

            }

        }

The new PlaceDoors method above keeps track of a Boolean flag for each side of the room. It will only place a door on a particular side if no doors have been placed previously. The new output can be seen in the following screen shot.

exampleoutput2

The new output is much better and looks like something to go adventuring in. This is of course still very basic and we could add additional functionality to create archways, secret doors, etc.

The next step is to convert our dungeon into a tile-based representation.

Converting to tiles

Our current cell-based dungeon representation is unsuitable for tile-based games such as roguelikes. The reason for this is that tiles normally only represent one feature of a dungeon i.e. a wall is only a wall, a door is only a door. In our current cell-based structure one cell represents four sides and can’t be displayed using a tile-based algorithm.

To convert to a tile-based structure we need to “expand” our cells into tiles, with each tile only holding one piece of information. This means that each side will be represented by a separate tile. For this process we are only interested in non-rock cells i.e. corridor or room cells.

We can represent our tiles as a 2-dimensional array of integer values. The specific values for rock, wall, floor and door can be any value we choose. For the moment I will use 0 for rock, 1 for corridor and 2 for doors. [Edit: I updated this to a Enum called TileType after an anonymous comment. I didn’t want to use the Enum originally as I wanted to decouple code using the dungeon generator from having to use my Enum. Still not sure if its a good idea, but when I’ve finished my roguelike I’ll write a post about it.]

The following test illustrates the functionality required to convert our cell-based structure to tiles.

        [Test]

        public void TestExpandWithCorridorTiles()

        {

            RoomGenerator roomGenerator = new RoomGenerator();

            Dungeon dungeon = new Dungeon(4, 4);

 

            dungeon.CreateCorridor(new Point(2, 1), DirectionType.North);

            dungeon.CreateCorridor(new Point(1, 2), DirectionType.South);

            dungeon.CreateCorridor(new Point(1, 1), DirectionType.West);

            dungeon.CreateCorridor(new Point(2, 2), DirectionType.East);

 

            // Create and place room

            Room room = new Room(2, 2);

            room.InitializeRoomCells();

            roomGenerator.PlaceRoom(new Point(1, 1), room, dungeon);

 

            int[,] dungeonTiles = DungeonGenerator.ExpandToTiles(dungeon);

 

            // Assert the dimensions are correct

            Assert.AreEqual(dungeon.Width * 2 + 1, dungeonTiles.GetUpperBound(0) + 1);

            Assert.AreEqual(dungeon.Height * 2 + 1, dungeonTiles.GetUpperBound(1) + 1);

 

            // Assert tiles were expanded correctly

            for(int x = 0; x < dungeon.Width * 2 + 1; x++)

            {

                for(int y = 0; y < dungeon.Height * 2 + 1; y++)

                {

                    if (((x == 5) & (y == 1)) ||

                    ((x == 1) & (y == 3)) ||

                    ((x == 3) & (y == 3)) ||

                    ((x == 4) & (y == 3)) ||

                    ((x == 5) & (y == 3)) ||

                    ((x == 3) & (y == 4)) ||

                    ((x == 4) & (y == 4)) ||

                    ((x == 5) & (y == 4)) ||

                    ((x == 3) & (y == 5)) ||

                    ((x == 4) & (y == 5)) ||

                    ((x == 5) & (y == 5)) ||

                    ((x == 7) & (y == 5)) ||

                    ((x == 3) & (y == 7))

                        )

                        Assert.IsTrue(dungeonTiles[x, y] == (int)TileType.Empty);

                    else

                        Assert.IsTrue(dungeonTiles[x, y] == (int)TileType.Rock);

                }

            }

        }

In the above test we create a small 4×4 dungeon with a 2×2 room in the middle. We then create a corridor in each direction from each corner of the room. We then invoke a new method on the DungeonGenerator class called ExpandToTiles. This method takes a Dungeon instance as input parameter and returns a 2-dimensional array of integer values representing the tiles.

Our test then asserts that the 2-dimensional array is twice the size + 1 of the dungeon in width and height. The reason for this is that there will always be a ring of rock around the dungeon and a tile for each of the sides are shared between the dungeon cells.

The test then loops through each value in the expanded array and tests to see if the value is either rock, corridor or a door. The above test is only testing walls and corridors. I have included a test for doors in the source code download.

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

        public static int[, ] ExpandToTiles(Dungeon dungeon)

        {

            // Instantiate our tile array

            int[, ] tiles = new int[dungeon.Width * 2 + 1, dungeon.Height * 2 + 1];

 

            // Initialize the tile array to rock

            for (int x = 0; x < dungeon.Width * 2 + 1; x++)

                for (int y = 0; y < dungeon.Height * 2 + 1; y++)

                    tiles[x, y] = (int)TileType.Rock;

 

            // Fill tiles with corridor values for each room in dungeon

            foreach (Room room in dungeon.Rooms)

            {

                // Get the room min and max location in tile coordinates

                Point minPoint = new Point(room.Bounds.Location.X * 2 + 1, room.Bounds.Location.Y * 2 + 1);

                Point maxPoint = new Point(room.Bounds.Right * 2, room.Bounds.Bottom * 2 );

 

                // Fill the room in tile space with an empty value

                for (int i = minPoint.X; i < maxPoint.X; i++)

                    for (int j = minPoint.Y; j < maxPoint.Y; j++)

                        tiles[i, j] = (int)TileType.Empty;

            }

 

            // Loop for each corridor cell and expand it

            foreach (Point cellLocation in dungeon.CorridorCellLocations)

            {

                Point tileLocation = new Point(cellLocation.X*2 + 1, cellLocation.Y*2 + 1);

                tiles[tileLocation.X, tileLocation.Y] = (int)TileType.Empty;

 

                if (dungeon[cellLocation].NorthSide == SideType.Empty) tiles[tileLocation.X, tileLocation.Y – 1] = (int)TileType.Empty;

                if (dungeon[cellLocation].NorthSide == SideType.Door) tiles[tileLocation.X, tileLocation.Y – 1] = (int)TileType.Door;

 

                if (dungeon[cellLocation].SouthSide == SideType.Empty) tiles[tileLocation.X, tileLocation.Y + 1] = (int)TileType.Empty;

                if (dungeon[cellLocation].SouthSide == SideType.Door) tiles[tileLocation.X, tileLocation.Y + 1] = (int)TileType.Door;

 

                if (dungeon[cellLocation].WestSide == SideType.Empty) tiles[tileLocation.X – 1, tileLocation.Y] = (int)TileType.Empty;

                if (dungeon[cellLocation].WestSide == SideType.Door) tiles[tileLocation.X – 1, tileLocation.Y] = (int)TileType.Door;

 

                if (dungeon[cellLocation].EastSide == SideType.Empty) tiles[tileLocation.X + 1, tileLocation.Y] = (int)TileType.Empty;

                if (dungeon[cellLocation].EastSide == SideType.Door) tiles[tileLocation.X + 1, tileLocation.Y] = (int)TileType.Door;

            }

 

            return tiles;

        }

The above ExpandToTiles method instantiates a new 2-dimensional array to the size of our dungeon.Width * 2 + 1 and dungeon.Height * 2 +1. It then loops through each position in the array and sets the value to zero (or rock).

Next the method loops through every map in the dungeon and fills the corresponding tile are with empty tiles.

Next the method loops through every “corridor” cell location in the dungeon. At every location it checks each side to determine if its empty or a door and fills the adjacent tile with appropriate TileType. I compile and run the unit tests and they pass with no problems. Our new tile-based output now looks as follows.

exampleoutput3 

In the above screen shot I made use of the ‘+’ character to indicate doors and the ‘.’ character is the floor area.

Conclusion

In part 10 of the Generating Random Dungeons article series we started by refactoring our code by creating a new Map super class and renaming the old Map class to Dungeon. We also cleaned up some of the naming conventions and moved the Room generation and placement functionality into a new RoomGenerator class.

Next we implemented functionality to add doors to our rooms. This functionality was implemented using a very basic algorithm. A lot more can be added to make door placement a bit more intelligent (or maybe meaningful). I feel that the current implementation, however, is good enough as a prototype.

After that we converted the cell-based dungeon to a tile-based representation. The tile-based representation is important if you’re going to be using the random dungeons to create tile-based games such as roguelikes.

This part concludes the series on Generating Random Dungeons. I hope you all enjoyed it and learnt something through the process. I know I did.

Generating Random Dungeons (part 9)

Introduction

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 remove dead-ends by evaluating all the dead-end cells in the map. For each dead-end cell, we then checked a deadEndRemovalModifier to determine if we should remove that particular dead-end.

In this article we will look at creating and placing rooms within our dungeon.

Algorithm Step 11

This was perhaps the trickiest step. Looking at my generator, you’ll see three parameters: “room count” (Rn), “room width”, (Rw), and “room height” (Rh).

Generating rooms is actually easy: Rw is just a random number between the minimum and maximum widths. Rh is generated similarly.

For step 11 we need to be able to create a room with a random width (Rw) and height (Rh) as specified by minimum and maximum width and height parameters. We will define a room as a 2-dimensional array of cells similar to our Map class. We could inherit from the Map class, but I don’t see any benefit at the moment.

Currently we initialize our maze by setting each cell to “rock” i.e. the map starts out filled with rock. Rooms are typically defined as a rectangle with walls along the boundaries.

Therefore, to create a room, we will need to create a 2-dimensional array of cells with random width and height (as specified by the input parameters). We will then need to create walls on the boundaries of the room “map” and mark the inside cells as empty.

        [Test]

        public void TestCanCreateRandomSizeRoom()

        {

            int minRoomWidth = 2;

            int maxRoomWidth = 5;

            int minRoomHeight = 2;

            int maxRoomHeight = 5;

            Room room = Generator.CreateRoom(minRoomWidth, maxRoomWidth, minRoomHeight, maxRoomHeight);

 

            Assert.IsTrue(((minRoomWidth <= room.Width) && (room.Width <= maxRoomWidth)));

            Assert.IsTrue(((minRoomHeight <= room.Height) && (room.Height <= maxRoomHeight)));

        }

In the above test we define the room’s min and max boundary values. We then call the CreateRoom method on the Generator class. Our test asserts that the new room instance Width and Height properties falls within the boundaries as specified by our input parameters.

The code to make this test compile is as follows.

        public static Room CreateRoom(int minRoomWidth, int maxRoomWidth, int minRoomHeight, int maxRoomHeight)

        {

            return new Room(Random.Instance.Next(minRoomWidth, maxRoomWidth), Random.Instance.Next(minRoomHeight, maxRoomHeight));

        }

The above code uses a Room class that I’ve created. The new Room class is similar to the Map class implementation. All it has is a 2-dimensional array of cells and Width and Height properties as required by our test.

The CreateRoom method on the Generator class takes as input parameters the minRoomWidth, maxRoomWidth, minRoomHeight and maxRoomHeight. These parameters are used by the Random number generator to select random width and height values for the new Room instance.

I recompile the code, run the test and it runs with no problems.

The next test we need to write is to make sure that the room is initialized with its borders set to walls and all the inside cells to empty.

        [Test]

        public void TestCreateRoomInitializesCellsCorrectly()

        {

            int minRoomWidth = 2;

            int maxRoomWidth = 5;

            int minRoomHeight = 2;

            int maxRoomHeight = 5;

            Room room = Generator.CreateRoom(minRoomWidth, maxRoomWidth, minRoomHeight, maxRoomHeight);

 

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

            {

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

                {

                    Assert.IsTrue(room[x, y].WestSide == ((x == 0) ? SideType.Wall : SideType.Empty));

                    Assert.IsTrue(room[x, y].EastSide == ((x == room.Width – 1) ? SideType.Wall : SideType.Empty));

                    Assert.IsTrue(room[x, y].NorthSide == ((y == 0) ? SideType.Wall : SideType.Empty));

                    Assert.IsTrue(room[x, y].SouthSide == ((y == room.Height – 1) ? SideType.Wall : SideType.Empty));

                }

            }

        }

In the above test we once again call the CreateRoom method on the Generator class. We then loop through each cell in the room and test if the side of a cell is either a wall or empty. Sides should have walls if the cell lies on the boundaries of the room.

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

        public void InitializeRoomCells()

        {

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

            {

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

                {

                    Cell cell = new Cell();

 

                    cell.WestSide = (x == 0) ? SideType.Wall : SideType.Empty;

                    cell.EastSide = (x == Width – 1) ? SideType.Wall : SideType.Empty;

                    cell.NorthSide = (y == 0) ? SideType.Wall : SideType.Empty;

                    cell.SouthSide = (y == Height – 1) ? SideType.Wall : SideType.Empty;

 

                    this[x, y] = cell;

                }

            }

        }

I added the InitializeRoomCells method to the room class. This method is similar to the MarkCellsUnvisited method on the Map class. It has some additional functionality to set the SideType of each side of a cell depending on where it lies within the room. The effect is that cells on the boundaries of the room will have walls for their outer sides.

I recompile the code and run the test, but there is a problem. Our cells in the Room are null. I forgot to add the call to the InitializeRoomCells method to the CreateRoom method. I make the change to the code and the test runs fine.

        public static Room CreateRoom(int minRoomWidth, int maxRoomWidth, int minRoomHeight, int maxRoomHeight)

        {

            Room room = new Room(Random.Instance.Next(minRoomWidth, maxRoomWidth), Random.Instance.Next(minRoomHeight, maxRoomHeight));

            room.InitializeRoomCells();

            return room;

        }

Now we have the ability to create random sized rooms that are empty and have walls around them. The next step is to place our rooms within the dungeon.

Algorithm Step 12

  1. Set the “best” score to infinity (or some arbitrarily huge number). 
  2. Generate a room such that Wmin <= Rw <= Wmax and Hmin <= Rh <= Hmax.
  3. For each cell C in the dungeon, do the following:
  • Put the upper-left corner of the room at C. Set the “current” score to 0.
  • For each cell of the room that is adjacent to a corridor, add 1 to the current score.
  • For each cell of the room that overlaps a corridor, add 3 to the current score.
  • For each cell of the room that overlaps a room, add 100 to the current score.
  • If the current score is less than the best score, set the best score to the current score and note C as the best position seen yet.
  1. Place the room at the best position (where the best score was found).

Step 12 of the algorithm makes use of the CreateRoom functionality we’ve developed above to generate a new room. We now need to decide on a location within our maze to place the new room. The algorithm is actually quite simple. We need to loop for each cell in our maze and at each location calculate the “placement” score for our room.

The “placement” score is calculated by checking each cell in our room. If a cell is adjacent to a corridor then we add 1 to our score, if the cell overlaps a corridor then we add 3 to our score and finally if we the cell overlaps a room then we add 100 to our current score.

From the above we will need to be able to test a room cell against a map cell (for the adjacent and overlapping corridor test), but we also need to know about other room’s cells. We will therefore need a list of rooms we’ve already placed to be able to check if we overlap their boundaries.

As we loop through each cell in the maze we compare the “placement” score with the previous best. If the score is lower we make the best score our current score. Once we’ve looped through all the cells we place the room at the location with the lowest placement score.

We repeat this process for the number of rooms to place within the dungeon.

The test to place rooms within the dungeon is as follows.

        [Test]

        public void TestCanPlaceRoomsWithinDungeon()

        {

            int minRoomWidth = 2;

            int maxRoomWidth = 5;

            int minRoomHeight = 2;

            int maxRoomHeight = 5;

            int noOfRoomsToPlace = 5;

 

            Map map = Generator.Generate(25, 25, 30, 70, 70);

 

            Generator.PlaceRooms(map, noOfRoomsToPlace, minRoomWidth, maxRoomWidth, minRoomHeight, maxRoomHeight);

 

            Assert.IsTrue(map.Rooms.Count == noOfRoomsToPlace );

 

            foreach (Room room in map.Rooms)

            {

                Assert.IsTrue(minRoomWidth <= room.Width);

                Assert.IsTrue(room.Width <= maxRoomWidth);

                Assert.IsTrue(minRoomHeight <= room.Height);

                Assert.IsTrue(room.Height <= maxRoomHeight);

                Assert.IsTrue(map.Bounds.Contains(room.Bounds));

            }

        }

The above test defines the parameters for room generation and placement. It then generates a dungeon and calls the new PlaceRooms method on the Generator class passing in the generated dungeon and the room parameters. The test then asserts that the number of rooms in the map equals the noOfRoomsToPlace. The test then loops through each room in the dungeon and checks that its bounds falls within the limits specified by the parameters and whether the room falls within the bounds of the map.

The test requires a new PlaceRooms method that will generate and place the rooms on our map. The Map now requires an additional Rooms property that will expose the list of Rooms created. We also need some kind of Bounds property on our Map and Room class to perform the last bounds check in the test.

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

        public static void PlaceRooms(int noOfRoomsToPlace, int minRoomWidth, int maxRoomWith, int minRoomHeight, int maxRoomHeight)

        {

 

        }

 

        private readonly List<Room> rooms = new List<Room>();

 

        public ReadOnlyCollection<Room> Rooms

        {

            get { return rooms.AsReadOnly(); }

        }

In the above code listing I added the PlaceRooms method to the Generator class and created a new rooms field on the Map class. I expose the rooms field as a Read Only property using the List<T>.AsReadOnly method. The next step is to add the bounds checking functionality to the Map and Room classes.

        private Rectangle bounds;

       

        public Map(int width, int height)

        {

            cells = new Cell[width,height];

            bounds = new Rectangle(0, 0, width, height);

        }

       

        public Rectangle Bounds

        {

            get { return bounds; }

        }

To implement the bounds checking I added a new bounds field of type Rectangle to the Map and Room classes. I show the implementation of the Map class above. The Rectangle type gives us functionality to do intersect and contains calculations on points and other rectangles. The new Bounds property will also allow us to simplify the implementation of the Map and Room classes. I will discuss the possible refactorings in the next article.

I compile the room placement test and it compiles, but fails as expected. We haven’t implemented actual PlaceRooms method. To do this we need some additional functionality.

First we need to be able to check if a there is a corridor cell adjacent to a given location. The test is as follows.

        [Test]

        public void TestAdjacentCellIsNotCorridor()

        {

            Map map = new Map(3, 3);

            map.MarkCellsUnvisited(); // Fill map with rock

 

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

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

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

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

        }

 

        [Test]

        public void TestAdjacentCellIsCorridor()

        {

            Map map = new Map(3, 3);

            map.MarkCellsUnvisited();

 

            // Create some corridor cells from our current location outwards

            map.CreateCorridor(new Point(1, 1), DirectionType.North);

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

            map.CreateCorridor(new Point(1, 1), DirectionType.West);

            map.CreateCorridor(new Point(1, 1), DirectionType.East);

 

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

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

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

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

        }

The above tests make use of a new method on the Map class called AdjacentCellInDirectionIsCorridor. This method will return a Boolean result of “True” if the adjacent cell is a corridor. A cell is a corridor if it has 3 or less sides that aren’t walls.

The first test sets up a small map and marks all the cells as unvisited, leaving the map as solid rock. We then assert that the location in the middle of the map has no adjacent corridor cells in each direction.

The second test again initializes the map to rock, but then creates corridors from the location in the middle of the map outwards. We then assert that the location in the middle has an adjacent corridor cell in each direction.

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

        public bool AdjacentCellInDirectionIsCorridor(Point location, DirectionType direction)

        {

            Point target = GetTargetLocation(location, direction);

 

            switch (direction)

            {

                case DirectionType.North:

                    return this[target].IsCorridor;

                case DirectionType.West:

                    return this[target].IsCorridor;

                case DirectionType.South:

                    return this[target].IsCorridor;

                case DirectionType.East:

                    return this[target].IsCorridor;

                default:

                    throw new InvalidOperationException();

            }

        }

The code for the AdjacentCellInDirectionIsCorridor method is copied from our AdjacentCellInDirectionIsVisited method. Instead of checking if the adjacent cell is visited we now check if the cell is a corridor. I added a new property to the Cell class (IsCorridor) to make the WallCount < 4 check more meaningful.

I compile and run the tests and they all pass with no problems.

Next we need to test if a location within the map is a corridor. This can be done quite easily using our new IsCorridor property on the Cell class.

        [Test]

        public void TestCurrentCellIsNotCorridor()

        {

            Map map = new Map(3, 3);

            map.MarkCellsUnvisited();

 

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

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

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

        }

 

        [Test]

        public void TestCurrentCellIsCorridor()

        {

            Map map = new Map(3, 3);

            map.MarkCellsUnvisited();

 

            // Create some corridor cells from our current location outwards

            map.CreateCorridor(new Point(1, 1), DirectionType.North);

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

            map.CreateCorridor(new Point(1, 1), DirectionType.West);

            map.CreateCorridor(new Point(1, 1), DirectionType.East);

 

            Assert.IsFalse(map[0, 0].IsCorridor);

            Assert.IsTrue(map[1, 0].IsCorridor);

            Assert.IsFalse(map[2, 0].IsCorridor);

            Assert.IsTrue(map[0, 1].IsCorridor);

            Assert.IsTrue(map[1, 1].IsCorridor);

            Assert.IsTrue(map[2, 1].IsCorridor);

            Assert.IsFalse(map[0, 2].IsCorridor);

            Assert.IsTrue(map[1, 2].IsCorridor);

            Assert.IsFalse(map[2, 2].IsCorridor);

        }

The first test initializes our Map to solid rock and then loops through each location in the map and asserts that each location is not a corridor cell. For the second test we create a corridor in each direction from the location in the middle of the map. We then assert that the locations on the outside corners of the map aren’t corridor cells and that the locations in the middle (forming a + shape) are corridor cells.

We don’t need to add any additional functionality to our code to make the above tests compile and pass. I’m still in two minds on whether I need to wrap this functionality into its own method.

Next we need to write a test to check if the current location overlaps an existing room cell.

        [Test]

        public void TestLocationIsOutsideRoom()

        {

            Room room = new Room(2, 2);

            Assert.IsFalse(room.Bounds.Contains(new Point(-1, -1)));

            Assert.IsFalse(room.Bounds.Contains(new Point(2, 2)));

        }

 

        [Test]

        public void TestLocationIsInsideRoom()

        {

            Room room = new Room(2, 2);

            Assert.IsTrue(room.Bounds.Contains(new Point(0, 0)));

            Assert.IsTrue(room.Bounds.Contains(new Point(1, 1)));

        }

In the above tests I check if a location falls within the boundaries of a room by calling the Contains method of our new Bounds property on the room class. The first test checks locations outside the bounds and the second test checks locations inside the bounds of the room.

The above tests do not take into account rooms that have been offset from location (0, 0). We will need this functionality when we start placing rooms, but we can add it when we get there. No new code is needed to make the above tests compile and pass.

[I am beginning to think it might not be a bad idea to extract some of the common functionality from the Map class into a super class and have the Room class inherit from this super class. We could call the super class a “Map” and rename our current Map class to “Dungeon” or “Maze”. I will do this refactoring in a separate article as this current article is getting a bit long.]

Using the above functionality we can now calculate the room placement score for a given room and location within the map. The test which demonstrates this functionality is as follows.

        [Test]

        public void TestCanCalculateRoomPlacementScore()

        {

            Map map = new Map(3, 3);

            map.MarkCellsUnvisited();

 

            // Create some corridor cells from our current location outwards

            map.CreateCorridor(new Point(1, 1), DirectionType.North);

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

            map.CreateCorridor(new Point(1, 1), DirectionType.West);

            map.CreateCorridor(new Point(1, 1), DirectionType.East);

 

            // The scores for the cells in the room are as follows

            // (0, 0) = 2; (0, 1) = 4; (1, 0) = 4; (1, 1) = 5

            // Our room placement score should total 15

            Assert.AreEqual(15, map.CalculateRoomPlacementScore(new Point(0, 0), new Room(2, 2)));

        }

In the above test we initialize our map and create corridors in a ‘+’ formation as before. We then make a call to a new CalculateRoomPlacementScore method on the map using the Point (0, 0) and Room with size (2, 2) as input parameters. The room placement score should equal 15 to make the test pass for the given input parameters.

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

        public int CalculateRoomPlacementScore(Point location, Room room)

        {

            // Check if the room at the given location will fit inside the bounds of the map

            if (Bounds.Contains(new Rectangle(location, new Size(room.Width + 1, room.Height + 1))))

            {

                int roomPlacementScore = 0;

 

                // Loop for each cell in the room

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

                {

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

                    {

                        // Translate the room cell location to its location in the dungeon

                        Point dungeonLocation = new Point(location.X + x, location.Y + y);

 

                        // Add 1 point for each adjacent corridor to the cell

                        if (AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.North)) roomPlacementScore++;

                        if (AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.South)) roomPlacementScore++;

                        if (AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.West)) roomPlacementScore++;

                        if (AdjacentCellInDirectionIsCorridor(dungeonLocation, DirectionType.East)) roomPlacementScore++;

 

                        // Add 3 points if the cell overlaps an existing corridor

                        if (this[dungeonLocation].IsCorridor) roomPlacementScore += 3;

 

                        // Add 100 points if the cell overlaps any existing room cells

                        foreach (Room dungeonRoom in Rooms)

                            if (dungeonRoom.Bounds.Contains(dungeonLocation))

                                roomPlacementScore += 100;

                    }

                }

 

                return roomPlacementScore;

            }

            else

            {

                return int.MaxValue;

            }

        }

The CalculateRoomPlacementScore method first checks if the room at the provided location will fit into the bounds of the Map. It will return a very high number if it falls outside the bounds, leading to the location eventually being discarded. If the location is valid we then loop through each cell in the room. First the cell location is translated to the map or dungeon location. We then make use of our scoring functionality to calculate the room placement score.

The last bit of functionality we need to complete the room placement algorithm is the code to actually place the room within our dungeon. All this should really do is copy the layout of the room cells to the dungeon starting at a given location and add the room the a list of rooms already placed. The code to test this functionality is as follows.

        [Test]

        public void TestPlaceRoomOffsetsRoomToNewLocation()

        {

            Map map = new Map(3, 3);

            map.MarkCellsUnvisited();

 

            Room room = new Room(2, 2);

            room.InitializeRoomCells();

 

            map.PlaceRoom(new Point(1, 1), room);

 

            // Assert the room has been offset to location (1, 1)

            Assert.AreEqual(1, room.Bounds.X);

            Assert.AreEqual(1, room.Bounds.Y);

            // Assert the room’s dimensions have been preserved

            Assert.AreEqual(2, room.Bounds.Width);

            Assert.AreEqual(2, room.Bounds.Height);

        }

 

        [Test]

        public void TestPlaceRoomAddsToRoomCollectionOnMap()

        {

            Map map = new Map(3, 3);

            map.MarkCellsUnvisited();

 

            Room room = new Room(2, 2);

            room.InitializeRoomCells();

 

            map.PlaceRoom(new Point(1, 1), room);

 

            // Assert the room was added to the rooms collection

            Assert.AreEqual(1, map.Rooms.Count);

            Assert.IsTrue(map.Rooms.Contains(room));

        }

 

        [Test]

        public void TestPlaceRoomUpdatesMapLayoutToRoomLayout()

        {

            Map map = new Map(3, 3);

            map.MarkCellsUnvisited();

 

            Room room = new Room(2, 2);

            room.InitializeRoomCells();

 

            Point location = new Point(1, 1);

            map.PlaceRoom(location, room);

 

            // Loop through each cell in the room and make sure that the sides

            // in the corresponding cell of the map are the same

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

            {

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

                {

                    // Translate the room cell location to its location in the dungeon

                    Point dungeonLocation = new Point(location.X + x, location.Y + y);

                    Assert.AreEqual(map[dungeonLocation].NorthSide, room[x, y].NorthSide);

                    Assert.AreEqual(map[dungeonLocation].SouthSide, room[x, y].SouthSide);

                    Assert.AreEqual(map[dungeonLocation].WestSide, room[x, y].WestSide);

                    Assert.AreEqual(map[dungeonLocation].EastSide, room[x, y].EastSide);

                }

            }

        }

The above tests create a small map filled with rock and then invoke the PlaceRoom method on the Map class. The new PlaceRoom method will take as input parameters the location at which to place the room and the room to place.

The first test asserts that the room was offset to the location specified and that the dimensions of the room were preserved. The second test asserts that the room was added to the placed rooms collection on the Map. The third test asserts that the layout of the dungeon cells were updated to that of the corresponding room cell.

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

        public void PlaceRoom(Point location, Room room)

        {

            // Offset the room origin to the new location

            room.SetLocation(location);

 

            // Loop for each cell in the room

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

            {

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

                {

                    // Translate the room cell location to its location in the dungeon

                    Point dungeonLocation = new Point(location.X + x, location.Y + y);

                    this[dungeonLocation].NorthSide = room[x, y].NorthSide;

                    this[dungeonLocation].SouthSide = room[x, y].SouthSide;

                    this[dungeonLocation].WestSide = room[x, y].WestSide;

                    this[dungeonLocation].EastSide = room[x, y].EastSide;

                }

            }

 

            rooms.Add(room);

        }

The PlaceRoom method updates the offset of the Room instance by setting the Bounds rectangle to the provided location. We then loop for each cell in the room and update the layout of the dungeon cell with the corresponding room cell.

I compile the code, run the tests and they all pass.

We now have enough functionality to implement our room placement algorithm. The updated PlaceRooms method is now as follows.

        public static void PlaceRooms(Map map, int noOfRoomsToPlace, int minRoomWidth, int maxRoomWith, int minRoomHeight, int maxRoomHeight)

        {

            // Loop for the amount of rooms to place

            for (int roomCounter = 0; roomCounter < noOfRoomsToPlace; roomCounter++)

            {

                Room room = CreateRoom(minRoomWidth, maxRoomWith, minRoomHeight, maxRoomHeight);

                int bestRoomPlacementScore = int.MaxValue;

                Point? bestRoomPlacementLocation = null;

 

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

                {

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

                    {

                        Point currentRoomPlacementLocation = new Point(x, y);

                        int currentRoomPlacementScore = map.CalculateRoomPlacementScore(currentRoomPlacementLocation, room);

 

                        if (currentRoomPlacementScore < bestRoomPlacementScore)

                        {

                            bestRoomPlacementScore = currentRoomPlacementScore;

                            bestRoomPlacementLocation = currentRoomPlacementLocation;

                        }

                    }

                }

 

                // Create room at best room placement cell

                if (bestRoomPlacementLocation != null)

                    map.PlaceRoom(bestRoomPlacementLocation.Value, room);

            }

        }

The PlaceRooms method loops for each room specified by the noOfRoomsToPlace input parameter. First it creates a new Room using the CreateRoom method and the provided input parameters. We then loop for each cell in the Map and calculate the room placement score for each location. The room is then placed at the location that had the lowest score.

The following is a screen shot using our new room placement code with noOfRoomsToPlace = 5, minRoomWidth = 2, maxRoomWidth = 5, minRoomHeight = 2, maxRoomHeight = 5.

exampleoutput1

The above screen shot seems ok, but we have a problem. There are some rooms which aren’t connected to any part of the dungeon. We’ll need to make a change to our algorithm to ensure that rooms are always created adjacent to a corridor within the dungeon.

Fortunately this change is quite simple to implement. Instead of evaluating all the cells within our map, we should just evaluate the cells containing corridors. We can add this functionality by adding a CorridorCells enumerator to our Map class as follows.

        public IEnumerable<Point> CorridorCellLocations

        {

            get

            {

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

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

                        if (this[x, y].IsCorridor) yield return new Point(x, y);

            }

        }

The CorridorCellLocations property loops through each cell in the map and yield returns when the location is a corridor cell. The updated PlaceRooms method is now as follows.

                foreach (Point currentRoomPlacementLocation in map.CorridorCellLocations)

                {

                    int currentRoomPlacementScore = map.CalculateRoomPlacementScore(currentRoomPlacementLocation, room);

 

                    if (currentRoomPlacementScore < bestRoomPlacementScore)

                    {

                        bestRoomPlacementScore = currentRoomPlacementScore;

                        bestRoomPlacementLocation = currentRoomPlacementLocation;

                    }

                }

I’ve removed the two nested for loops and replaced them with a foreach loop as seen above. The code is a bit simpler to read and the CorridorCellLocations property provides a bit more meaning to the code. I rerun the tests and everything passes. The new sample output is now as follows.

exampleoutput2

By only evaluating corridor cells as valid locations for placing rooms we eliminated the possibility of having rooms that are disconnected from the dungeon corridors.

Conclusion

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

The requirement was to create random sized rooms and place them within the dungeon. To meet these requirements we added quite a lot of functionality to our classes and they are beginning to feel a bit bloated.

There is a lot of commonality between the Room and Map classes and I will deal with refactoring them into a super class in the next article. I also find that I’m using two for loops a lot when evaluating all the cells within a Map or Room and we can possible simplify this with an Enumerator.

In part 10 of this article series we will look at refactoring the code base and adding some doors to our rooms.

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.

Generating Random Dungeons (part 7)

Introduction

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

The requirement was to be able to identify all the dead-end corridor cells in the map and to “erase” them. In doing so we would be able to remove corridor cells from the map and create impassible “rock” cells.

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

Algorithm Step 8

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

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

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

The test that satisfies this requirement is as follows.

        [Test]

        public void TestMinSparsenessFactor()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            Generator.CreateDenseMaze(map, 50);

            Generator.SparsifyMaze(map, 0);

 

            // Assert that no cells were turned into rock

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

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

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

        }

 

        [Test]

        public void TestMaxSparsenessFactor()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            Generator.CreateDenseMaze(map, 50);

            Generator.SparsifyMaze(map, 100);

 

            // Assert that all cells were turned into rock

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

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

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

        }

 

        [Test]

        public void TestMidSparsenessFactor()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

            Generator.CreateDenseMaze(map, 50);

            Generator.SparsifyMaze(map, 50);

 

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

            int currentRockCellCount = 0;

 

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

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

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

 

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

            Assert.AreEqual(targetRockCellCount, currentRockCellCount);

        }

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

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

        public bool IsDeadEnd

        {

            get { return WallCount == 3; }

        }

 

        public int WallCount

        {

            get

            {

                int wallCount = 0;

                if (northSide == SideType.Wall) wallCount++;

                if (southSide == SideType.Wall) wallCount++;

                if (westSide == SideType.Wall) wallCount++;

                if (eastSide == SideType.Wall) wallCount++;

                return wallCount;

            }

        }

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

        public static void SparsifyMaze(Map map, int sparsenessModifier)

        {

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

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

 

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

 

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

            {

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

                {

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

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

                }

 

                Point point = enumerator.Current;

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

            }

        }

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

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

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

exampleoutput

Conclusion

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

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

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

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

Generating Random Dungeons (part 6)

Introduction

In part 5 of the Generating Random Dungeons article series we implemented functionality to allow us to specify a “randomness” factor which influenced how often our corridor directions changed. This allowed us to either create mazes with long winding corridors or with corridors that change at every turn or a combination of both. 

This is all fine and well, but our maze is not really a dungeon as generated by the algorithm we are implementing. A dungeon typically has some winding corridors, corridors intersecting with each other, corridors looping around on themselves, and of course some rooms (we’ll get to this I promise). The implication is that our map should have some areas filled with rock i.e. not completely filled with corridors.

The author of the algorithm calls this the “sparseness” factor of the dungeon. Let’s see how we’ll add this feature.

Algorithm Step 7

Look at every cell in the maze grid. If the given cell contains a corridor that exits the cell in only one direction (in other words, if the cell is the end of a dead-end hallway), “erase” that cell by removing the corridor.

The first part of this step requires that we evaluate each cell in the maze (or map) and then check if that cell is a dead end. We can determine if a cell is a dead-end by evaluating how many of its sides are walls. Cells with 3 wall sides will therefore be dead-end cells.

Let’s write a test to check if a cell is a dead-end.

        [Test]

        public void TestIfCellIsDeadEnd()

        {

            Cell cell = new Cell();

            cell.NorthSide = SideType.Empty;

            Assert.IsTrue(cell.IsDeadEnd);

 

            cell = new Cell();

            cell.WestSide = SideType.Empty;

            Assert.IsTrue(cell.IsDeadEnd);

 

            cell = new Cell();

            cell.SouthSide = SideType.Empty;

            Assert.IsTrue(cell.IsDeadEnd);

 

            cell = new Cell();

            cell.EastSide = SideType.Empty;

            Assert.IsTrue(cell.IsDeadEnd);

        }

 

        [Test]

        public void TestIfCellIsNotDeadEnd()

        {

            Cell cell = new Cell();

            Assert.IsFalse(cell.IsDeadEnd);

 

            cell = new Cell();

            cell.NorthSide = SideType.Empty;

            cell.EastSide = SideType.Empty;

            Assert.IsFalse(cell.IsDeadEnd);

 

            cell.WestSide = SideType.Empty;

            Assert.IsFalse(cell.IsDeadEnd);

 

            cell.SouthSide = SideType.Empty;

            Assert.IsFalse(cell.IsDeadEnd);

        }

In the above tests we added a property to the Cell class which returns a Boolean value indicating if the cell is a dead-end or not. Our first test checks that the property will return “True” when only one of either side is not a wall (or empty). The second test ensures that for a cell with 4, 2, 1 and no walls the property will return a “False” value.

The code to make these tests compile is as follows.

        public bool IsDeadEnd

        {

            get

            {

                int wallCount = 0;

                if (northSide == SideType.Wall) wallCount++;

                if (southSide == SideType.Wall) wallCount++;

                if (westSide == SideType.Wall) wallCount++;

                if (eastSide == SideType.Wall) wallCount++;

                return wallCount == 3;

            }

        }

The above code checks each side of the cell and increments a wallCount variable for each side that is a wall. It then checks if there were 3 walls in the cell and returns a “True” result (otherwise it returns “False”).

I compile the code and run the tests and they all pass.

We can now determine if a cell is a dead-end or not. The next step is to evaluate each cell in the map and check if it’s a dead-end or not. It’s the dead-end cells that we are interested in. I think it would be cool if we could have a function that would return all the dead-end cells in the map for us.

The test to return all the dead-end cells in a map is as follows.

        [Test]

        public void TestCanRetrieveAllDeadEndCellsInMap()

        {

            Generator generator = new Generator();

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

 

            // Loop through each cell and increment counter for each dead end

            int deadEndCellCount1 = 0;

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

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

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

 

            // Loop through each dead end cell location in map

            int deadEndCellCount2 = 0;

            foreach (Point location in map.DeadEndCellLocations)

            {

                // Assert the location is a dead end

                Assert.IsTrue(map[location].IsDeadEnd); 

                deadEndCellCount2++;

            }

 

            // Assert that DeadEndCellLocations returns the same amount of

            // dead-end cell locations as manual process

            Assert.AreEqual(deadEndCellCount1, deadEndCellCount2);

        }

In the above test we first generate our dense maze. We then manually loop through each cell in the maze and check if it’s a dead-end. We keep a counter of how many dead-end cells we found.

We then try to enumerate all the dead-end cell locations in the map. First we test if the cell at the location is really a dead-end and then we increment our second counter. The last step is to compare the two counters to ensure that we had the same dead-end cell count for each process.

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

        public IEnumerable<Point> DeadEndCellLocations

        {

            get

            {

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

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

                        if (this[x, y].IsDeadEnd) yield return new Point(x, y);

            }

        }

In the above code I implemented a property on the map class that returns an IEnumerable of type Point. The code loops through each cell in the map and then yield returns the location if it is a dead-end.

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

Our next task is to remove the dead-end corridor (Cell). A corridor is defined by two adjacent cells not having walls between them. To remove our dead-end cell we need to create a wall at its empty side. Then we need to add a wall on the opposite side of the adjacent cell.

The first thing we need is to determine the direction of the corridor leading out of the dead-end cell. The test to retrieve this direction is as follows.

        [Test]

        public void TestCanGetDeadEndCorridorDirection()

        {

            Cell cell = new Cell();

            cell.NorthSide = SideType.Empty;

            Assert.AreEqual(DirectionType.North, cell.CalculateDeadEndCorridorDirection());

 

            cell = new Cell();

            cell.SouthSide = SideType.Empty;

            Assert.AreEqual(DirectionType.South, cell.CalculateDeadEndCorridorDirection());

 

            cell = new Cell();

            cell.WestSide = SideType.Empty;

            Assert.AreEqual(DirectionType.West, cell.CalculateDeadEndCorridorDirection());

 

            cell = new Cell();

            cell.EastSide = SideType.Empty;

            Assert.AreEqual(DirectionType.East, cell.CalculateDeadEndCorridorDirection());

        }

 

        [Test]

        [ExpectedException(typeof(InvalidOperationException))]

        public void TestInvalidCallOfGetDeadEndCorridorDirection()

        {

            Cell cell = new Cell();

            cell.CalculateDeadEndCorridorDirection();

        }

In the above tests we check that the CalculateDeadEndCorridorDirection method returns the direction of the empty side of our dead-end cell.

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

        public DirectionType CalculateDeadEndCorridorDirection()

        {

            if (!IsDeadEnd) throw new InvalidOperationException();

 

            if (northSide == SideType.Empty) return DirectionType.North;

            if (southSide == SideType.Empty) return DirectionType.South;

            if (westSide == SideType.Empty) return DirectionType.West;

            if (eastSide == SideType.Empty) return DirectionType.East;

 

            throw new InvalidOperationException();

        }

The CalculateDeadEndCorridorDirection method checks each side to determine if it’s empty. The method returns the direction of the first empty side. The method will throw an exception if the cell is not a dead-end cell.

I compile the code and run the tests and they all pass.

Now that we have the direction of the dead-end corridor we need to create a wall in that direction. This task is very similar to the CreateCorridor task we used to actually create the maze. We can reuse the CreateCorridor algorithm by factoring out the SideType being created. Let’s start by refactoring the CreateCorridor method as follows.

        public Point CreateCorridor(Point location, DirectionType direction)

        {

            return CreateSide(location, direction, SideType.Empty);

        }

 

        private Point CreateSide(Point location, DirectionType direction, SideType sideType)

        {

            Point target = GetTargetLocation(location, direction);

 

            switch (direction)

            {

                case DirectionType.North:

                    this[location].NorthSide = sideType;

                    this[target].SouthSide = sideType;

                    break;

                case DirectionType.South:

                    this[location].SouthSide = sideType;

                    this[target].NorthSide = sideType;

                    break;

                case DirectionType.West:

                    this[location].WestSide = sideType;

                    this[target].EastSide = sideType;

                    break;

                case DirectionType.East:

                    this[location].EastSide = sideType;

                    this[target].WestSide = sideType;

                    break;

            }

 

            return target;

        }

In the above code I created a new method called CreateSide. This method is identical to the old CreateCorridor method, but takes as input an additional parameter sideType which is used to specify the SideType that will be created between two adjacent cells.

Next I updated the CreateCorridor method to call the CreateSide method by passing in a SideType of “Empty”. Now we have an easy way of reusing the CreateSide functionality to remove our dead-end cell. Before continuing I rerun the unit tests to make sure I didn’t break anything.

The test to create a wall between two adjacent cells is as follows.

        [Test]

        public void TestCreateWallBetweenAdjacentCells()

        {

            Map map = new Map(10, 10);

            map.MarkCellsUnvisited();

 

            // Loop through each cell and make all the sides empty

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

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

                {

                    map[x, y].NorthSide = SideType.Empty;

                    map[x, y].SouthSide = SideType.Empty;

                    map[x, y].WestSide = SideType.Empty;

                    map[x, y].EastSide = SideType.Empty;

                }

 

            // We now have map with no walls.

            // Test creating walls in each direction

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

 

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

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

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

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

 

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

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

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

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

        }

In the above test I loop through each cell and remove all the walls. The reason for this is that our cells are always initialised with four walls. Next I call the new CreateWall method with a given location and direction and then test each side to make sure the walls are created in the right directions. I have excluded the tests for the other directions in this code listing, but the full test is implemented in the source code.

We now have enough functionality to implement the requirements of step 7 of the algorithm. First I am going to refactor the Generator class and add a CreateDenseMaze method and change the Generate method to call the CreateDenseMaze method. (This encapsulates all the functionality we implemented before step 7 of the algorithm). I rerun the unit tests to make sure the changes didn’t break anything.

The test to implement the requirements of step 7 of the algorithm is as follows.

        [Test]

        public void TestSparsifyMazeRemovesDeadEnds()

        {

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

 

            // Enumerate all the current dead-end locations

            // Add them to a list

            List<Point> deadEndLocations = new List<Point>();

            foreach (Point point in map.DeadEndCellLocations)

                deadEndLocations.Add(point);

 

            Generator.SparsifyMaze(map);

 

            // Enumerate all the new dead-end locations

            // Assert that they aren’t in the original list

            foreach (Point point in map.DeadEndCellLocations)

                Assert.IsFalse(deadEndLocations.Contains(point));

        }

In the above test I generate a dense maze as per our original functionality. I then enumerate all the dead-end locations in the maze and add them to a list. Next I invoke the SparsifyMaze method to remove the current set of dead-ends. I then enumerate all the new dead-end locations and compare them with the original set to ensure that all the original dead-ends were removed.

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

        public static void SparsifyMaze(Map map)

        {

            foreach (Point point in map.DeadEndCellLocations)

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

        }

The actual code to implement step 7 in our generator is quite simple. We enumerate all the dead-end locations and create a wall in the direction of the dead-end corridor.

Next I add the SparsifyMaze method to our Generate method to include it in the main algorithm. I rerun the unit tests to make sure they are all valid. The new Generate method is now as follows.

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

        {

            Map map = new Map(width, height);

            map.MarkCellsUnvisited();

 

            CreateDenseMaze(map, changeDirectionModifier);

            SparsifyMaze(map);

 

            return map;

        }

Below is a screen shot of our maze after incorporating the SparsifyMaze method. I updated the drawing algorithm to draw “rock” cells as black blocks.

exampleoutput1

Conclusion

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

The requirement was to be able to identify all the dead-end corridor cells in the map and to “erase” them. In doing so we would be able to remove corridor cells from the map and create impassible “rock” cells.

These new requirements added functionality to the Cell class to allow us to determine if it is a dead-end or not. We also added a method to determine the direction of the corridor leading out of the dead-end cell.

Next we added a property to the Map class to allow us to enumerate all the dead-end cells in the map. We also refactored our CreateCorridor method into a more generic CreateSide method. We used this new CreateSide method to implement a CreateWall method to allow us to remove the dead-end cells from the map.

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

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.