Procedural Level Generation in Games using a Cellular Automaton: Part 1

Identifying Caverns

Recursive flood-fill with four directions

Recursive flood-fill with four directions

Once you identify individual caverns, you can then either connect or remove them all, except the largest cavern. You'll be doing both in this tutorial.

The best way to identify the caverns in the cave is to apply a flood fill algorithm that can determine the area connected to a given cell in a grid.

Have you ever used a flood fills in paint programs like Photoshop to fill areas with a different color? It works just as well on caves. :]

First, add the following private property to the class extension in Cave.m:

@property (strong, nonatomic) NSMutableArray *caverns;

This allows easy access to information about the caverns later.

To perform the flood fill, you need two new methods in Cave.m:

• One that creates a copy of the current grid. From this, you'll loop over every floor cell. For each one you'll recursively test each floor cell in its von Neumann neighborhood.
• Another you'll call recursively to test cells in the von Neumann neighborhood of a cell. This will also change each tested cell's type to a fill value.

Tackle the recursive method first. Add this method to Cave.m:

- (void)floodFillCavern:(NSMutableArray *)array fromCoordinate:(CGPoint)coordinate
    fillNumber:(NSInteger)fillNumber
{
  // 1
  CaveCell *cell = (CaveCell *)array[(NSUInteger)coordinate.y][(NSUInteger)coordinate.x];
  
  // 2
  if (cell.type != CaveCellTypeFloor) {
    return;
  }
  
  // 3
  cell.type = fillNumber;
  
  // 4
  [[self.caverns lastObject] addObject:cell];
  
  // 5
  if (coordinate.x > 0) {
    [self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x - 1, coordinate.y)
      fillNumber:fillNumber];
  }
  if (coordinate.x < self.gridSize.width - 1) {
    [self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x + 1, coordinate.y)
      fillNumber:fillNumber];
  }
  if (coordinate.y > 0) {
    [self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x, coordinate.y - 1)
      fillNumber:fillNumber];
  }
  if (coordinate.y < self.gridSize.height - 1) {
    [self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x, coordinate.y + 1)
      fillNumber:fillNumber];
  }
}

The intent of this method is to be recursive. As you can see, it calls itself several times. Here's a play-by-play of what it does:

1. Use the grid coordinate passed to the method to get the CaveCell to test.
2. If the cell you're testing isn't a floor cell, the method simply returns. When dealing with recursive methods, you always need some condition like this that will eventually stop the recursion, otherwise you'll crash with an infinite loop.
3. You change the cell's type to the fillNumber that passed to the method. Each cavern will have a unique fill number, and this is how you'll tell caverns apart later. It also ensures the cell is never tested again because it will no longer be considered a floor cell. This is the reason you're performing the flood fill on a copy of the cave grid.
4. The cell gets added to the last array in the list of caverns. The lastObject of the caverns array will be the current cavern where you're performing the flood fill.
5. Perform a recursive test for each cell in the von Neumann neighborhood. The test runs in the order west, east, north and south. Performance-wise, this is the smartest way since the flood fill goes from top to bottom.

Still in Cave.m, add the second required method:

- (void)identifyCaverns
{
  // 1
  self.caverns = [NSMutableArray array];
  
  // 2
  NSMutableArray *floodFillArray = [NSMutableArray arrayWithCapacity:(NSUInteger)self.gridSize.height];
  
  for (NSUInteger y = 0; y < self.gridSize.height; y++) {
    NSMutableArray *floodFillArrayRow = [NSMutableArray arrayWithCapacity:(NSUInteger)self.gridSize.width];
    
    for (NSUInteger x = 0; x < self.gridSize.width; x++) {
      CaveCell *cellToCopy = (CaveCell *)self.grid[y][x];
      CaveCell *copiedCell = [[CaveCell alloc] initWithCoordinate:cellToCopy.coordinate];
      copiedCell.type = cellToCopy.type;
      [floodFillArrayRow addObject:copiedCell];
    }
    
    [floodFillArray addObject:floodFillArrayRow];
  }
  
  // 3
  NSInteger fillNumber = CaveCellTypeMax;
  for (NSUInteger y = 0; y < self.gridSize.height; y++) {
    for (NSUInteger x = 0; x < self.gridSize.width; x++) {
      if (((CaveCell *)floodFillArray[y][x]).type == CaveCellTypeFloor) {
        [self.caverns addObject:[NSMutableArray array]];
        [self floodFillCavern:floodFillArray fromCoordinate:CGPointMake(x, y) fillNumber:fillNumber];
        fillNumber++;
      }
    }
  }
  
  NSLog(@"Number of caverns in cave: %lu", (unsigned long)[self.caverns count]);
}

Now here's a step-by-step :

1. Create an instance of a new mutable array for the caverns in the cave. Each cavern will be a mutable array of CaveCells.
2. Create a deep copy of the cave grid. Since the flood fill will change the type of the cell, you'll need to work on a copy of the grid rather than the grid itself.
3. Perform the flood fill by looping through each cell in the copy of the grid. If the cell is a floor tile, it means the cell has not been tested already, so a new cavern starts and the flood fill starts from the current cell.

Now, add the following line to generateWithSeed:, right before the [self generateTiles]; line:

[self identifyCaverns];

Build and run. In the console, you should be able to see 22 tidy little caverns, for a cave generated with a seed of 0.

You now know all the caverns in the cave and you're left with a few choices with increasing difficulty:

1. You can keep the cave as-is. If you work with destructible terrain, the player will be able to break, blast and bore through the walls to access the unconnected areas.
2. You can remove all the unconnected caverns by filling all but the largest cavern with wall cells. The advantage is that the organic look of the cave remains while ensuring the knight can reach all parts of the cave. The downside is that you lose some playable area.
3. You can connect the unconnected caverns to the largest of the caverns. The advantage is that you keep all the walkable areas of the original cave. The downside is that the connections between the caverns will be straight lines, which just doesn't flatter organic look of a cave.

In this tutorial, you'll learn how to do options two and three. No matter which option you choose for the game, you'll need to know which cavern is the largest, so you know where to put the entry and exit.

All you have to do is count the number of CaveCell instances in each cavern array in the caverns. So, add the following method to Cave.m to do the counting:

- (NSInteger)mainCavernIndex
{
  NSInteger mainCavernIndex = -1;
  NSUInteger maxCavernSize = 0;
  
  for (NSUInteger i = 0; i < [self.caverns count]; i++) {
    NSArray *caveCells = (NSArray *)self.caverns[i];
    NSUInteger caveCellsCount = [caveCells count];
    
    if (caveCellsCount > maxCavernSize) {
      maxCavernSize = caveCellsCount;
      mainCavernIndex = i;
    }
  }
  
  return mainCavernIndex;
}

This method will simply loop through each array in caverns, checking which has the most instances of CaveCell. It returns an index that identifies the largest cavern, and henceforth shall be known as the 'main cavern'.