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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s