Procedural Level Generation in Games using a Cellular Automaton: Part 1

Creating Tiles

Do you remember passing the name of a texture atlas to the initializer when you created _cave during initialization of MyScene? Your next task is to add the code to create the tiles for the cave using the textures in the tiles atlas.

Before you add the method to create tiles, it's convenient to have a couple helper methods: one to determine if a grid coordinate is valid, and one to get a cell from the grid based on the coordinates.

Add the following methods to Cave.m:

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

- (CaveCell *)caveCellFromGridCoordinate:(CGPoint)coordinate
{
  if ([self isValidGridCoordinate:coordinate]) {
    return (CaveCell *)self.grid[(NSUInteger)coordinate.y][(NSUInteger)coordinate.x];
  }
  
  return nil;
}

These methods are pretty straightforward.

• isValidGridCoordinate: checks tile coordinates against the grid's size to ensure they are within the range of possible grid coordinates.
• caveCellFromGridCoordinate: returns a CaveCell instance based on the grid coordinate. Remember that this is backwards to what you might expect (it uses self.grid[y][x] instead of self.grid[x][y]) due to the way you set up the arrays, as discussed earlier. It returns nil if the grid coordinate is invalid.

With these methods in place, you can now implement the method to generate the grid's tiles. Still in Cave.m add the following method:

- (void)generateTiles
{
  for (NSUInteger y = 0; y < self.gridSize.height; y++) {
    for (NSUInteger x = 0; x < self.gridSize.width; x++) {
      CaveCell *cell = [self caveCellFromGridCoordinate:CGPointMake(x, y)];
      
      SKSpriteNode *node;
      
      switch (cell.type) {
        case CaveCellTypeWall:
          node = [SKSpriteNode spriteNodeWithTexture:[self.atlas textureNamed:@"tile2_0"]];
          break;
          
        default:
          node = [SKSpriteNode spriteNodeWithTexture:[self.atlas textureNamed:@"tile0_0"]];
          break;
      }
      
      // Add code to position node here:
      
      node.blendMode = SKBlendModeReplace;
      node.texture.filteringMode = SKTextureFilteringNearest;
      
      [self addChild:node];
    }
  }
}

The code above simply loops through the grid to build sprites based on the types of cells.

Note: This sets the blend mode to replace, because there is no alpha transparency in these cells. It also sets the filtering mode to nearest, which gives a nice pixel-art style.

To create the tiles, add the following code to generateWithSeed: in Cave.m, just after [self initializeGrid];:

[self generateTiles];

Build and run. You should now see the following, it's not much yet, but your knight is one step closer to adventure:

Positioning Tiles

The tiles were created based on the node count, but why can't you see them? They're stacked atop each other! Once you create a tile, you need to calculate the position for it in the cave. Take a look at this diagram.

At the top, row numbers begin at 0 and increase towards the bottom, while column numbers begin at 0 on the left and increase towards the right. Remember that the grid array is indexed by (row (y), column (x)). So you're not crazy and this tutorial was not written with a whiskey in hand, the grid is purposefully reversed.

As you see in the diagram, you need the size of a tile to calculate its position correctly. That is why you'll add a handy property to the Cave class to get the size. Open Cave.h and add the following property:

@property (assign, nonatomic, readonly) CGSize tileSize;

The property is read only; it will not change once a Cave instance generates.

Open Cave.m and add this method:

- (CGSize)sizeOfTiles
{
  SKTexture *texture = [self.atlas textureNamed:@"tile0_0"];
  return texture.size;
}

This returns the size of one of the tile textures in the cave's atlas, and assumes all are the same size. This is a fair assumption, considering how it builds tile maps.

Go to initWithAtlasNamed:gridSize: in Cave.m and add the following line of code after the line _gridSize = gridSize;:

_tileSize = [self sizeOfTiles];

Next, you need to create a new method to do the actual calculation of the tile position. Add this new method to Cave.m:

- (CGPoint)positionForGridCoordinate:(CGPoint)coordinate
{
  return CGPointMake(coordinate.x * self.tileSize.width + self.tileSize.width / 2.0f,
    (coordinate.y * self.tileSize.height + self.tileSize.height / 2.0f));
}

As you see, the calculation in this method corresponds to the calculation illustrated in the diagram above. It simply multiplies the given x and y coordinates with the tile's width and height, respectively.

You add half the tile's width and height to those values because you're calculating the tile's center point.

The last step is to add the positioning to the tile upon creation. Go back to generateTiles and add this single line of code after the comment // Add code to position node here::

node.position = [self positionForGridCoordinate:CGPointMake(x, y)];

Build and run the game and use the joystick to move around the cave.

This isn't exactly a cave, is it? More like a giant wasteland. Why are there no walls?

[spoiler title="Solution"]initializeGrid initializes every cell it creates as a floor tile.[/spoiler]

The Initial Seed

Now that the boilerplate code is in place to manage the grid and tile creation, you can safely move on to implementing the first step in the cellular automaton creation: the initial distribution of cell states.

You're going to start by randomly setting each cell to be either a wall or a floor. You'll want to tweak the chance of a cell becoming either a wall or a floor during the cave generation, so, you add the following property to Cave.h:

@property (assign, nonatomic) CGFloat chanceToBecomeWall;

The value of chanceToBecomeWall will be in the range of 0.0 to 1.0. A value of 0.0 means all cells in the cave will become floors, and a value of 1.0 means all cells in the cave will become walls.

Inside Cave.m, set the default value of chanceToBecomeWall to 0.45 by adding the following code to initWithAtlasNamed:gridSize: after the line that initializes _tileSize:

_chanceToBecomeWall = 0.45f;

This will mean that there is a 45% chance that a cell become a wall. Why 0.45, you might ask? This value comes from good, old fashioned trial-and-error, and it tends to give satisfactory results.

You'll need to generate random numbers quite a few times during cave generation, so add the following method to Cave.m:

- (CGFloat) randomNumberBetween0and1
{
  return random() / (float)0x7fffffff;
}

This method returns a value between 0 and 1. It uses the random() function, which needs to be seeded before use. This should only happen once per cave generation, so add the following line in generateWithSeed:, just before the line that calls initializeGrid:

srandom(seed);

At the moment, all cells in the cave are floors, but it won't always be a two-dimensional environment. You need to take into account the fact that some cells will become a wall or a floor by modifying initializeGrid.

Inside initializeGrid in Cave.m, replace the line cell.type = CaveCellTypeFloor; with the following line of code:

cell.type = [self randomNumberBetween0and1] < self.chanceToBecomeWall ? CaveCellTypeWall : CaveCellTypeFloor;

Instead of defaulting every cell to be a floor, each cell gets a type based on the value returned by the random number generator, taking into account the chanceToBecomeWall property.

Time to see the fruit of your labor thus far. Build and run, and you should now see the following:

Try moving around using the joystick. Not very cave-like, is it? So, what's next?