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

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

#### Version

• Other, Other, Other

In this tutorial series, you’ll use a discreet model called cellular automaton to generate procedural caves for your games. You’ll also learn how to overcome some of the obstacles this model imposes on level generation, like removing unreachable areas of the level and ensuring the exit can always be reached by the player.

If you have read the previous tutorial on procedural level generation on this site, you already know the basics of procedural level generation using the Drunkard Walk algorithm. The Drunkard Walk is a reliable, battle-tested algorithm that generates levels, but it’s just one of many options out there.

This tutorial series uses Sprite Kit, a framework introduced with iOS 7. You will also need Xcode 5. If you are not already familiar with Sprite Kit, I recommend you read the Sprite Kit Tutorial for Beginners on this site. For readers who are using a different game framework, fear not. You can easily use the ideas from this tutorial in the game framework of your choice.

By now, you’re probably asking yourself, “What on Earth is a cellular automaton, anyway?” Time to indulge in a little theory.

## Cellular Automata Explained

A cellular automaton (pl. cellular automata) is a discreet computational model first discovered in the 1940s. Experts in mathematics, physics and biology have studied it extensively, and while it has produced mountains of complex mathematics, the basic concept is really simple.

At its core, a cellular automaton consists of an n-dimensional grid with a number of cells in a finite state and a set of transition rules. Each cell of the grid can be in one of several states; in the simplest case, cells can be on or off.

The initial distribution of cell states constitutes the seed of the automaton in an initial state (t0).

A new generation is created (advancing t by 1) by applying the transition rules to all cells simultaneously, thereby putting every cell in a new state in terms of its current state and the current states of all the cells in its neighborhood. The neighborhood defines which cells around a given cell affect its future state.

For a two-dimensional automata, the two most common types of neighborhoods are Moore neighborhoods and von Neumann neighborhoods, as illustrated below.

A Moore neighborhood (a) is a square: a Moore neighborhood of size 1 consists of the eight cells surrounding c, including those surrounding it diagonally.

A von Neumann neighborhood (b) is like a cross centered on P: above, below, left and right.

A well-known example of cellular automata to many game developers is Conway’s Game of Life, which is a two-dimensional grid of cells with each cell in a state of either dead or alive. Four transition rules govern the grid:

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by overcrowding.
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

You’ll be implementing a variation of Game of Life to generate cave-like levels in this tutorial. But enough theory. Time to code.

## Getting Started

Unzip it and double-click CellularAutomataStarter\CellularAutomataStarter.xcodeproj to open it in Xcode. Build and run using the iPhone Retina (3.5-inch) scheme. You’ll see the following on screen:

That is one sad knight. No dragons, no damsels, no battles and no glory in sight! Good thing you’re here to change that. How about you create a treasure-laden cave labyrinth for the knight to explore?

The starter project contains all the assets you’ll need for this tutorial and a few important classes:

• `Cave`: An `SKNode` subclass that contains a stub implementation of the cave class. You’ll extend this throughout the tutorial.
• `DPad`: Provides a basic implementation of a joystick so the player can control the knight
• `MyScene`: Sets up the Sprite Kit scene and processes game logic
• `Player`: A `SKSpriteNode` subclass that contains the knight’s logic

Take a moment to browse the project and familiarize yourself with the setup. The code has plenty of comments to help you understand how it works. Are you ready to give your knight something to do?

## Implementing a Cellular Automaton

Your first step to implement a cellular automaton is to create a grid and put cells into the grid.

Open Cave.m and add the following private property to the class extension:

```@property (strong, nonatomic) NSMutableArray *grid;
```

You made the property for the grid private, because you shouldn’t modify it directly from outside the class. Besides, the state of the grid will update via the transition rules you’ll add later in the tutorial.

Next, create a new class to serve as a cell in your grid.

Create a new file by selecting File\New\File…, choose iOS\Cocoa Touch\Objective-C class and click Next. Name the class CaveCell, make it a Subclass of NSObject, click Next, make sure the CellularAutomataStarter target is checked, and click Create.

Each cell should be in a finite state, so add the following enumeration to the CaveCell.h class after the `#import` statement:

```typedef NS_ENUM(NSInteger, CaveCellType) {
CaveCellTypeInvalid = -1,
CaveCellTypeWall,
CaveCellTypeFloor,
CaveCellTypeMax
};
```

This defines the possible states for cells in the game, along with `CaveCellTypeMax` that always has a value of one greater than the last real state. Adding a value like this to an `enum` definition makes it easy to do things like loop through all the possible values.

Also in CaveCell.h, add the following code to the `@interface` section:

```@property (assign, nonatomic) CGPoint coordinate;
@property (assign, nonatomic) CaveCellType type;

- (instancetype)initWithCoordinate:(CGPoint)coordinate;
```

This adds two public properties to the class, one to store the cell’s coordinates within the grid and one to store the cell’s type (or state). You also added an initializer to construct a new cell with the given coordinates.

Implement the initializer in CaveCell.m by adding the following code in the `@implementation` section:

```- (instancetype)initWithCoordinate:(CGPoint)coordinate
{
if ((self = [super init])) {
_coordinate = coordinate;
_type = CaveCellTypeInvalid;
}
return self;
}
```

The initializer creates a new CaveCell instance with the coordinate given and sets the type to `CaveCellTypeInvalid`. Later, you’ll set the type of the cell to either a wall (`CaveCellTypeWall`) or a floor (`CaveCellTypeFloor`).

You’ve now created the foundation for two of the three core parts of a cellular automaton: the grid and the cell. Next, you’ll create a method to put the cells into the grid.

Open Cave.m and import the CaveCell.h header:

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

Still inside Cave.m, add the following method that initializes the grid:

```- (void)initializeGrid
{
self.grid = [NSMutableArray arrayWithCapacity:(NSUInteger)self.gridSize.height];

for (NSUInteger y = 0; y < self.gridSize.height; y++) {
NSMutableArray *row = [NSMutableArray arrayWithCapacity:(NSUInteger)self.gridSize.width];

for (NSUInteger x = 0; x < self.gridSize.width; x++) {
CGPoint coordinate = CGPointMake(x, y);
CaveCell *cell = [[CaveCell alloc] initWithCoordinate:coordinate];
cell.type = CaveCellTypeFloor;
}

}
}
```

If you look at `initWithAtlasNamed:gridSize:` in Cave.m, you'll see that you initialize instances of `Cave` by passing in the size of the grid, in cells. You use this information in `initializeGrid` to create a two-dimensional mutable array (i.e. an array of arrays) for the grid and assign a floor cell to each position in the grid.

Do you notice anything strange about how the grid is set up?
[spoiler title="Solution"]The way you set up the arrays means you need to reference cells with the y-coordinate first. That means to get the `CaveCell` at column (x-coordinate) 4 and row (y-coordinate) 6 you would get it using the code `(CaveCell *)self.grid[6][4]`.[/spoiler]

To allow generating a new cave from the Cave class, add this new method declaration to Cave.h:

```- (void)generateWithSeed:(unsigned int)seed;
```

Now, implement it in Cave.m:

```- (void)generateWithSeed:(unsigned int)seed
{
NSLog(@"Generating cave...");
NSDate *startDate = [NSDate date];

[self initializeGrid];

NSLog(@"Generated cave in %f seconds", [[NSDate date] timeIntervalSinceDate:startDate]);
}
```

This method initializes the grid using `initializeGrid` and logs the time it took to generate the cave. The method also accepts a `seed` parameter. Although you don't do anything with this parameter yet, soon you will implement code that allows you to generate different caves by using different values for this parameter.

But if you pass the same value, it will always generate the same cave. In this tutorial, you'll always pass the same value – 0 – to make it easier to observe changes.

Tip: If you want to generate a random cave every time, just pass `time(0)` as the seed value in your call to `generateWithSeed:`.

To test that everything works as intended open MyScene.m and add the following import statement:

```#import "Cave.h"
```

Also, add the following private property to the class extension:

```@property (strong, nonatomic) Cave *cave;
```

You're going to use this property to ensure easy access to the `Cave` object you generate.

Finally, add the following code after the inline comment `// Add code to generate new cave here` in `initWithSize:`:

```_cave = [[Cave alloc] initWithAtlasNamed:@"tiles" gridSize:CGSizeMake(64.0f, 64.0f)];
_cave.name = @"CAVE";
[_cave generateWithSeed:0];
```

This will instantiate a new `Cave` object using a texture atlas named "tiles" and then generate the cave with a seed value of `0`. Then `_cave` is added as a child of `_world` (rather than the scene itself, which will make scrolling easier later).

Build and run the game. Check to see if the console has an entry like this:

At the moment, there is no visual difference to the game. You should do something about that. :]

## Creating Tiles

Do you remember passing the name of a texture atlas to the initializer when you created `_cave` during initialization of `MyScene`? Your next task is to add the code to create the tiles for the cave using the textures in the tiles atlas.

Before you add the method to create tiles, it's convenient to have a couple helper methods: one to determine if a grid coordinate is valid, and one to get a cell from the grid based on the coordinates.

Add the following methods to Cave.m:

```- (BOOL)isValidGridCoordinate:(CGPoint)coordinate
{
return !(coordinate.x < 0 ||
coordinate.x >= self.gridSize.width ||
coordinate.y < 0 ||
coordinate.y >= self.gridSize.height);
}

- (CaveCell *)caveCellFromGridCoordinate:(CGPoint)coordinate
{
if ([self isValidGridCoordinate:coordinate]) {
return (CaveCell *)self.grid[(NSUInteger)coordinate.y][(NSUInteger)coordinate.x];
}

return nil;
}
```

These methods are pretty straightforward.

• `isValidGridCoordinate:` checks tile coordinates against the grid's size to ensure they are within the range of possible grid coordinates.
• `caveCellFromGridCoordinate:` returns a CaveCell instance based on the grid coordinate. Remember that this is backwards to what you might expect (it uses self.grid[y][x] instead of self.grid[x][y]) due to the way you set up the arrays, as discussed earlier. It returns `nil` if the grid coordinate is invalid.

With these methods in place, you can now implement the method to generate the grid's tiles. Still in Cave.m add the following method:

```- (void)generateTiles
{
for (NSUInteger y = 0; y < self.gridSize.height; y++) {
for (NSUInteger x = 0; x < self.gridSize.width; x++) {
CaveCell *cell = [self caveCellFromGridCoordinate:CGPointMake(x, y)];

SKSpriteNode *node;

switch (cell.type) {
case CaveCellTypeWall:
node = [SKSpriteNode spriteNodeWithTexture:[self.atlas textureNamed:@"tile2_0"]];
break;

default:
node = [SKSpriteNode spriteNodeWithTexture:[self.atlas textureNamed:@"tile0_0"]];
break;
}

// Add code to position node here:

node.blendMode = SKBlendModeReplace;
node.texture.filteringMode = SKTextureFilteringNearest;

}
}
}
```

The code above simply loops through the grid to build sprites based on the types of cells.

Note: This sets the blend mode to replace, because there is no alpha transparency in these cells. It also sets the filtering mode to nearest, which gives a nice pixel-art style.

To create the tiles, add the following code to `generateWithSeed:` in Cave.m, just after `[self initializeGrid];`:

```[self generateTiles];
```

Build and run. You should now see the following, it's not much yet, but your knight is one step closer to adventure:

## Positioning Tiles

The tiles were created based on the node count, but why can't you see them? They're stacked atop each other! Once you create a tile, you need to calculate the position for it in the cave. Take a look at this diagram.

At the top, row numbers begin at 0 and increase towards the bottom, while column numbers begin at 0 on the left and increase towards the right. Remember that the grid array is indexed by (row (y), column (x)). So you're not crazy and this tutorial was not written with a whiskey in hand, the grid is purposefully reversed.

As you see in the diagram, you need the size of a tile to calculate its position correctly. That is why you'll add a handy property to the `Cave` class to get the size. Open Cave.h and add the following property:

```@property (assign, nonatomic, readonly) CGSize tileSize;
```

The property is read only; it will not change once a `Cave` instance generates.

Open Cave.m and add this method:

```- (CGSize)sizeOfTiles
{
SKTexture *texture = [self.atlas textureNamed:@"tile0_0"];
return texture.size;
}
```

This returns the size of one of the tile textures in the cave's atlas, and assumes all are the same size. This is a fair assumption, considering how it builds tile maps.

Go to `initWithAtlasNamed:gridSize:` in Cave.m and add the following line of code after the line `_gridSize = gridSize;`:

```_tileSize = [self sizeOfTiles];
```

Next, you need to create a new method to do the actual calculation of the tile position. Add this new method to Cave.m:

```- (CGPoint)positionForGridCoordinate:(CGPoint)coordinate
{
return CGPointMake(coordinate.x * self.tileSize.width + self.tileSize.width / 2.0f,
(coordinate.y * self.tileSize.height + self.tileSize.height / 2.0f));
}
```

As you see, the calculation in this method corresponds to the calculation illustrated in the diagram above. It simply multiplies the given x and y coordinates with the tile's width and height, respectively.

You add half the tile's width and height to those values because you're calculating the tile's center point.

The last step is to add the positioning to the tile upon creation. Go back to `generateTiles` and add this single line of code after the comment `// Add code to position node here:`:

```node.position = [self positionForGridCoordinate:CGPointMake(x, y)];
```

Build and run the game and use the joystick to move around the cave.

This isn't exactly a cave, is it? More like a giant wasteland. Why are there no walls?

[spoiler title="Solution"]`initializeGrid` initializes every cell it creates as a floor tile.[/spoiler]

## The Initial Seed

Now that the boilerplate code is in place to manage the grid and tile creation, you can safely move on to implementing the first step in the cellular automaton creation: the initial distribution of cell states.

You're going to start by randomly setting each cell to be either a wall or a floor. You'll want to tweak the chance of a cell becoming either a wall or a floor during the cave generation, so, you add the following property to Cave.h:

```@property (assign, nonatomic) CGFloat chanceToBecomeWall;
```

The value of `chanceToBecomeWall` will be in the range of 0.0 to 1.0. A value of 0.0 means all cells in the cave will become floors, and a value of 1.0 means all cells in the cave will become walls.

Inside Cave.m, set the default value of `chanceToBecomeWall` to 0.45 by adding the following code to `initWithAtlasNamed:gridSize:` after the line that initializes `_tileSize`:

```_chanceToBecomeWall = 0.45f;
```

This will mean that there is a 45% chance that a cell become a wall. Why 0.45, you might ask? This value comes from good, old fashioned trial-and-error, and it tends to give satisfactory results.

You'll need to generate random numbers quite a few times during cave generation, so add the following method to Cave.m:

```- (CGFloat) randomNumberBetween0and1
{
return random() / (float)0x7fffffff;
}
```

This method returns a value between 0 and 1. It uses the `random()` function, which needs to be seeded before use. This should only happen once per cave generation, so add the following line in `generateWithSeed:`, just before the line that calls `initializeGrid`:

```srandom(seed);
```

At the moment, all cells in the cave are floors, but it won't always be a two-dimensional environment. You need to take into account the fact that some cells will become a wall or a floor by modifying `initializeGrid`.

Inside `initializeGrid` in Cave.m, replace the line `cell.type = CaveCellTypeFloor;` with the following line of code:

```cell.type = [self randomNumberBetween0and1] < self.chanceToBecomeWall ? CaveCellTypeWall : CaveCellTypeFloor;
```

Instead of defaulting every cell to be a floor, each cell gets a type based on the value returned by the random number generator, taking into account the `chanceToBecomeWall` property.

Time to see the fruit of your labor thus far. Build and run, and you should now see the following:

Try moving around using the joystick. Not very cave-like, is it? So, what's next?

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

// 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).
• The transitioned grid of cells is assigned to the `grid` property. ARC will automatically free memory for the old grid.
• 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. ;]

## Identifying Caverns

Recursive flood-fill with four directions

Good thing there's a fix for the knight, and that is to identify each cavern that is part of the cave. For the sake of clarity with this tutorial, a cavern is defined as an area that isn't connected to any other areas.

Once you identify individual caverns, you can then either connect or remove them all, except the largest cavern. You'll be doing both in this tutorial.

The best way to identify the caverns in the cave is to apply a flood fill algorithm that can determine the area connected to a given cell in a grid.

Have you ever used a flood fills in paint programs like Photoshop to fill areas with a different color? It works just as well on caves. :]

First, add the following private property to the class extension in Cave.m:

```@property (strong, nonatomic) NSMutableArray *caverns;
```

To perform the flood fill, you need two new methods in `Cave.m`:

• One that creates a copy of the current grid. From this, you'll loop over every floor cell. For each one you'll recursively test each floor cell in its von Neumann neighborhood.
• Another you'll call recursively to test cells in the von Neumann neighborhood of a cell. This will also change each tested cell's type to a fill value.

Tackle the recursive method first. Add this method to Cave.m:

```- (void)floodFillCavern:(NSMutableArray *)array fromCoordinate:(CGPoint)coordinate
fillNumber:(NSInteger)fillNumber
{
// 1
CaveCell *cell = (CaveCell *)array[(NSUInteger)coordinate.y][(NSUInteger)coordinate.x];

// 2
if (cell.type != CaveCellTypeFloor) {
return;
}

// 3
cell.type = fillNumber;

// 4

// 5
if (coordinate.x > 0) {
[self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x - 1, coordinate.y)
fillNumber:fillNumber];
}
if (coordinate.x < self.gridSize.width - 1) {
[self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x + 1, coordinate.y)
fillNumber:fillNumber];
}
if (coordinate.y > 0) {
[self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x, coordinate.y - 1)
fillNumber:fillNumber];
}
if (coordinate.y < self.gridSize.height - 1) {
[self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x, coordinate.y + 1)
fillNumber:fillNumber];
}
}
```

The intent of this method is to be recursive. As you can see, it calls itself several times. Here's a play-by-play of what it does:

1. Use the grid `coordinate` passed to the method to get the `CaveCell` to test.
2. If the cell you're testing isn't a floor cell, the method simply returns. When dealing with recursive methods, you always need some condition like this that will eventually stop the recursion, otherwise you'll crash with an infinite loop.
3. You change the cell's type to the `fillNumber` that passed to the method. Each cavern will have a unique fill number, and this is how you'll tell caverns apart later. It also ensures the cell is never tested again because it will no longer be considered a floor cell. This is the reason you're performing the flood fill on a copy of the cave grid.
4. The cell gets added to the last array in the list of caverns. The `lastObject` of the `caverns` array will be the current cavern where you're performing the flood fill.
5. Perform a recursive test for each cell in the von Neumann neighborhood. The test runs in the order west, east, north and south. Performance-wise, this is the smartest way since the flood fill goes from top to bottom.

Still in Cave.m, add the second required method:

```- (void)identifyCaverns
{
// 1
self.caverns = [NSMutableArray array];

// 2
NSMutableArray *floodFillArray = [NSMutableArray arrayWithCapacity:(NSUInteger)self.gridSize.height];

for (NSUInteger y = 0; y < self.gridSize.height; y++) {
NSMutableArray *floodFillArrayRow = [NSMutableArray arrayWithCapacity:(NSUInteger)self.gridSize.width];

for (NSUInteger x = 0; x < self.gridSize.width; x++) {
CaveCell *cellToCopy = (CaveCell *)self.grid[y][x];
CaveCell *copiedCell = [[CaveCell alloc] initWithCoordinate:cellToCopy.coordinate];
copiedCell.type = cellToCopy.type;
}

}

// 3
NSInteger fillNumber = CaveCellTypeMax;
for (NSUInteger y = 0; y < self.gridSize.height; y++) {
for (NSUInteger x = 0; x < self.gridSize.width; x++) {
if (((CaveCell *)floodFillArray[y][x]).type == CaveCellTypeFloor) {
[self floodFillCavern:floodFillArray fromCoordinate:CGPointMake(x, y) fillNumber:fillNumber];
fillNumber++;
}
}
}

NSLog(@"Number of caverns in cave: %lu", (unsigned long)[self.caverns count]);
}
```

Now here's a step-by-step :

1. Create an instance of a new mutable array for the caverns in the cave. Each cavern will be a mutable array of `CaveCell`s.
2. Create a deep copy of the cave grid. Since the flood fill will change the `type` of the cell, you'll need to work on a copy of the grid rather than the grid itself.
3. Perform the flood fill by looping through each cell in the copy of the grid. If the cell is a floor tile, it means the cell has not been tested already, so a new cavern starts and the flood fill starts from the current cell.

Now, add the following line to `generateWithSeed:`, right before the `[self generateTiles];` line:

```[self identifyCaverns];
```

Build and run. In the console, you should be able to see 22 tidy little caverns, for a cave generated with a seed of 0.

You now know all the caverns in the cave and you're left with a few choices with increasing difficulty:

1. You can keep the cave as-is. If you work with destructible terrain, the player will be able to break, blast and bore through the walls to access the unconnected areas.
2. You can remove all the unconnected caverns by filling all but the largest cavern with wall cells. The advantage is that the organic look of the cave remains while ensuring the knight can reach all parts of the cave. The downside is that you lose some playable area.
3. You can connect the unconnected caverns to the largest of the caverns. The advantage is that you keep all the walkable areas of the original cave. The downside is that the connections between the caverns will be straight lines, which just doesn't flatter organic look of a cave.

In this tutorial, you'll learn how to do options two and three. No matter which option you choose for the game, you'll need to know which cavern is the largest, so you know where to put the entry and exit.

All you have to do is count the number of `CaveCell` instances in each cavern array in the `caverns`. So, add the following method to Cave.m to do the counting:

```- (NSInteger)mainCavernIndex
{
NSInteger mainCavernIndex = -1;
NSUInteger maxCavernSize = 0;

for (NSUInteger i = 0; i < [self.caverns count]; i++) {
NSArray *caveCells = (NSArray *)self.caverns[i];
NSUInteger caveCellsCount = [caveCells count];

if (caveCellsCount > maxCavernSize) {
maxCavernSize = caveCellsCount;
mainCavernIndex = i;
}
}

return mainCavernIndex;
}
```

This method will simply loop through each array in `caverns`, checking which has the most instances of `CaveCell`. It returns an index that identifies the largest cavern, and henceforth shall be known as the 'main cavern'.

## Removing Unconnected Caverns

If you choose to remove all the disconnected caverns, then you need to fill them in with wall tiles.

To do that, add this new method to Cave.m:

```- (void) removeDisconnectedCaverns
{
NSInteger mainCavernIndex = [self mainCavernIndex];
NSUInteger cavernsCount = [self.caverns count];

if (cavernsCount > 0) {
for (NSUInteger i = 0; i < cavernsCount; i++) {
if (i != mainCavernIndex) {
NSArray *array = (NSArray *)self.caverns[i];

for (CaveCell *cell in array) {
((CaveCell *)self.grid[(NSUInteger)cell.coordinate.y][(NSUInteger)cell.coordinate.x]).type =
CaveCellTypeWall;
}
}
}
}
}
```

First, this method gets the index of the main cavern, then it uses a `for` loop to go through the `caverns` array. It turns all the `CaveCell` instances into walls within the caverns, except for those in the main cavern.

To see your latest efforts in action, add the following line of code to `generateWithSeed:` just before the line that calls `generateTiles`:

```[self removeDisconnectedCaverns];
```

Build and run now, and note that your cave no longer has any unconnected caverns.

Tip: It might be difficult to actually see what has changed between runs. The following illustrations show exactly what happened.These images were created by using `spriteNodeWithColor:size:` with a size of 2x2 points in place of using `spriteNodeWithTexture:` in `generateTiles`, and modifying `sizeOfTiles` accordingly.

## Where To Go From Here?

Here is the finished example project from this tutorial series so far.

Congratulations, you have generated your own random cave system using cellular automata! Your knight now has a mysterious cavern to explore.

However, there's more you can do! Stay tuned for the second and final part of the series, where 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.

In the meantime, if you have any questions or comments, please join the forum discussion below!