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

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

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:

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;
      [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?
[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];
[_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:

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