Procedural Level Generation in Games Tutorial: Part 2

A tutorial on procedural level generation using the Drunkard Walk algorithm. By Kim Pedersen.

Leave a rating/review
Save for later

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

This is the second and final part of the tutorial that teaches you how to implement procedurally generated levels using the Drunkard Walk algorithm.

In the first part of the tutorial, you created the basic level generation and learned how to use Sprite Kit’s build-in physics engine to set up collision detection so the player cannot walk through walls.

Now in Part 2, you’re going to extend your algorithm to generate a more dungeon-like level with more open spaces, allow for the simultaneous creation of multiple paths and include properties to put you in better control of the level generation process.

You will continue where you left off in the first part, so grab the completed project from Part 1 if you do not have it already.

Get ready to level up again!

The FloorMaker Class

You might have noticed that the levels generated in Part 1 tend to be long, winding corridors. This is obviously not a very interesting level design and makes finding the exit less than a challenge.

That you get long corridors is not surprising. After all, the algorithm you’ve implemented moves one tile in a random direction and then does that again, thereby connecting it to the previous tile positioned. While there is a chance this might generate wide room-like areas, it isn’t likely to do so often enough to create maps that look like dungeons.

Now you’ll modify the algorithm so that it performs several random walks simultaneously. Basically, it will be like throwing all the drunken people out of the bar and asking them to go home.

The map generation needs to track different paths being created at the same time. You’ll do this using an instance of a class named FloorMaker for each path.

Go to File\New\New File…, choose the iOS\Cocoa Touch\Objective-C class template and click Next. Name the class FloorMaker, make it a subclass of NSObject and click Next. Be sure the ProceduralLevelGeneration target is selected and then click Create.

Open FloorMaker.h and add the following code between @interface and @end:

@property (nonatomic) CGPoint currentPosition;
@property (nonatomic) NSUInteger direction;

- (instancetype) initWithCurrentPosition:(CGPoint)currentPosition andDirection:(NSUInteger)direction;

Now open FloorMaker.m and implement the initializer method:

- (instancetype) initWithCurrentPosition:(CGPoint)currentPosition andDirection:(NSUInteger)direction
    if (( self = [super init] ))
        self.currentPosition = currentPosition;
        self.direction = direction; 
    return self;

FloorMaker is fairly simple. It has two properties to keep track of the current position and direction, and an initializer that allows you to set these properties when you create an instance of the class.

With the FloorMaker class in place, you can move on to using it in the map generation.

Running the FloorMaker

The first step is to import FloorMaker into Map.m. Add the following code after the existing #import pre-processor directives:

#import "FloorMaker.h"

You’ll refactor generateTileGrid to use multiple FloorMaker objects simultaneously, but you’ll do so in stages. First, make the following modifications so that it uses a single FloorMaker.

Inside generateTileGrid, replace this line:

CGPoint currentPosition = startPoint;

With this one:

FloorMaker* floorMaker = [[FloorMaker alloc] initWithCurrentPosition:startPoint andDirection:0];

You no longer need to store the current position in a local variable, because each FloorMaker will store its own current position. So you delete the currentPosition and add a variable named floorMaker, initialized at startPoint.

Now that you’ve deleted currentPosition, replace each use of currentPosition with floorMaker.currentPosition. Don’t worry, Xcode will give you errors to help you find them. ;]

Next, replace this line:

NSInteger direction = [self randomNumberBetweenMin:1 andMax:4];

With this one:

floorMaker.direction = [self randomNumberBetweenMin:1 andMax:4];

Just as you replaced the local variable currentPosition with floorMaker.currentPosition, here you replace the local variable direction with floorMaker.direction, and for the same reason.

Finally, modify the switch check to use floorMaker.direction instead of the local variable direction.

Build and run, and the app should run exactly as it did before.


Now you’ll change Map to support using multiple FloorMakers. Add the following property to the Map class extension in Map.m:

@property (nonatomic) NSMutableArray *floorMakers;

The floorMakers array holds a reference to all active FloorMakers.

Then go back to generateTileGrid and make the following changes to use the floorMakers array instead of a local FloorMaker object.

Replace the following lines:

NSUInteger currentFloorCount = 1;
FloorMaker* floorMaker = [[FloorMaker alloc] initWithCurrentPosition:startPoint andDirection:0];

With these:

__block NSUInteger currentFloorCount = 1;
self.floorMakers = [NSMutableArray array];
[self.floorMakers addObject:[[FloorMaker alloc] initWithCurrentPosition:startPoint andDirection:0]];

You add the __block type specifier to the currentFloorCount declaration so that you can modify its value from within an Objective-C block, which you’ll be doing shortly. You remove the local floorMaker variable and instead initialize the Map‘s floorMakers property with a mutable array containing a single FloorMaker object. Later, you’ll be adding more FloorMakers to this array.

Modify the contents of the while loop in generateTileGrid as follows:

while ( currentFloorCount < self.maxFloorCount ) {
  [self.floorMakers enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
  FloorMaker *floorMaker = (FloorMaker *)obj;

    // original contents of the while loop HERE

This changes the method so that it iterates over the objects in the floorMakers array and performs the Drunkard Walk for each one.

Eventually you'll have more than one FloorMaker running, but you can only have one exit point. In order to ensure that the last floor tile the game creates becomes the exit, move the line that sets _exitPoint from where it is now to immediately after the currentFloorCount++; line. This simply assigns the _exitPoint after the game creates all the floor tiles, and the final tile created becomes the exit point.

Once again, build and run, and note that things seem unchanged.


Allowing for Multiple Paths

While the map generation works, it is still only running one instance of the FloorMaker at any given time, so the levels that are produced are very similar to what you got in Part 1 of the tutorial. Since the idea of the FloorMaker is to have many of them, you're now going to change the generateTileGrid method slightly to allow generation of more FloorMakers.

Back in generateTileGrid, add the following code at the end of the block, just before the closing brace and bracket }]:

if ( [self randomNumberBetweenMin:0 andMax:100] <= 50 )
    FloorMaker *newFloorMaker = [[FloorMaker alloc] initWithCurrentPosition:floorMaker.currentPosition andDirection:[self randomNumberBetweenMin:1 andMax:4]];

    [self.floorMakers addObject:newFloorMaker];

This code adds a 50% chance that a new FloorMaker will be created at each step of a FloorMaker. Notice that the code creates newFloorMaker with a position equal to the current position of the current FloorMaker, but with a random direction.

Build and run again. Notice anything odd?


There are two issues here. First, the algorithm now generates much wider rooms, rather than long corridors. You'll make some changes later to influence the types of maps it creates, so ignore this issue for now.

The second problem is easy to miss, but if you generate a few maps and count the floor tiles, you'll find your app no longer respects the maxFloorCount value. It will actually produce some number of floor tiles between maxFloorCount and maxFloorCount + the number of floorMakers - 1. That's because the while loop in generateTileGrid checks to see if the you've created enough walls before it iterates over floorMakers.

For example, if you had a current value of 62 tiles, a max of 64 and 10 FloorMakers, you would pass the check to enter the while loop, but then you'd produce up to 10 additional floor tiles when you iterated over floorMakers.

To fix this, find the following if check in generateTileGrid that validates newPosition prior to adding a floor type:

      if([self.tiles isValidTileCoordinateAt:newPosition] &&
         ![self.tiles isEdgeTileAt:newPosition] &&
         [self.tiles tileTypeAt:newPosition] == MapTileTypeNone)

And add an additional check to validate currentFloorCount, like this:

      if([self.tiles isValidTileCoordinateAt:newPosition] &&
         ![self.tiles isEdgeTileAt:newPosition] &&
         [self.tiles tileTypeAt:newPosition] == MapTileTypeNone &&
         currentFloorCount < self.maxFloorCount)

Now when you run, you'll get exactly maxFloorCount floor tiles. Go ahead and count them!

While you are getting close to having a true procedurally generated level, there is still one major disadvantage: The only thing you are able to control is how big you want the level to be. Is that really enough? Wouldn't it be great if you could control if you wanted a level with big open spaces or a level with long narrow corridors? I bet it would! It’s all about the properties, baby.

Fine-Tuning Map Generation

To make the Map class more versatile, you're going to add a few properties that will impact the level generation.

Open Map.h and adding the following properties:

@property (nonatomic) NSUInteger turnResistance;
@property (nonatomic) NSUInteger floorMakerSpawnProbability;
@property (nonatomic) NSUInteger maxFloorMakerCount;

These three properties will have a direct impact on the map generation by controlling how a FloorMaker behaves:

  • turnResistance determines how hard it is for the FloorMaker to make a turn. Setting this to 100 will generate one long, straight path whereas 0 will generate paths with lots of twists and turns.
  • floorMakerSpawnProbability controls the probability of creating another FloorMaker while generating the tile grid. A value of 100 will ensure the game creates a FloorMaker at each iteration, whereas 0 will result in no additional FloorMakers beyond the initial one.
  • maxFloorMakerCount is the max number of FloorMakers that can be active at one time.

For these properties to be of any use, you need to implement them in the code. First make sure the properties are properly initialized to a default value. Open Map.m and add the following code to initWithGridSize: just after self.gridSize = gridSize:

self.maxFloorCount = 110;
self.turnResistance = 20;
self.floorMakerSpawnProbability = 25;
self.maxFloorMakerCount = 5;

Go to generateTileGrid in Map.m and find the following line:

floorMaker.direction = [self randomNumberBetweenMin:1 andMax:4];

And turn it into the following if statement:

if ( floorMaker.direction == 0 || [self randomNumberBetweenMin:0 andMax:100] <= self.turnResistance ){
  floorMaker.direction = [self randomNumberBetweenMin:1 andMax:4];

This small change ensures that the game only changes the direction of a FloorMaker if the FloorMaker has no set direction or when the turnResistance probability has been exceeded. As explained above, the higher the value of turnResistance, the higher the probability of the FloorMaker changing direction.

Next, change the line:

if ( [self randomNumberBetweenMin:0 andMax:100] <= 50 ) this:

if ( [self randomNumberBetweenMin:0 andMax:100] <= self.floorMakerSpawnProbability &&
     [self.floorMakers count] < self.maxFloorMakerCount )

Now, instead of a hard-coded 50% chance of creating a new FloorMaker, you can adjust the probability to make it more or less likely to create a new FloorMaker if the number of existing FloorMakers is less than the maximum allowed, as defined by maxFloorMakerCount.

Map generated with a maxFloorCount = 110, maxFloorMakerCount = 5, floorMakerSpawnProbability = 25 and turnResistance = 20. Experiment and see what levels you will get.

Map generated with a maxFloorCount = 110, maxFloorMakerCount = 5, floorMakerSpawnProbability = 25 and turnResistance = 20. Experiment and see what sort of levels you get.

Open MyScene.m and add the following lines after the line = 64: = 3; = 20; = 30;

Build and run.

Procedural Levels, tweaked values

Procedural Levels, tweaked values

Before moving on, experiment with setting different values for these properties as well as the maxFloorCount to become familiar with how they affect level generation.

When you're finished, change the values in MyScene.m to look like these: = 110; = 20; = 25; = 5;

Fine-Tuning Room Size

So far, a FloorMaker only places one floor at a time, but the method applied here can just as easily place several floor tiles in one step, allowing for more open areas within the generated map.

To remain flexible with the level generation, first add a few properties to the Map.h file:

@property (nonatomic) NSUInteger roomProbability;
@property (nonatomic) CGSize roomMinSize;
@property (nonatomic) CGSize roomMaxSize;

Then initialize these properties with a default value in initWithGridSize: in Map.m, right after the line that sets maxFloorMakerCount:

self.roomProbability = 20;
self.roomMinSize = CGSizeMake(2, 2);
self.roomMaxSize = CGSizeMake(6, 6);

By default, 20% of the time the game will generate a room with a size between (2,2) tiles and (6,6) tiles.

Still in Map.m, insert the following method:

- (NSUInteger) generateRoomAt:(CGPoint)position withSize:(CGSize)size
    NSUInteger numberOfFloorsGenerated = 0;
    for ( NSUInteger y = 0; y < size.height; y++)
        for ( NSUInteger x = 0; x < size.width; x++ )
            CGPoint tilePosition = CGPointMake(position.x + x, position.y + y);

            if ( [self.tiles tileTypeAt:tilePosition] == MapTileTypeInvalid )

            if ( ![self.tiles isEdgeTileAt:tilePosition] )
                if ( [self.tiles tileTypeAt:tilePosition] == MapTileTypeNone )
                    [self.tiles setTileType:MapTileTypeFloor at:tilePosition];

    return numberOfFloorsGenerated;

This method adds a room with its top-left corner at the passed position with the passed size and returns a value representing the number of tiles created. If the room overlaps any existing floor tiles, then that overlap is not counted in the number returned by the method.

To start generating rooms, go to generateTileGrid in Map.m and insert the following lines just after currentFloorCount++:

if ( [self randomNumberBetweenMin:0 andMax:100] <= self.roomProbability )
    NSUInteger roomSizeX = [self randomNumberBetweenMin:self.roomMinSize.width 
    NSUInteger roomSizeY = [self randomNumberBetweenMin:self.roomMinSize.height 

    currentFloorCount += [self generateRoomAt:floorMaker.currentPosition 
                                     withSize:CGSizeMake(roomSizeX, roomSizeY)];

This generates a new room at the current position of the FloorMaker with a room size that is between the minimum and maximum, so long as the probability of creating a room instead of a tile has been met.

To experiment with these new properties, go to MyScene.m and set the properties of the Map class by inserting the following code right before [self generate] in initWithSize:: = 20; = CGSizeMake(2, 2); = CGSizeMake(6, 6);

Build and run with various different values to see how they affect the map generation.


At this point, it's once again possible to create more than maxFloorCount floor tiles, because the room creation logic does not check internally to make sure the added tiles for the room doesn't exceed the limit.

You've created a versatile map generation class that whips out a new level every time you send a generate message to an instance of the Map class. By changing its properties, you can directly control if you want big open spaces or tight narrow corridors.

Where to Go from Here?

Here’s the final project with all of the code from the tutorial.

The Drunkard Walk algorithm is an extremely powerful yet simple procedural generation method that you can easily extend to produce any variation of dungeon you might like. But it is just one of many procedural generation algorithms out there and all of them have their strengths and weaknesses.

Let me know if you enjoyed this series and would like to see more in this series on procedural level generation. Also, if you have any comments or suggestions related to this tutorial, please join the forum discussion below!

Kim Pedersen


Kim Pedersen


Over 300 content creators. Join our team.