It’s Alive (almost)

I was able to implement A* pathfinding over the weekend and this opened up a lot of functionality. My A* implementation was based on the following articles.

Path Finding Using A* in C# 3

Amit’s Game Programming – A* Heuristics

I used Eric’s articles for the A* algorithm main loop and data structures and Amit’s article to tweak my movement heuristics.

My first usage of the new pathfinding code was to write a “explorer”. My plan is to use this during dungeon exploration. The player can switch on “Auto Explore” and the explorer code will automatically explore the dungeon on the player’s behalf. It’s almost like running in Angband, but the code will only interrup when a monster or new item is detected.

My explorer uses a simple methodology for exploring the map. Pick the closest unseen tile, find a path to it (using A*) and then navigate there. Repeat until there are no more unseen tiles. This seems to work quite well.

At the moment this exploration algorithm is a bit “dumb” as the closest unseen tile isn’t always the best tile to pick. An improvement would be to give unseen tiles within the current room a higher priority than tiles outside a room (if the player was inside a room). This will cause the explorer to finish exploring rooms before heading out into tunnels.

My next usage of the explorer was to tweak my dungeon generation. As I generate a dungeon I let the explorer try and visit all the “walkable” tiles. If he can’t find a route to a specific unseen tile then the dungeon was generated with inaccessible areas.

My algorithm then switches to “Dig” mode. I find the closest seen tile (to the inaccessible unseen tile), find the path, and navigate to the seen tile. I then change my path finding behaviour to ignore all movement costs for walls (allowing it to move through walls) and to favour up, down, left and right directions over diagonals. A* now finds a path, through walls, to the unseen tile and my explorer now navigates to that tile. Everytime the explorer “bump’s” into a wall it creates a floor tile, forming a tunnel. My dungeons no longer have inaccessible areas.

The abibility to switch, replace or alter movement behaviour is quite important to me. I can now, independent of the type of actor (player, monster, type of monster) change the way it moves on the map. An “ethereal” movement behaviour would allow an actor to move through obstacles, a “digger” movement behaviour would allow the actor to dig tunnels through obstacles.

So far I’m quite happy with the results.

My next step is to implement some simple AI types that will “explore” the dungeon e.g. wandering monsters, follow the player, or guard an area.

Advertisements

Lighting and Dungeon Prefab Techdemo

The purpose of this demo is to show off the dungeon generation that makes use of dynamic and static light sources and custom dungeon prefabs. You can download the binaries at codeplex.

For this release I improved the room and door placement as well as adding the dungeon prefab functionality. I still have situations where the dungeon generator creates unreachable areas. This is due to the way rooms are placed resulting in certain corridors being cut off. I tried to remedy this by
always adding a door to a deadend with a corridor on the opposite side. Its not perfect yet, but I’m happy with 90% of the results.

I haven’t thought of placing lights in a procedural manner and as a shortcut I make use of the prefabs to get them into the dungeons.

The lighting has been adjusted to allow for proper alpha blending of the light values (before I just used an additive blending which resulted in mostly white lights). There is still the problem of tiles being lit by lights from behind walls. I hope to correct this in a future release.

I am still undecided as to whether lights within the dungeon actually add any value.

Enjoy, and as always comments and feedback are welcome.

Dependencies:

This application was developed using .NET 3.5 and is written in C#. I use SDL.NET which runs on top of the Tao.NET framework. Input is handled using SDL and rendering via OpenGL. I use DevIL to do image loading etc.

I have only tested this on Windows XP. And you will need .NET 3.5 to run the application. I have added the SDL dependencies to this release.

I am struggling with getting the application working on OpenSUSE. The error has something todo with DevIL. If anyone is willing to assist. You will need to install Mono 1.9 and SDL.NET. To run the application on mono you will have to use the following script ‘mono RogueLib.Game.exe’

Issues:

I have noticed some rendering issues on my Radeon X1900. Could be driver related. Works fine on all NVidia machines I’ve tested. I didn’t expect to have any issues using OpenGl but I do.

Keys:

Use the direction keypad or numeric keys to navigate the map.
Use spacebar to create a new dungeon.
Use escape to end the demo.

Custom Dungeon Prefabs:

The dungeonprefabs.xml file in the config directory is used to configure custom dungeon prefab rooms.

The layout tag uses a CSV layout to describe the structure. Use 0 for a NULL tile, 1 for a floor, 2 for a wall and 3 for a closed door.

Each dungeon row begins on a new line.

The light sources tag allow you to specify lights within the prefab. You can customize the light colour, radius and the attenuation function. The attenuation parameters are used in the formula 1 / constant + (linear * distance) + (quadratic * distance * distance).

The connectors tags tell the dungeon generator how to place a prefab within the dungeon. The generator will attempt to connect the prefab to a corridor for each connector specified. I haven’t really tested this algorithm for connectors within the prefab. My examples only have connectors on the edges of the prefab.

The prefabs will be placed over any existing dungeon structures. At the time of placement there should only be corridors and the prefabs will be placed adjacent to any corridors.

Dungeon Prefabs are Ready

I always intended to have support for some form of custom rooms in my dungeon generator. The idea is similar to Angband’s vault system, but a lot more generalized. Instead of using custom rooms or prefabs for vault encounters, I wanted to supplement the dungeon generation with custom built rooms or sets of rooms.

These dungeon prefabs required me to implement a file format in XML that would represent the prefab structure. My schema allows me to set up the layout, specify light sources, and connectors.

The function of the connectors tag is to give the dungeon generation algorithm some guidance in placing the prefab within the dungeon. The algorithm will try to place a prefab with each connector located next to a corridor within the dungeon. Locations with no connected connectors are rejected.

The added benefit of the prefab implementation is that I now have serialization for most of my dungeon data. This means that I can easily save a generated dungeon which will be useful for save files in the future.

I hacked the prefab generation into my existing dungeon generation code, but it soon became a mess. This led me to revisit the room and door generation code.

The room and door generation code now has a nice set of unit tests. The algorithms for each are also a bit more purposeful in terms of placing rooms and creating doors in an intelligent manner.

I am not 100% happy with it yet, but its a substantial improvement. I will need to implement some form of maze (or dungeon) solving algorithm to make it smarter.

There are still a few issues with the lighting system, but I want to implement some new functionality before I continue tweaking. It’s really boring running around dungeons without any monsters.

I hope to have a new tech-demo ready for download in the next few days. I am just doing some Linux testing before I upload.

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.