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

Growing the cave

The next step you take is to apply the transition rules of the cellular automaton. Remember the rules that governed the cells in Conway's Game of Life? The transition rules are applied to all cells simultaneously thereby changing the state of the cells based on their neighborhood.

Exactly the same approach will grow the cave. You'll create a method that iterates each cell in the grid, and applies the transition rules to decide whether the cell will be a wall or a floor.

The below figure illustrates how applying the transition rules will impact cave generation:

The first thing you do is define the transition rules. In this tutorial, you apply these rules:

1. If a cell is a wall and less than 3 cells in the Moore neighborhood are walls, the cell changes state to a floor.
2. If a cell is a floor and greater than 4 cells in the Moore neighborhood are walls, the cell changes state to a wall.
3. Otherwise, the cell remains in its current state.

To make the cave generation as flexible as possible, add these two new properties to Cave.h:

@property (assign, nonatomic) NSUInteger floorsToWallConversion;
@property (assign, nonatomic) NSUInteger wallsToFloorConversion;

These properties allow you to set the number of floors or walls that mark the thresholds for the transition rules described earlier. You need to give them a default value, so open Cave.m and add the following code to initWithAtlasNamed:gridSize:, just after the line that initializes _chanceToBecomeWall:

_floorsToWallConversion = 4;
_wallsToFloorConversion = 3;

The default values are the result of trial-and-error and known to give good results. But don't take my word for it, play around with these property values to see how they affect the cave generation.

Your last step before applying transition rules is to create a method to count the number of walls in the Moore neighborhood of a cell. Do you remember how many cells are in the Moore neighborhood?

[spoiler title="Solution"]There are eight cells in the Moore neighborhood. See the illustration below for further details.

[/spoiler]

Add the following method to Cave.m:

- (NSUInteger)countWallMooreNeighborsFromGridCoordinate:(CGPoint)coordinate
{
  NSUInteger wallCount = 0;
  
  for (NSInteger i = -1; i < 2; i++) {
    for (NSInteger j = -1; j < 2; j++) {
      // The middle point is the same as the passed Grid Coordinate, so skip it
      if ( i == 0 && j == 0 ) {
        break;
      }
      
      CGPoint neighborCoordinate = CGPointMake(coordinate.x + i, coordinate.y + j);
      if (![self isValidGridCoordinate:neighborCoordinate]) {
        wallCount += 1;
      } else if ([self caveCellFromGridCoordinate:neighborCoordinate].type == CaveCellTypeWall) {
        wallCount += 1;
      }
    }
  }
  return wallCount;
}

The for loops might look a bit weird at first, but there is a method to the madness. The idea is to count the number of wall cells around the grid coordinates (x, y).

If you look at the illustration below, you can see coordinates for neighbors are one less, equal to, and one greater than the original coordinate. Your two for loops give you just that, starting at -1 and looping through +1.

You might have noticed the code counts invalid grid coordinates (for instance, coordinates that are off the edge of the grid) as walls. This will help fill in the edges of the cave, but it is a matter of preference if you want to do this. You can experiment by not doing it, if you like.

Add this method to Cave.m to perform a transition step to all the cells in the grid:

- (void)doTransitionStep
{
  // 1
  NSMutableArray *newGrid = [NSMutableArray arrayWithCapacity:(NSUInteger)self.gridSize.height];
  
  // 2
  for (NSUInteger y = 0; y < self.gridSize.height; y++) {
    NSMutableArray *newRow = [NSMutableArray arrayWithCapacity:(NSUInteger)self.gridSize.width];
    for (NSUInteger x = 0; x < self.gridSize.width; x++) {
      CGPoint coordinate = CGPointMake(x, y);
      
      // 3
      NSUInteger mooreNeighborWallCount = [self countWallMooreNeighborsFromGridCoordinate:coordinate];
      
      // 4
      CaveCell *oldCell = [self caveCellFromGridCoordinate:coordinate];
      CaveCell *newCell = [[CaveCell alloc] initWithCoordinate:coordinate];
      
      // 5
      // 5a
      if (oldCell.type == CaveCellTypeWall) {
        newCell.type = (mooreNeighborWallCount < self.wallsToFloorConversion) ?
          CaveCellTypeFloor : CaveCellTypeWall;
      } else {
        // 5b
        newCell.type = (mooreNeighborWallCount > self.floorsToWallConversion) ?
          CaveCellTypeWall : CaveCellTypeFloor;
      }
      [newRow addObject:newCell];
    }
    [newGrid addObject:newRow];
  }
  
  // 6
  self.grid = newGrid;
}

Let's go over this section-by-section:

1. Create a new grid that will be the state of the grid after the transition step has been performed. To understand why this is needed, remember that to calculate the new value of a cell in the grid, you need to look at the eight neighbors in the Moore neighborhood. If you already calculated the new value of some of the cells and put them back in the grid, then the calculation will be a mix of new and old data.
2. Iterate through all the cells in the grid. You use two for loops for this purpose.
3. For each cell, you use the countWallMooreNeighborsFromGridCoordinate: method you added earlier to calculate the number of walls in the Moore neighborhood.
4. A copy (newCell) of the current cell (oldCell) is made for the reason stated in section 1.
5. The transition rules apply to the cell. Based on the cell type (wall or floor), it checks the number of wall cells in the Moore neighborhood against the limits for changing the cell.

• 5a: If the cell is a wall and mooreNeighborWallCount is less than the value of wallsToFloorConversion, then the wall changes to a floor (transition rule 1). Otherwise, it remains a wall (transition rule 3).
• 5b: If the cell is a floor and the MooreNeighborWallCount is greater than the value of the floorsToWallConversion, then the floor changes to a wall (transition rule 2). Otherwise, it remains a floor (transition rule 3).

Now you've almost implemented the transition step of the cellular automaton. The only thing missing is actually performing the transition step or steps when you generate the cave.

To be flexible, add another property to add the ability to set how many transition steps perform when the cave generates. Open Cave.h and add the following property:

@property (assign, nonatomic) NSUInteger numberOfTransitionSteps;

Experimentation revealed that using two transitions steps works well. Initialize the property by adding this to initWithAtlasNamed:gridSize: in Cave.m, just after the line that initializes _wallsToFloorConversion:

_numberOfTransitionSteps = 2;

Still in Cave.m, add the following for loop to generateWithSeed: between the lines [self initializeGrid]; and [self generateTiles];:

for (NSUInteger step = 0; step < self.numberOfTransitionSteps; step++) {
  NSLog(@"Performing transition step %lu", (unsigned long)step + 1);
  [self doTransitionStep];
}

This simply runs the desired number of transition steps by calling doTransitionStep at each iteration of the loop.

Now you've implemented the cellular automaton fully. Build and run to see how the transition steps affect cave generation.

At this point, you have a nice, realistic looking cave, but did you notice there are unreachable caverns? In the above image, green highlights indicate where the unreachable areas lie.

Since the knight has no holy hand grenades, this leaves the player in a bad way, so you'll need to fix that. Or, maybe you could make that an In-App Purchase. ;]