Procedural Level Generation in Games Tutorial: Part 1

Note from Ray: This is a brand new Sprite Kit tutorial released as part of the iOS 7 Feast. Enjoy!

Most games you play have carefully designed levels that always remain the same. Experienced players know exactly what happens at any given time, when to jump and what button to press. While this is not necessarily a bad thing, it does to some extent reduce the game’s lifespan with a given player. Why play the same level over and over again?

One way to increase your game’s replay value is to allow the game to generate its content programmatically – also known as adding procedurally generated content.

In this tutorial, you will learn to create tiled dungeon-like levels using an algorithm called the Drunkard Walk. You will also create a reusable Map class with several properties for controlling a level’s generation.

This tutorial 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 not yet ready to switch to Sprite Kit, fear not. You can easily rewrite the code in this tutorial to use Cocos2d.

Getting Started

Before getting started, let’s clear up one possible misconception: procedural should not be confused with random. Random means that you have little control over what happens, which should not be the case in game development.

Even in procedurally generated levels, your player should be able to reach the exit. What would be the fun of playing an endless runner like Canabalt if you got to a gap between buildings that would be impossible to jump? Or playing a platformer where the exit is in a place you cannot reach? In this sense, it might be even harder to design a procedurally generated level than to carefully craft your level in Tiled.

I assume, being the bad-ass coder that you are, that you scoff at such cautionary statements. To get started, download the starter project for this tutorial. Once downloaded, unzip the file and open the project in Xcode, and build and run. You should now see a screen similar to this:

Procedural Level Generation Starter Project

The starter project contains the basic building blocks of the game, including all necessary artwork, sound effects and music. Take note of the following important classes:

• Map: Creates a basic 10×10 square that functions as the level for the game.
• MapTiles: A helper class that manages a 2D grid of tiles. I will explain this class later in the tutorial.
• DPad: Provides a basic implementation of a joystick to control the player’s character, a cat.
• MyScene: Sets up the Sprite Kit scene and processes game logic.

Spend a few moments getting familiar with the code in the starter project before moving on. There are comments to help you understand how the code works. Also, try playing the game by using the DPad at the bottom-left corner to move the cat to the exit. Notice how the start and exit points change every time the level begins.

The Beginnings of a New Map

If you played the starter game more than once, you probably discovered that the game isn’t very fun. As Jordan Fisher writes in GamaSutra, game levels, especially procedurally generated ones, need to nail these three criteria to be successful:

• Feasibility: Can you beat the level?
• Interesting design: Do you want to beat it?
• Skill level: Is it a good challenge?

Your current level fails two of these three criteria: The design is not very interesting, as the outer perimeter never changes, and it is too easy to win, as you can always see where the exit is when the level starts. Hence, to make the level more fun, you need to generate a better dungeon and make the exit harder to find.

The first step is to change the way you generate the map. To do so, you’ll delete the Map class and replace it with a new implementation.

Select Map.h and Map.m in the Project Navigator, press Delete and then select Move to Trash.

Next go to File\New\New File…, choose the iOS\Cocoa Touch\Objective-C class and click Next. Name the class Map, make it a Subclass of SKNode and click Next. Make sure the ProceduralLevelGeneration target is selected and click Create.

Open Map.h and add the following code to the @interface section:

@property (nonatomic) CGSize gridSize;
@property (nonatomic, readonly) CGPoint spawnPoint;
@property (nonatomic, readonly) CGPoint exitPoint;

+ (instancetype) mapWithGridSize:(CGSize)gridSize;
- (instancetype) initWithGridSize:(CGSize)gridSize;

This is the interface that MyScene expects for the Map class. You specify here where to spawn the player and exit, and create some initializers to construct the class given a certain size.

Implement these in Map.m by adding this code to the @implementation section:

+ (instancetype) mapWithGridSize:(CGSize)gridSize
{
   return [[self alloc] initWithGridSize:gridSize];
}

- (instancetype) initWithGridSize:(CGSize)gridSize
{
   if (( self = [super init] ))
   {
      self.gridSize = gridSize;
      _spawnPoint = CGPointZero;
      _exitPoint = CGPointZero;
   }
   return self;
}

Here you add a stub implementation that simply sets the player spawn and exit points to CGPointZero. This will allow you to have a simple starting point – you’ll fill these out to be more interesting later.

Build and run, and you should see the following:

Gone are the borders of the map and the feline hero gets sucked right into the exit, making the game unplayable – or really, really easy if you are a glass-half-full kind of person. Not really the a-maze-ing (pun intended) game you were hoping for, right? Well, time to put down some floors. Enter the Drunkard Walk algorithm.

The Drunkard Walk Algorithm

The Drunkard Walk algorithm is a kind of random walk and one of the simplest dungeon generation algorithms around. In its simplest implementation, the Drunkard Walk algorithm works as follows:

The principle of the Drunkard Walk algorithm.

1. Choose a random start position in a grid and mark it as a floor.
2. Pick a random direction to move (Up, Down, Left or Right).
3. Move in that direction and mark the position as a floor, unless it already is a floor.
4. Repeat steps 2 and 3 until a desired number of floors have been placed in the grid.

Nice and simple, eh? Basically, it is a loop that runs until a desired number of floors have been placed in the map. To allow the map generation to be as flexible as possible, you will start implementing the algorithm by adding a new property to hold the number of tiles to generate.

Open Map.h and add the following property:

@property (nonatomic) NSUInteger maxFloorCount;

Next, open Map.m and add the following method:

- (void) generateTileGrid
{
    CGPoint startPoint = CGPointMake(self.gridSize.width / 2, self.gridSize.height / 2);

    NSUInteger currentFloorCount = 0;

    while ( currentFloorCount < self.maxFloorCount )
    {
        currentFloorCount++;
    }
}

The above code begins to implement step 1 in the basic Drunkard Walk algorithm loop, but there is one significant difference. Can you spot it?

[spoiler title="Solution"]startPoint is defaulted to the center of the grid instead of a random position. You do this to prevent the algorithm from butting up against the edges and getting stuck. More about that in the second part of the tutorial.[/spoiler]

generateTileGrid begins by setting a start position and then enters a loop that runs until the currentFloorCount is equal to the desired number of floors defined by the maxFloorCount property.

When you initialize a Map object, you should invoke generateTileGrid to ensure that you create the grid. So, add the following code to initWithGridSize: in Map.m, after the _exitPoint = CGPointZero line:

[self generateTileGrid];

Build and run to make sure the game compiles as expected. Nothing has changed since the last run. The cat is still sucked into the exit and there are still no walls. You still need to write the code to generate the floor, but before you do that, you need to understand the MapTiles helper class.