Procedural Level Generation in Games Tutorial: Part 2

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 )

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

• One great method for creating cave levels is cellular automata, which has infinite customization possibilities.
• Another great method to learn is Binary Space Partitioning (BSP), which creates some wicked-looking grid-like dungeon levels.

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!