Procedural Level Generation in Games Tutorial: Part 1

Managing the Tile Grid

The MapTiles class is essentially a wrapper for a dynamic C array that will manage a 2D grid for the Map class.

Note: If you're wondering why I choose to use a C array instead of an NSMutableArray, it comes down to personal preference. I generally do not like boxing primitive data types like integers into objects and then unboxing them again to use them, and since the MapTiles grid is just an array of integers, I prefer a C array.

The MapTiles class is already in your project. If you've taken a glance through and feel you understand how it works well, feel free to skip ahead to the next section, Generating the Floor.

But if you're unsure about how it works, keep reading to learn how to recreate it step-by-step, and I'll explain how it works along the way.

To start, select MapTiles.h and MapTiles.m in the Project Navigator, press Delete and then select Move to Trash.

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

In order to make it easy to identify the type of tile, add this enum below the #import statement in MapTiles.h:

typedef NS_ENUM(NSInteger, MapTileType)
{
    MapTileTypeInvalid = -1,
    MapTileTypeNone = 0,
    MapTileTypeFloor = 1,
    MapTileTypeWall = 2,
};

If later on you want to extend the MapTiles class with further tile types, you should put those in this MapTileType enum.

Note: Notice the integer values you assign to each of the enums. They weren't picked at random. Look in the tiles.atlas texture atlas and click the 1.png file, and you will see that it is the texture for the floor just as MapTileTypeFloor has a value of 1. This makes it easy to convert the 2D grid array into tiles later on.

Open MapTiles.h and add the following properties and method prototypes between @interface and @end:

@property (nonatomic, readonly) NSUInteger count;
@property (nonatomic, readonly) CGSize gridSize;

- (instancetype) initWithGridSize:(CGSize)size;
- (MapTileType) tileTypeAt:(CGPoint)tileCoordinate;
- (void) setTileType:(MapTileType)type at:(CGPoint)tileCoordinate;
- (BOOL) isEdgeTileAt:(CGPoint)tileCoordinate;
- (BOOL) isValidTileCoordinateAt:(CGPoint)tileCoordinate;

You've added two read-only properties: count provides the total number of tiles in the grid and gridSize holds the width and height of the grid in tiles. You'll find these properties handy later on. I'll explain the five methods as you implement the code.

Next, open MapTiles.m and add the following class extension right above the @implementation line:

@interface MapTiles ()
@property (nonatomic) NSInteger *tiles;
@end

This code adds a private property tiles to the class. This is a pointer to the array that holds information about the tile grid.

Now implement initWithGridSize: in MapTiles.m after the @implementation line:

- (instancetype) initWithGridSize:(CGSize)size
{
    if (( self = [super init] ))
    {
        _gridSize = size;
        _count = (NSUInteger) size.width * size.height;
        self.tiles = calloc(self.count, sizeof(NSInteger));
        NSAssert(self.tiles, @"Could not allocate memory for tiles");
    }
    return self;
}

You initialize the two properties in initWithGridSize:. Since the total number of tiles in the grid is equal to the width of the grid multiplied by the grid height, you assign this value to the count property. Using this count, you allocate the memory for the tiles array with calloc, which ensures all variables in the array are initialized to 0, equivalent to the enumerated variable MapTileTypeNone.

As ARC will not manage memory allocated using calloc or malloc, you should release the memory whenever you deallocate the MapTiles object. Before initWithGridSize: but after @implementation, add the dealloc method:

- (void) dealloc
{
    if ( self.tiles )
    {
        free(self.tiles);
        self.tiles = nil;
    }
}

dealloc frees the memory when you deallocate an object and resets the tiles property pointer to avoid it pointing to an array that no longer exists in memory.

Apart from the construction and deconstruction, the MapTiles class also has a few helper methods for managing tiles. But before you start implementing these methods, you need to understand how the tiles array exists in memory versus how it is organized in a grid.

Figure 1: How calloc organizes the variables in memory. Each number is the index of the variable in memory.

When you allocate memory for the tiles using calloc, it reserves n bytes for each array item, depending on the data type, and puts them end-to-end in a flat structure in memory (see figure 1).

This organization of tiles is hard to work with in practice. It is much easier to find a tile by using an (x,y) pair of coordinates, as illustrated in Figure 2, so that is how the MapTiles class should organize the tile grid.

Figure 2: How the MapTiles class organizes the variables in memory.

Thankfully, it is very easy to calculate the index of a tile in memory from an (x,y) pair of coordinates since you know the size of the grid from the gridSize property. The numbers outside the square in Figure 2 illustrate the x- and y-coordinates, respectively. For example, the (x,y) coordinates (1,2) in the grid will be index 9 of the array. You calculate this using the formula:

index in memory = y * gridSize.width + x

With this knowledge, you can start implementing a method that will calculate an index from a pair of grid coordinates. For convenience, you will also create a method to ensure the grid coordinates are valid.

In MapTiles.m, add the following new methods:

- (BOOL) isValidTileCoordinateAt:(CGPoint)tileCoordinate
{
    return !( tileCoordinate.x < 0 ||
              tileCoordinate.x >= self.gridSize.width ||
              tileCoordinate.y < 0 ||
              tileCoordinate.y >= self.gridSize.height );
}

- (NSInteger) tileIndexAt:(CGPoint)tileCoordinate
{
    if ( ![self isValidTileCoordinateAt:tileCoordinate] )
    {
        NSLog(@"Not a valid tile coordinate at %@", NSStringFromCGPoint(tileCoordinate));
        return MapTileTypeInvalid;
    }
    return ((NSInteger)tileCoordinate.y * (NSInteger)self.gridSize.width + (NSInteger)tileCoordinate.x);
}

isValidTileCoordinateAt: tests if a given pair of coordinates is within the bounds of the grid. Notice how the method checks to see if it is outside of the bounds and then returns the opposite result, so if the coordinates are outside the bounds, it returns NO, and if they are not outside of the bounds, it returns YES. This is faster than checking if the coordinates are within the bounds, which would require the conditions to be AND-ed together instead of OR-ed.

tileIndexAt: uses the equation discussed above to calculate an index from a pair of coordinates, but before doing this, it tests if the coordinates are valid. If not, it returns MapTileTypeInvalid, which has a value of -1.

With the math in place, it is now possible to easily create the methods to return or set the tile type. So, add the following two methods after initWithGridSize: in MapTiles.m:

- (MapTileType) tileTypeAt:(CGPoint)tileCoordinate
{
    NSInteger tileArrayIndex = [self tileIndexAt:tileCoordinate];
    if ( tileArrayIndex == -1 )
    {
        return MapTileTypeInvalid;
    }
    return self.tiles[tileArrayIndex];
}

- (void) setTileType:(MapTileType)type at:(CGPoint)tileCoordinate
{
    NSInteger tileArrayIndex = [self tileIndexAt:tileCoordinate];
    if ( tileArrayIndex == -1 )
    {
        return;
    }
    self.tiles[tileArrayIndex] = type;
}

The two methods calculate the index from the pair of coordinates passed using the tileIndexAt: method you just added and then either set or return the MapTileType from the tiles array.

Last but not least, add a method to determine if a given pair of tile coordinates is at the edge of the map. You'll later use this method to ensure you do not place any floors at the edge of the grid, thereby making it impossible to encapsulate all floors behind walls.

- (BOOL) isEdgeTileAt:(CGPoint)tileCoordinate
{
    return ((NSInteger)tileCoordinate.x == 0 ||
            (NSInteger)tileCoordinate.x == (NSInteger)self.gridSize.width - 1 ||
            (NSInteger)tileCoordinate.y == 0 ||
            (NSInteger)tileCoordinate.y == (NSInteger)self.gridSize.height - 1);
}

Referring to Figure 2 above, notice that border tiles would be any tile with an x-coordinate of 0 or gridSize.width – 1, since the grid indices are zero-based. Equally, an y-coordinate of 0 or gridSize.height – 1 would be a border tile.

Finally, when testing it's nice to be able to see what your procedural generation is actually generating. Add the following implementation of description, which will output the grid to the console for easy debugging:

- (NSString *) description
{
    NSMutableString *tileMapDescription = [NSMutableString stringWithFormat:@"<%@ = %p | \n",
                                           [self class], self];
    
    for ( NSInteger y = ((NSInteger)self.gridSize.height - 1); y >= 0; y-- )
    {
        [tileMapDescription appendString:[NSString stringWithFormat:@"[%i]", y]];
        
        for ( NSInteger x = 0; x < (NSInteger)self.gridSize.width; x++ )
        {
            [tileMapDescription appendString:[NSString stringWithFormat:@"%i", 
                                              [self tileTypeAt:CGPointMake(x, y)]]];
        }
        [tileMapDescription appendString:@"\n"];
    }
    return [tileMapDescription stringByAppendingString:@">"];
}

This method simply loops through the grid to create a string representation of the tiles.

That was a lot of text and code to take in, but what you've built will make the procedural level generation much easier, since you can now abstract the grid handling from the level generation. Now it's time to lay down some ground.