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

A tutorial on procedural level generation using a cellular automaton to create cave-like levels in games. By Kim Pedersen.

### Sign up/Sign in

With a **free** Kodeco account you can download source code, track your progress,
bookmark, personalise your learner profile and more!

Already a member of Kodeco? Sign in

### Sign up/Sign in

With a **free** Kodeco account you can download source code, track your progress,
bookmark, personalise your learner profile and more!

Already a member of Kodeco? Sign in

## Contents

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

45 mins

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

- First, you select the main cavern array, as this is where you place the entrance and exit.
- 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.
- Convert the random cell to an entrance cell and set the
`entrance`

property coordinates for that cell. - 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.
- 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. - 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.

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

*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));
```

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