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

Kim Pedersen

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:

• 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.

Lists

During the algorithm, you will need two lists:

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

The algorithm

And here is the algorithm itself:

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.

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.

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];
}

{
// 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]) {
}

// Left
p = CGPointMake(cellCoordinate.x - 1, cellCoordinate.y);
if ([self isValidGridCoordinate:p]) {
}

// Bottom
p = CGPointMake(cellCoordinate.x, cellCoordinate.y + 1);
if ([self isValidGridCoordinate:p]) {
}

// Right
p = CGPointMake(cellCoordinate.x + 1, cellCoordinate.y);
if ([self isValidGridCoordinate: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

// 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

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.

## 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?

Solution Inside: Solution SelectShow

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?

Tip: You can determine the direction to head to find the exit by inserting the following code at the end of `placeEntranceAndExit` in Cave.m -- just remember that origin (x = 0, y = 0) is at bottom-left:

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

## Treasure

No knight is going to be thrilled about trudging through an unfamiliar cave without potential for some kind of reward. Treasure will help keep him motivated and coming back for more.

Placing treasure can be as easy as randomly selecting a floor cell and placing a gold-filled chest there. But that might make it far too easy for the knight. You'll apply a different approach that will put treasure in less obvious places.

You've already created a method to count how many walls surround a cell. By looping over all the cells in the finished cave system, you can determine how many walls surround each cell. Cells surrounded by several walls are often at the end of a corridor or in an isolated area; the perfect place to hide treasure.

First, you'll add a new cell type to allow you to mark cells that contain treasure easily. Open CaveCell.h and add the following type to the `CaveCellType` enumeration, just above `CaveCellTypeMax`:

```CaveCellTypeTreasure,
```

You'll use this new type for any cell that contains treasure.

Add the following method to Cave.m:

```- (void)placeTreasure
{
NSUInteger treasureHiddenLimit = 4;

for (NSUInteger y = 0; y < self.gridSize.height; y++) {
for (NSUInteger x = 0; x < self.gridSize.width; x++) {
CaveCell *cell = (CaveCell *)self.grid[y][x];

if (cell.type == CaveCellTypeFloor) {
NSUInteger mooreNeighborWallCount =
[self countWallMooreNeighborsFromGridCoordinate:CGPointMake(x, y)];

if (mooreNeighborWallCount > treasureHiddenLimit) {
// Place treasure here
cell.type = CaveCellTypeTreasure;
}
}
}
}
}
```

This method simply loops over all cells in the cave, and for each floor cell it checks if the number of walls in the Moore neighborhood is greater than `treasureHiddenLimit`. If so, the cell becomes a treasure cell.

You still need to make the treasure visible, so add the following case to the `switch` statement in `generateTiles` in Cave.m:

```case CaveCellTypeTreasure:
{
node = [SKSpriteNode spriteNodeWithTexture:[self.atlas textureNamed:@"tile0_0"]];

SKSpriteNode *treasure = [SKSpriteNode spriteNodeWithTexture:[self.atlas textureNamed:@"treasure"]];
treasure.name = @"TREASURE";
treasure.position = CGPointMake(0.0f, 0.0f);

break;
}
```

If the cell type is equal to `CaveCellTypeTreasure`, then it creates a tile for the floor. Then it adds another `SKSpriteNode`, and assigns a treasure texture as a child to the floor tile. By adding the chest as a child, you can easily remove it when the knight collects the goods.

Placing the treasure requires a single line of code to be added to `generateWithSeed:` in Cave.m. Add the following code just after the line that calls `placeEntranceAndExit`:

```[self placeTreasure];
```

Build and run and send your knight on a treasure hunt.

You now have a fully functional cave generator that places entrance, exit and treasure procedurally. What more could you want? Well, maybe you should do something about the knight's superhuman ability to walk through walls.

## Collision Detection

In the previous tutorial on procedural level generation, the internal physics engine was used to resolve collisions. In this tutorial, you'll take a different approach and implement your own custom collision detection and handling.

There are many varieties of collision detection, and the math behind the methods can be pretty complicated. Lucky for you, this tutorial uses basic rectangular shapes for the cave and knight, so simple bounding box collision detection will suffice.

In order to detect collisions between the knight and the cave, you need to be able to tell which cell(s) the knight currently occupies. In this case, the knight sprite is a bit smaller than a cell, so you know the knight will only ever occupy one, two or four cells.

Once you know which cell(s) the knight occupies, you can tell which are wall cells. For each wall cell, you'll resolve the collision based on the intersection between the knight and the wall.

To do this, calculate the intersection between the rectangle for the knight and the rectangle for the cell.

The following illustration shows how to resolve the collisions:

1. The intersection between the knight and wall is higher than it is wide. Hence, the collision will resolve horizontally, which allows the knight to slide along the wall vertically.
2. The intersection between the knight and the wall is wider than it is tall. The collision will resolve vertically, which allows the knight to slide along the wall horizontally.
3. In case the intersection between the knight and wall is as high as it is wide, the collision will be resolved both horizontally and vertically.

Once you've determined how to resolve the collision, you'll use the intersecting rectangle to move the knight out of the collision.

For instance, if you determine you need to resolve horizontally, you move the knight horizontally in the opposite direction he is moving by an amount that corresponds to the width of the intersecting rectangle.

Since you might need to resolve several wall collisions at once, the best practice is not to change the position of the knight directly. That would cause the knight to stutter while resolving the collisions.

Instead, you'll change the desired position of the knight. Luckily, the `Player` class already includes such a property. :]

Based on the explanation above, you'll need to add a few helper methods:

1. A method to get an array of cells in the cave the knight currently occupies.
2. Another method to resolve collisions between the knight and any wall cells. This method returns a vector to repel the knight in the correct direction based on the intersecting rectangle.

You'll add the collision-handling code to `MyScene`. This is the most logical place, as this is where the game logic lives.

Start by adding a forward declaration of `CaveCell` in Cave.h before `@interface`:

```@class CaveCell;
```

Next, implement the two helper methods described above. You'll start with the method to return an array of cell(s) the knight is currently occupying.

But before you can do that, you need to add two new methods to `Cave`:

• One that will return the grid coordinate for a position (in points)
• Another that returns the rectangle for a cell given a grid coordinate in the cave.

```- (CGPoint)gridCoordinateForPosition:(CGPoint)position
{
return CGPointMake((position.x / self.tileSize.width), (position.y / self.tileSize.height));
}

- (CGRect)caveCellRectFromGridCoordinate:(CGPoint)coordinate
{
if ([self isValidGridCoordinate:coordinate]) {
CGPoint cellPosition = [self positionForGridCoordinate:coordinate];

return CGRectMake(cellPosition.x - (self.tileSize.width / 2),
cellPosition.y - (self.tileSize.height / 2),
self.tileSize.width,
self.tileSize.height);
}
return CGRectZero;
}
```

The first method simply calculates which grid coordinates correspond to the `position` by dividing the position coordinates with the width and height of a tile.

The other method returns the rectangle for a cell at the `coordinate` passed as a parameter.

Now you need to create a few public methods in the `Cave` class. Open Cave.h and add the following method declarations to the interface:

```- (CaveCell *)caveCellFromGridCoordinate:(CGPoint)coordinate;
- (CGPoint)gridCoordinateForPosition:(CGPoint)position;
- (CGRect)caveCellRectFromGridCoordinate:(CGPoint)coordinate;
```

Next, open MyScene.m and add the following `#import`:

```#import "CaveCell.h"
```

This allows `MyScene` to access information about a `CaveCell` object instance.

Still in MyScene.m add the following method:

```- (NSArray *)getCaveCellsFromRect:(CGRect)rect
{
NSMutableArray *array = [NSMutableArray array];

CaveCell *topLeft = [self.cave caveCellFromGridCoordinate:
[self.cave gridCoordinateForPosition:rect.origin]];

CaveCell *topRight = [self.cave caveCellFromGridCoordinate:
[self.cave gridCoordinateForPosition:CGPointMake(CGRectGetMaxX(rect), CGRectGetMinY(rect))]];

CaveCell *bottomLeft = [self.cave caveCellFromGridCoordinate:
[self.cave gridCoordinateForPosition:CGPointMake(CGRectGetMinX(rect), CGRectGetMaxY(rect))]];

CaveCell *bottomRight = [self.cave caveCellFromGridCoordinate:
[self.cave gridCoordinateForPosition:CGPointMake(CGRectGetMaxX(rect), CGRectGetMaxY(rect))]];

if (topLeft && topLeft.type == CaveCellTypeWall) {
}
if (topRight && topRight.type == CaveCellTypeWall && ![array containsObject:topRight]) {
}
if (bottomLeft && bottomLeft.type == CaveCellTypeWall && ![array containsObject:bottomLeft]) {
}
if (bottomRight && bottomRight.type == CaveCellTypeWall && ![array containsObject:bottomRight]) {
}

return array;
}
```

This method accepts a `CGRect` and finds any cells that intersect it. First it finds the `CaveCell` at each corner of `rect` and stores them in `topLeft`, `topRight`, `bottomLeft`, and `bottomRight`.

For each of these cells, you check if it's a wall and ensure it hasn't already been added to `array`. That's because the four cells could potentially all be the same cell if the knight fits exactly within the rectangle of a single cell.

Now that you know the unique wall cell(s) the knight currently occupies, add the second method, which will allow you to resolve all the collisions. Add the following to MyScene.m:

```- (CGPoint)intersectionRepelDistanceBetweenRect:(CGRect)playerRect andRect:(CGRect)cellRect
{
if (CGRectIntersectsRect(playerRect, cellRect)) {
// 1
NSInteger signX = CGRectGetMaxX(playerRect) > CGRectGetMaxX(cellRect) ? 1 : -1;
NSInteger signY = CGRectGetMaxY(playerRect) > CGRectGetMaxY(cellRect) ? 1 : -1;

// 2
CGRect intersectionRect = CGRectIntersection(playerRect, cellRect);

// 3
if (CGRectGetWidth(intersectionRect) < CGRectGetHeight(intersectionRect)) {
// If the width is less than the height, resolve the collision horizontally
return CGPointMake(CGRectGetWidth(intersectionRect) * signX, 0.0f);
} else if (CGRectGetWidth(intersectionRect) > CGRectGetHeight(intersectionRect)) {
// If the width is greater than the height, resolve the collision vertically
return CGPointMake(0.0f, CGRectGetHeight(intersectionRect) * signY);
} else {
// If the width and height of the intersection are equal, then resolve collision
// both horizontally and vertically
return CGPointMake(CGRectGetWidth(intersectionRect) * signX,
CGRectGetHeight(intersectionRect) * signY);
}
}
// 4
return CGPointZero;
}
```

We'll cover this line-by-line:

1. You compare the right and bottom corners of the two rectangles to determine the direction of the intersection. This way you'll know what direction the knight was going when the player collided with the wall cell, so that you can reverse the movement.
2. The handy built-in function `CGRectIntersection` calculates the intersection between the two rectangles.
3. Based on the intersection rectangle, you return the appropriate direction to resolve the collision. Remember the images describing this earlier?
4. If the knight and cell did not intersect, then return `CGPointZero`.

You'll now put these two methods to good use. Add the following code to `update:` in MyScene.m, just after the comment `// Insert code to detect collision between player and walls here`:

```NSArray *cells = [self getCaveCellsFromRect:self.player.boundingRect];

for (CaveCell *cell in cells) {
CGPoint repel = [self intersectionRepelDistanceBetweenRect:self.player.boundingRect
andRect:[self.cave caveCellRectFromGridCoordinate:cell.coordinate]];

self.player.desiredPosition = CGPointMake(self.player.desiredPosition.x + repel.x,
self.player.desiredPosition.y + repel.y);
}
```

Build and run. Voila! The knight no longer has free reign of the cave and superhuman abilities...or does he? Seems he's found his way to the hinterlands.

There are still some places he can squeeze through because there isn't yet a border of walls surrounding the cave. This is easy to fix.

Open Cave.m and add the following method:

```- (BOOL)isEdgeAtGridCoordinate:(CGPoint)coordinate
{
return ((NSUInteger)coordinate.x == 0 ||
(NSUInteger)coordinate.x == (NSUInteger)self.gridSize.width - 1 ||
(NSUInteger)coordinate.y == 0 ||
(NSUInteger)coordinate.y == (NSUInteger)self.gridSize.height - 1);
}
```

This method returns `YES` if a given grid coordinate is at the edge of the grid and `NO` if the grid coordinate isn't at the edge of the grid.

Still inside Cave.m, replace the line that sets `cell.type` in `initializeGrid` with the following code:

```if ([self isEdgeAtGridCoordinate:coordinate]) {
cell.type = CaveCellTypeWall;
} else {
cell.type = [self randomNumberBetween0and1] < self.chanceToBecomeWall ? CaveCellTypeWall :
CaveCellTypeFloor;
}
```

This will ensure all edge cells become walls, but leave it to chance if all other cells should become walls or floors.

Do another build and run. Haha!! The knight is a captive of your cave, well, except for the exit.

## Handling treasure chests and exit

The collision handling between the knight and cave is in place, but you still need to create the code for handling the collisions between the knight and the treasure chests, as well as define what happens when the knight reaches the exit.

You'll handle this collisions in a similar way to how you handled collisions with the walls. The only major difference is the exit and treasure chests should not block the knight from walking through them.

Your strategy is to determine the cell type underneath the center point of the knight. If the cell type is either a `CaveCellTypeExit` or `CaveCellTypeTreasure`, then you'll handle the collisions by taking an appropriate action.

Add the following code to the `update:` method in MyScene.m just after the comment `// Insert code to detect if player reached exit or found treasure here`:

```CaveCell *cell = [self.cave caveCellFromGridCoordinate:
[self.cave gridCoordinateForPosition:self.player.position]];

switch (cell.type) {
case CaveCellTypeExit:
NSLog(@"Found the exit");
break;

case CaveCellTypeTreasure:
NSLog(@"Found treasure");
break;

default:
break;
}
```

First, it determines the type of cell underneath the player. Depending on the cell type it writes a different log statement to the console.

Build and run the project again, and move the knight over the exit and/or treasure cells to see that these collisions are detected.

Now that you know the collision logic works as expected, add the code to handle the collisions. First, add this method to MyScene.m to resolve the collision with the exit:

```- (void)resolveExit
{
// Disable the joystick to ensure the player cannot move around after reaching the exit
self.isExitingLevel = YES;

// Create actions to play the sound file for reaching the exit and add a block to transition
// to the next cave
SKAction *soundAction = [SKAction playSoundFileNamed:@"fanfare.mp3" waitForCompletion:NO];
SKAction *blockAction = [SKAction runBlock:^{
[self.view presentScene:[[MyScene alloc] initWithSize:self.size] transition:[SKTransition
doorsCloseVerticalWithDuration:0.5f]];
}];
SKAction *exitAnimAction = [SKAction sequence:@[[SKAction group:@[soundAction]], blockAction]];

// Run the action sequence
[self.player runAction:exitAnimAction];
}
```

This is basic Sprite Kit code that plays a sound and presents a new scene when the knight emerges from the cave. The first line is important: it sets `isExitingLevel` to `YES`, which `update:` checks to disable the knight's movement.

Go back to `update:` and replace the line `NSLog(@"Found the exit");` with the following:

```[self resolveExit];
```

Do a build and run, and lead your knight to the exit. Once you pass through it, you'll hear a victorious fanfare and a new random cave will generate.

## Epic Loot!

The only thing left to do is to add the code to resolve collisions with treasure chests. Add this final method to MyScene.m:

```- (void)resolveTreasureInCell:(CaveCell *)cell
{
// Make this cell into a floor
cell.type = CaveCellTypeFloor;

// Calculate the position of the cell within the cave
CGPoint cellPosition = CGPointMake(
cell.coordinate.x * self.cave.tileSize.width + self.cave.tileSize.width / 2,
(cell.coordinate.y * self.cave.tileSize.height + self.cave.tileSize.height / 2));

// Get the node at the point of this cell
SKNode *node = [self.cave nodeAtPoint:cellPosition];

if (node) {
// Get the treasure child node
if ([node.name isEqualToString:@"TREASURE"]) {
node = node.parent;
}

// Remove the treasure child sprite node
[node removeAllChildren];

// Play a sound effect for picking up the treasure
[node runAction:[SKAction playSoundFileNamed:@"treasure.wav" waitForCompletion:NO]];
}
}
```

First, the cell converts to a floor cell, which prevents future collisions with this cell. Then it calculates the position of the cell within the cave, which gets the treasure chest sprite node from the cell. The treasure sprite is removed and the game plays a sound file to signal the knight found the treasure.

Finally, change `update:` in MyScene.m by replacing the line `NSLog(@"Found treasure");` with the following:

```[self resolveTreasureInCell:cell];
```

Build and run. Take the knight on an adventure in the cave and collect as much treasure you can before emerging into the next level of the cave.

## Where to Go From Here?

Congratulations! Now that you're at the end of this tutorial, you should have a good understanding of how to implement cellular automaton to create cave-like levels for games.

You also know a thing or two about how to overcome some of the challenges of using a cellular automaton. If you want to see a copy of the game in its entirety, download the final project. It has all the code from the above tutorial.

To take your learnings a step further, experiment with your cave generation code and find ways to improve it.

For instance, you can combine the A* path-finding with removing very small disconnected caverns. This, combined with finding a cell in the main cavern nearby the disconnected cavern, will make the path-finding a lot less destructive. If you want to preserve more of the original structure of the cavern, this is will help.

Also, try to make the tiles in the cave a bit more random, and you can start with some of the extra textures included in the texture atlas. Our book iOS Games by Tutorials has some great examples on how to do this, so be sure to pick up a copy to catapult your skills to the next level.

If you have any comments or suggestions related to this tutorial, please join the discussion below.

Kim Pedersen

When Kim is not working on developing the next treatment for diabetes at a large pharmaceutical company he is spending his spare time developing games for iOS. He started programming on his C64 at the age of 8, and has since then been creating games on Amiga, PC and XBox360. He never thought he would ditch his beloved Windows PC for a Mac - but that changed three years ago and he has since then been dedicated to developing the next big iOS mobile indie hit.

... 27 total!

... 83 total!

... 47 total!

... 16 total!

... 4 total!

... 32 total!

... 4 total!

... 8 total!

... 4 total!