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

Procedural Level Generation in Games using a Cellular Automaton: Part 1
Learn how to add a procedural cave system into your game!

Learn how to add a procedural cave system into your game!

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.

Moore and von Neumann neighborhoods

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

To get started, download the starter project.

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:

Starter Project first run

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,

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;
      [row addObject:cell];
    [self.grid addObject:row];

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?

Solution Inside: Solution SelectShow
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].

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";
[_cave generateWithSeed:0];
[_world addChild:_cave];

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:

Output to console

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"]];
          node = [SKSpriteNode spriteNodeWithTexture:[self.atlas textureNamed:@"tile0_0"]];
      // Add code to position node here:
      node.blendMode = SKBlendModeReplace;
      node.texture.filteringMode = SKTextureFilteringNearest;
      [self addChild:node];

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:

Tile Position Incorrect

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.

Calculating position for a tile

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.

The tiles are aligning perfectly

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

Solution Inside: Solution SelectShow
initializeGrid initializes every cell it creates as a floor tile.

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:


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:

Initial seeded cave

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 effect of transition rules on cave development
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?

Solution Inside: Solution SelectShow
There are eight cells in the Moore neighborhood. See the illustration below for further details.
Moore and von Neumann neighborhoods

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 ) {
      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.

Counting walls in the Moore neighborhood

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;
      [newRow addObject:newCell];
    [newGrid addObject:newRow];
  // 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).
  6. 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.

Disconnected caverns

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

Holy Hand Grenade 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;

This allows easy access to information about the caverns later.

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
  // 1
  CaveCell *cell = (CaveCell *)array[(NSUInteger)coordinate.y][(NSUInteger)coordinate.x];
  // 2
  if (cell.type != CaveCellTypeFloor) {
  // 3
  cell.type = fillNumber;
  // 4
  [[self.caverns lastObject] addObject:cell];
  // 5
  if (coordinate.x > 0) {
    [self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x - 1, coordinate.y)
  if (coordinate.x < self.gridSize.width - 1) {
    [self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x + 1, coordinate.y)
  if (coordinate.y > 0) {
    [self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x, coordinate.y - 1)
  if (coordinate.y < self.gridSize.height - 1) {
    [self floodFillCavern:array fromCoordinate:CGPointMake(coordinate.x, coordinate.y + 1)

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;
      [floodFillArrayRow addObject:copiedCell];
    [floodFillArray addObject:floodFillArrayRow];
  // 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.caverns addObject:[NSMutableArray array]];
        [self floodFillCavern:floodFillArray fromCoordinate:CGPointMake(x, y) 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 CaveCells.
  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.

Number of caverns

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 =

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.
Removing unconnected caverns

Tip: It might be difficult to actually see what has changed between runs. The following illustrations show exactly what happened.Before and after removing disconnected cavernsThese images were created by using spriteNodeWithColor:size: with a size of 2×2 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!

Procedural Level Generation in Games using a Cellular Automaton: Part 1 is a post from: Ray Wenderlich

The post Procedural Level Generation in Games using a Cellular Automaton: Part 1 appeared first on Ray Wenderlich.



Write a comment