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
Share

Procedural Level Generation in Games Tutorial: Part 2

20 mins

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 `FloorMaker`s. 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 `FloorMaker`s.

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

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 `FloorMaker`s 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 `FloorMaker`s.

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

}
```

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 `FloorMaker`s, 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 `FloorMaker`s beyond the initial one.
• `maxFloorMakerCount` is the max number of `FloorMaker`s 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 )`

...to 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 `FloorMaker`s 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 sort of levels you get.

Open MyScene.m and add the following lines after the line `self.map.maxFloorCount = 64`:

```self.map.maxFloorMakerCount = 3;
self.map.floorMakerSpawnProbability = 20;
self.map.turnResistance = 30;
```

Build and run.

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:

```self.map.maxFloorCount = 110;
self.map.turnResistance = 20;
self.map.floorMakerSpawnProbability = 25;
self.map.maxFloorMakerCount = 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 )
{
continue;
}

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

numberOfFloorsGenerated++;
}
}
}
}
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
andMax:self.roomMaxSize.width];
NSUInteger roomSizeY = [self randomNumberBetweenMin:self.roomMinSize.height
andMax:self.roomMaxSize.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:`:

```self.map.roomProbability = 20;
self.map.roomMinSize = CGSizeMake(2, 2);
self.map.roomMaxSize = 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

Author