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

Welcome back to our 2-part tutorial series on procedural level generation in games using a cellular automaton. In other words, how to make cool caves! :]

In the first part of the series, you learned how to use a cellular automaton similar to Conway’s Game of Life to transform random tiles into a cave system, and remove unconnected caves.

In this second and final part of the series, you’ll learn how to connect unconnected caverns, place an exit and entrance into the cavern, add collision detection – and yes, there will be treasure.

This tutorial will pick up where you left things off in the previous tutorial. If you don’t have it already, here is the example project where you left things off last time.

Connecting Unconnected Caverns

In the previous tutorial, you solved the problem of unconnected caverns by simply removing all unconnected caverns. But you have another option: connect the unconnected caverns to the main cavern.

To do this, you will use A* path-finding to find a path from a random point in the unconnected cavern to a random point in the main cavern. This will also convert all cells in the path to floor cells.

Note: If you’re new to A* path-finding, it might help you to skim through our A* path-finding tutorial to get familiar with the theory behind it.

As a refresher, here’s a quick crash course of the algorithm.

Movement costs

During the algorithm, you will be calculating a movement cost F = G + H where:

Lists

During the algorithm, you will need two lists:

The algorithm

And here is the algorithm itself:

Demo

Finally, here is an animated GIF demoing the algorithm:

Key for lists (colors of tile borders): Open list green, Closed list red, final shortest path blue.

Key for movement costs (numbers on each tile): G score lower left, H score lower right, and F score upper left.

Again, for a full walkthrough check out our A* path-finding tutorial.

• G = The movement cost from the start space to this tile (i.e. how many tiles the hero needs to walk to get to that square).
• H = The estimated cost to get from the tile to the target tile. Again, this is an estimate only; you can think of H as heuristic, like the “city block” estimate.

• Open list: Tiles currently under consideration
• Closed list: Tiles already considered

1. Get the tile on the open list, with the lowest F score. Call this S.
2. Remove S from the open list, and add it to the closed list.
3. For each square T in S‘s walkable adjacent tiles:
   1. If T is in the closed list: Ignore it.
   2. If T is not in the open list: Add it and compute its score.
   3. If T is already in the open list: Check if the F score is lower when we use the current generated path to get there. If it is, update its score and update its parent as well.
4. When the target square is in the open list, add it to the closed list. Then you can walk backwards from the target square to the open list to get the shortest path.

1. If T is in the closed list: Ignore it.
2. If T is not in the open list: Add it and compute its score.
3. If T is already in the open list: Check if the F score is lower when we use the current generated path to get there. If it is, update its score and update its parent as well.

You’ll use a slightly modified version of the algorithm from our our A* path-finding tutorial to find the shortest, most inexpensive path between the two points. For the A* heuristic function, wall cells will earn a higher value than floor cells. Doing this will allow the A* path-finding to dig through walls, as a last resort.

First, you’ll create an exact copy of the ShortestPathStep class from our A* path-finding tutorial.

• Go to File\New\File…
• Choose iOS\Cocoa Touch\Objective-C class, and click Next
• Name the class ShortestPathStep
• Make it a subclass of NSObject, click Next and then Create.

Paste the following code into ShortestPathStep.h between @interface and @end:

@property (assign, nonatomic) CGPoint position;
@property (assign, nonatomic) NSInteger gScore;
@property (assign, nonatomic) NSInteger hScore;
@property (strong, nonatomic) ShortestPathStep *parent;

- (instancetype)initWithPosition:(CGPoint)pos;
- (NSInteger)fScore;

Then paste the following code into ShortestPathStep.m between @implementation and @end:

- (instancetype)initWithPosition:(CGPoint)pos
{
  if ((self = [super init])) {
    _position = pos;
  }
  return self;
}

- (NSString *)description
{
  return [NSString stringWithFormat:@"%@  pos=%@  g=%ld  h=%ld  f=%ld", [super description],
    NSStringFromCGPoint(self.position), (long)self.gScore, (long)self.hScore, (long)[self fScore]];
}

- (BOOL)isEqual:(ShortestPathStep *)other
{
  return CGPointEqualToPoint(self.position, other.position);
}

- (NSInteger)fScore
{
  return self.gScore + self.hScore;
}

There are no modifications to this class from the original A* path-finding tutorial.

Import the ShortestPathStep header in Cave.m:

#import "ShortestPathStep.h"

To initiate the path-finding, you need a method to get a set of random coordinates from the main cavern and each of the unconnected caverns.

Still in Cave.m, insert the following method:

- (void)connectToMainCavern
{
  NSUInteger mainCavernIndex = [self mainCavernIndex];
  
  NSArray *mainCavern = (NSArray *)self.caverns[mainCavernIndex];
  
  for (NSUInteger cavernIndex = 0; cavernIndex < [self.caverns count]; cavernIndex++) {
    if (cavernIndex != mainCavernIndex) {
      NSArray *originCavern = self.caverns[cavernIndex];
      CaveCell *originCell = (CaveCell *)originCavern[arc4random() % [originCavern count]];
      CaveCell *destinationCell = (CaveCell *)mainCavern[arc4random() % [mainCavern count]];
      [self createPathBetweenOrigin:originCell destination:destinationCell];
    }
  }
}

First, this method gets the main cavern index and array. Then it loops through the remaining caverns and selects a random cell inside both the smaller cavern and the main cavern. The originCell (from a disconnected cavern) and destinationCell (from the main cavern) are passed as parameters to createPathBetweenOrigin:destination:. You'll be implementing this method soon, so do not worry about the compiler error for now.

Before implementing createPathBetweenOrigin:destination:, you'll need a few helper methods:

1. A method to insert a ShortestPathStep into the open list at the appropriate position (ordered by F score).
2. A method to compute the movement cost between adjacent cells..
3. A method to compute the H score for a cell.

Paste the following three methods in Cave.m:

// Added inList parameter as this implementation does not use properties to store
// open and closed lists.
- (void)insertStep:(ShortestPathStep *)step inList:(NSMutableArray *)list
{
  NSInteger stepFScore = [step fScore];
  NSInteger count = [list count];
  NSInteger i = 0;
  
  for (; i < count; i++) {
    if (stepFScore <= [[list objectAtIndex:i] fScore]) {
      break;
    }
  }
  
  [list insertObject:step atIndex:i];
}

- (NSInteger)costToMoveFromStep:(ShortestPathStep *)fromStep toAdjacentStep:(ShortestPathStep *)toStep
{
  // Always returns one, as it is equally expensive to move either up, down, left or right.
  return 1;
}

- (NSInteger)computeHScoreFromCoordinate:(CGPoint)fromCoordinate toCoordinate:(CGPoint)toCoordinate
{
  // Get the cell at the toCoordinate to calculate the hScore
  CaveCell *cell = [self caveCellFromGridCoordinate:toCoordinate];
  
  // It is 10 times more expensive to move through wall cells than floor cells.
  NSUInteger multiplier = cell.type = CaveCellTypeWall ? 10 : 1;
  
  return multiplier * (abs(toCoordinate.x - fromCoordinate.x) + abs(toCoordinate.y - fromCoordinate.y));
}

The inline comments in the above methods explain where these methods differ from the original Cocos2D tutorial in good detail, so be sure to read them through.

Next, create a method to get all cell coordinates in the von Neumann neighborhood of a specific coordinate:

- (NSArray *)adjacentCellsCoordinateForCellCoordinate:(CGPoint)cellCoordinate
{
  NSMutableArray *tmp = [NSMutableArray arrayWithCapacity:4];
  
  // Top
  CGPoint p = CGPointMake(cellCoordinate.x, cellCoordinate.y - 1);
  if ([self isValidGridCoordinate:p]) {
    [tmp addObject:[NSValue valueWithCGPoint:p]];
  }
  
  // Left
  p = CGPointMake(cellCoordinate.x - 1, cellCoordinate.y);
  if ([self isValidGridCoordinate:p]) {
    [tmp addObject:[NSValue valueWithCGPoint:p]];
  }
  
  // Bottom
  p = CGPointMake(cellCoordinate.x, cellCoordinate.y + 1);
  if ([self isValidGridCoordinate:p]) {
    [tmp addObject:[NSValue valueWithCGPoint:p]];
  }
  
  // Right
  p = CGPointMake(cellCoordinate.x + 1, cellCoordinate.y);
  if ([self isValidGridCoordinate:p]) {
    [tmp addObject:[NSValue valueWithCGPoint:p]];
  }
  
  return [NSArray arrayWithArray:tmp];
}

This method gets all valid adjacent cell coordinates for the four possible cells in the von Neumann neighborhood and returns them as coordinates in an array. Unlike the original code, it returns all valid grid coordinates as it is possible to move over walls and floors alike.

Now that all the helper methods are in place, add the following code to Cave.m:

- (void)createPathBetweenOrigin:(CaveCell *)originCell destination:(CaveCell *)destinationCell
{
  NSMutableArray *openSteps = [NSMutableArray array];
  NSMutableArray *closedSteps = [NSMutableArray array];
  
  [self insertStep:[[ShortestPathStep alloc] initWithPosition:originCell.coordinate] inList:openSteps];
  
  do {
    // Get the lowest F cost step.
    // Because the list is ordered, the first step is always the one with the lowest F cost.
    ShortestPathStep *currentStep = [openSteps firstObject];
    
    // Add the current step to the closed list
    [closedSteps addObject:currentStep];
    
    // Remove it from the open list
    [openSteps removeObjectAtIndex:0];
    
    // If the currentStep is the desired cell coordinate, we are done!
    if (CGPointEqualToPoint(currentStep.position, destinationCell.coordinate)) {
      // Turn the path into floors to connect the caverns
      do {
        if (currentStep.parent != nil) {
          CaveCell *cell = [self caveCellFromGridCoordinate:currentStep.position];
          cell.type = CaveCellTypeFloor;
        }
        currentStep = currentStep.parent; // Go backwards
      } while (currentStep != nil);
      break;
    }
    
    // Get the adjacent cell coordinates of the current step
    NSArray *adjSteps = [self adjacentCellsCoordinateForCellCoordinate:currentStep.position];
    
    for (NSValue *v in adjSteps) {
      ShortestPathStep *step = [[ShortestPathStep alloc] initWithPosition:[v CGPointValue]];
      
      // Check if the step isn't already in the closed set
      if ([closedSteps containsObject:step]) {
        continue; // ignore it
      }
      
      // Compute the cost form the current step to that step
      NSInteger moveCost = [self costToMoveFromStep:currentStep toAdjacentStep:step];
      
      // Check if the step is already in the open list
      NSUInteger index = [openSteps indexOfObject:step];
      
      if (index == NSNotFound) { // Not on the open list, so add it
        
        // Set the current step as the parent
        step.parent = currentStep;
        
        // The G score is equal to the parent G score plus the cost to move from the parent to it
        step.gScore = currentStep.gScore + moveCost;
        
        // Compute the H score, which is the estimated move cost to move from that step
        // to the desired cell coordinate
        step.hScore = [self computeHScoreFromCoordinate:step.position
          toCoordinate:destinationCell.coordinate];
        
        // Adding it with the function which is preserving the list ordered by F score
        [self insertStep:step inList:openSteps];
        
      } else { // Already in the open list
        
        // To retrieve the old one, which has its scores already computed
        step = [openSteps objectAtIndex:index];
        
        // Check to see if the G score for that step is lower if we use the current step to get there
        if ((currentStep.gScore + moveCost) < step.gScore) {
          
          // The G score is equal to the parent G score plus the cost to move the parent to it
          step.gScore = currentStep.gScore + moveCost;
          
          // Because the G score has changed, the F score may have changed too.
          // So to keep the open list ordered we have to remove the step, and re-insert it with
          // the insert function, which is preserving the list ordered by F score.
          ShortestPathStep *preservedStep = [[ShortestPathStep alloc] initWithPosition:step.position];
          
          // Remove the step from the open list
          [openSteps removeObjectAtIndex:index];
          
          // Re-insert the step to the open list
          [self insertStep:preservedStep inList:openSteps];
        }
      }
    }
    
  } while ([openSteps count] > 0);
}

- (void)constructPathFromStep:(ShortestPathStep *)step
{
  do {
    if (step.parent != nil) {
      CaveCell *cell = [self caveCellFromGridCoordinate:step.position];
      cell.type = CaveCellTypeFloor;
    }
    step = step.parent; // Go backwards
  } while (step != nil);
}

This is the meat and bones of the A* path-finding algorithm. The implementation of this method is very much like how it is in the original tutorial, except for a few adaptations. Read the comments or go through the original tutorial to understand how it works.

Have you read and understood the code? Good, time to put all this path-finding to good use. :]

Now you've taken time to create two ways to construct one big connected cave. Why not make the Cave class customizable so you can choose one or the other?

Start by adding a new public property to Cave.h:

@property (assign, nonatomic) BOOL connectedCave;

If this property is set to YES, then the app will use A* path-finding. Otherwise, it removes the disconnected caves. By default, a cave with all disconnected caves removed will generate, as this property will have the default value NO.

Inside Cave.m, locate the following line in generateWithSeed::

[self removeDisconnectedCaverns];

and replace it with this code:

if (self.connectedCave) {
  [self connectToMainCavern];
} else {
  [self removeDisconnectedCaverns];
}

This code checks the value of the connectedCave property to determine if disconnected caverns should be removed or connected.

If you run the code now, it will remove all disconnected caverns. Since you just set it up to connect all parts of the cave, you probably want to see it in action, right?

Open MyScene.m and add the following line of code to initWithSize: just before the line that calls generateWithSeed: on _cave:

_cave.connectedCave = YES;

Build and run. Now you should see connections between all caverns, as shown in these before and after images:

Now you can see that A* path-finding adds a lot of straight-lined corridors. You need to decide if you can live with awkward precision or if you'd prefer to remove the disconnected caverns.

Tip: You can make the A* path-finding less destructive to the cave by selecting a cell from the main cavern that is closer to the disconnected cave. As it stands now, the method chooses a random cell in the main cavern, and it might be very far away from the cave to be connected.