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

Placing an Entrance and an Exit

Now you have a knight and a cave. Spelunking might be a nice pastime for modern adventurer, but a meaningless activity for your knight.

If you were to drop somebody in the middle of a cave, their immediate goal is to find a way out. In the next phase, you'll start by adding an entry to drop the knight in the cave and an exit for him to find.

Placing the starting point is straightforward. You'll find a random floor cell within the cave and make that cell an entrance cell.

The exit is a bit trickier as you don't want it to be too close to the entrance. The strategy you'll use is to find another random cell, then calculate the distance between it and the entrance.

If the distance is larger than or equal to your desired distance, then the randomly selected cell becomes an exit cell. Otherwise, the method selects another random cell and repeats the process.

Start by adding three new public properties to Cave.h:

@property (assign, nonatomic, readonly) CGPoint entrance;
@property (assign, nonatomic, readonly) CGPoint exit;
@property (assign, nonatomic) CGFloat minDistanceBetweenEntryAndExit;

The entrance and exit properties give you the coordinates of the entrance and exit in the level, respectively. They are pixel coordinates for the center of these two cells. Later, it will make it easier for you to position the player sprite node.

The minDistanceBetweenEntryAndExit property can be set to the minimum allowed distance between the entry and exit. This distance will be calculated using the Pythagorean theorem. The lower the value, the closer the exit can be to the entrance.

You'll want to default the property values for these new properties. Open Cave.m and add the following lines of code to initWithAtlasNamed:gridSize: after the line that initializes _numberOfTransitionSteps:

_entrance = CGPointZero;
_exit = CGPointZero;
_minDistanceBetweenEntryAndExit = 32.0f;

The entrance and exit properties default to CGPointZero since these will be set later during dungeon creation, and minDistanceBetweenEntryAndExit defaults to 32.0f, as this gives a nice distance between the entrance and exit.

The value for minDistanceBetweenEntryAndExit needs to be set before you create a cave, as the number is relative to the cave's grid size.

You also need to be able to set a cell's type as an entrance or an exit. To do that, add the following types to the CaveCellType enumeration in CaveCell.h, between CaveCellTypeFloor and CaveCellTypeMax:

CaveCellTypeEntry,
CaveCellTypeExit,

Next, add the following method to Cave.m:

- (void)placeEntranceAndExit
{
  // 1
  NSUInteger mainCavernIndex = [self mainCavernIndex];
  NSArray *mainCavern = (NSArray *)self.caverns[mainCavernIndex];
  
  // 2
  NSUInteger mainCavernCount = [mainCavern count];
  CaveCell *entranceCell = (CaveCell *)mainCavern[arc4random() % mainCavernCount];
  
  // 3
  [self caveCellFromGridCoordinate:entranceCell.coordinate].type = CaveCellTypeEntry;
  _entrance = [self positionForGridCoordinate:entranceCell.coordinate];
  
  CaveCell *exitCell = nil;
  CGFloat distance = 0.0f;
  
  do
  {
    // 4
    exitCell = (CaveCell *)mainCavern[arc4random() % mainCavernCount];
    
    // 5
    NSInteger a = (exitCell.coordinate.x - entranceCell.coordinate.x);
    NSInteger b = (exitCell.coordinate.y - entranceCell.coordinate.y);
    distance = sqrtf(a * a + b * b);
    
    NSLog(@"Distance: %f", distance);
  }
  while (distance < self.minDistanceBetweenEntryAndExit);
  
  // 6
  [self caveCellFromGridCoordinate:exitCell.coordinate].type = CaveCellTypeExit;
  _exit = [self positionForGridCoordinate:exitCell.coordinate];
}

There is a lot going on in this method, so let's go through it step-by-step:

1. First, you select the main cavern array, as this is where you place the entrance and exit.
2. Select a random cell within the main cavern. Remember that caverns only contain floor cells so there is no risk of placing the entrance atop a wall cell.
3. Convert the random cell to an entrance cell and set the entrance property coordinates for that cell.
4. Next, select another random cell in the main cavern for the exit. It might end up being the same cell you just chose, but the following check will take care of that.
5. Based on the grid coordinates of entranceCell and exitCell, the distance between these two coordinates is calculated using the Pythagorean theorem. If the distance is less than the value of minDistanceBetweenEntryAndExit, then it loops back to select a new random cell.
6. Convert exitCell into an exit cell and set the exit property coordinates for the exit cell.

If you're a bit rusty on basic trigonometry, the following image describes how to calculate the distance between two points using the Pythagorean theorem:

The distance between two points (the hypotenuse) is the square root of adding the horizontal distance (a) squared and the vertical distance (b) squared.

To learn more about the Pythagorean theorem, work through the Trigonometry for Game Programming tutorial on this site.

Note: You can speed up these sorts of checks by removing the call to sqrt. To do that you just need to store minDistanceBetweenEntryAndExit as the squared distance rather than the actual distance.

If you really need to know the true distance between the entrance and the exit, you couldn't do this trick, but in cases like this where you're simply comparing against a known distance, it works just fine.

Place the entrance and exit at the time you generate the cave for best results. Inside Cave.m, add the following code to generateWithSeed: just before the line that calls generateTiles:

[self identifyCaverns];
[self placeEntranceAndExit];

This simply re-runs the flood fill algorithm and places the entrance and exit. Here's a mini-challenge: Why run the flood fill algorithm a second time?

[spoiler title="Solution"]Without running the flood fill algorithm on the cave a second time, the caverns property would contain the state of the caverns before you remove or connect caverns. Therefore, the placement of the entrance and exit would never be in areas that are outside of the original main cavern.[/spoiler]

Good job! Your cave now has an entrance and an exit. Now you need to make them visible to the player. This requires an update to generateTiles in Cave.m. Add the following two cases to the switch statement:

case CaveCellTypeEntry:
  node = [SKSpriteNode spriteNodeWithTexture:[self.atlas textureNamed:@"tile4_0"]];
  break;
	
case CaveCellTypeExit:
  node = [SKSpriteNode spriteNodeWithTexture:[self.atlas textureNamed:@"tile3_0"]];
  break;

These cases simply create sprite nodes with either an entrance texture (stairs up) or an exit texture (stairs down), depending on what's appropriate for the cell type.

Now you need to make sure the knight starts at the entrance of the cave, so open MyScene.m and change the line that initializes self.player.desiredPosition in initWithSize: so it looks like this:

_player.desiredPosition = _cave.entrance;

Build and run, and you'll see the knight standing at the entrance, ready to find the exit. Spend a short while walking around the cave to see if you can find the exit.

Did you find the exit yet?

NSLog(@"Entrance is at: %@", NSStringFromCGPoint(entranceCell.coordinate));
NSLog(@"Exit is at: %@", NSStringFromCGPoint(exitCell.coordinate));

NSLog(@"Entrance is at: %@", NSStringFromCGPoint(entranceCell.coordinate));
NSLog(@"Exit is at: %@", NSStringFromCGPoint(exitCell.coordinate));