Design Patterns and Video Games

2D Strategy Game (11): Automatic tiles

We continue to explore and illustrate the data view concept with the automatic selection of road and border tiles.

This post is part of the 2D Strategy Game series

The principle is similar to the one in the previous post: in the game data, we have a single (or few) cell types, and during the rendering, we select tiles to get better visuals. However, we don't randomly choose the tiles this time but use rules. For instance, there is a single cell value/id in the game state for rivers, while on-screen, there are many different tiles that connect the river cells:

4-connected tiles

We start with river and road tiles, which can connect to four neighbors: left, top, right, and bottom. Their coordinates, relatively to a center cell (0,0), are the following ones:

4-connected tiles: relative coordinates

Here is an example:

4-connected tiles: example

The game data is on the left: we found a road in the center, left, and top cells. Next, we want to choose a tile for the center cell: since there is a road to the left and the top, we select the tile that connects these two locations.

Binary mask and code. Since there are four neighbors and two possibilities per cell, we have 16 possible tiles:

all 4-connected tiles

It would be expensive to implement and slow to execute if we handle these combinations in a large if/elif statement. A usual approach proposes to compute a code for each combination and then use a lookup table to get the tile quickly.
To compute this code, we convert each road cell to 1 and each non-road cell to 0. With the previous example, it leads to the following binary mask:

4-connected tiles: mask

Then, we assign a weight for each cell (a power of 2 from 1 to 8):

4-connected tiles: weights

The code for a given mask is the sum of all weights where the mask has a 1. In the example, the code is 1+2=3.

Finally, we get the desired border using an array that maps a code to tile cell coordinates in the tileset. For example, this array can look like this one:

tilecodes4 = [
    (0, 0),  # Code 0
    (3, 0),  # Code 1
    (3, 3),  # Code 2
    (1, 2),  # Code 3
    ...

In the example, the tile is at tilecodes4[3] = (1, 2).

Note you can use this map, found in tools/tilecodes/tilecodes4.py in the attached program, with any 4-connected tiles as long as you distribute them in the way we did. Look at the tileset images in the assets/toen folder to see examples.

Implementation. To implement this feature, we first need to extract the cell values around a given cell. We add a new getNeighbors4() method in the Layer class that returns a tuple with four values:

def getNeighbors4(self, cell: Tuple[int, int]) -> Tuple[int, int, int, int]:
    x, y = cell
    w, h = self.__size[0] - 1, self.__size[1] - 1
    left = self.__cells[y][x - 1] if x > 0 else self.__defaultValue
    right = self.__cells[y][x + 1] if x < w else self.__defaultValue
    top = self.__cells[y - 1][x] if y > 0 else self.__defaultValue
    bottom = self.__cells[y + 1][x] if y < h else self.__defaultValue
    return left, top, bottom, right

We use a tuple because the number of neighbors is always the same (four), and in most cases, tuples run faster than lists, dictionaries, or variable names. So with the example above, it returns (307,307,X,Y), where X and Y are values different from 307 (= the value for a dirt road).

This method also handles layer edges and always returns a valid tuple. For instance, we pick the default value if the left cell is outside the layer (line 4). It is as if this default value surrounds the layer. The default value is the sea value for the ground layer, and for the others, it is none.

We create a new function mask4() in a new misc.tilecodes package dedicated to tile code computations. Given the neighbors and a value, it returns the corresponding binary mask:

def mask4(a: Tuple[int, int, int, int],
          value: int) -> Tuple[int, int, int, int]:
    return (a[0] == value, a[1] == value,
            a[2] == value, a[3] == value)

With the example above, it returns (1,1,0,0).

The function code4() computes the code of a mask:

def code4(a: Tuple[int, int, int, int]) -> int:
    return a[0] + 2 * a[1] + 4 * a[2] + 8 * a[3]

With the example above, it returns 3.

Finally, when we need to select a 4-connected tile, for instance, in the render() method of the ImpassableComponent class, we proceed in the following way for the river case:

neighbors = self.layer.getNeighbors4((x, y))
mask = mask4(neighbors, CellValue.IMPASSABLE_RIVER)
code = code4(mask)
rect = self.__river_code2rect[code]

We get the four neighbor values (line 1), compute the mask (line 2), then the mask (line 3). Finally, we retrieve the tile rectangle in the tileset (line 4). The river_code2rect array maps code to tile rectangles. We compute it in the getCode4Rects() of the Tileset class, which converts and shift the cell coordinates of the tilecodes4 array.

8-connected tiles

For the ground layer, we consider eight neighbors around each cell. It works pretty the same: we have relative coordinates around a center cell (0,0), and assign weights for each neighbor:

8-connected tiles: relactive coordinates and weights

Here is an example: neighbors (sea or ground), binary mask (Sea or other), selected weights, code (weights sum), and selected tile:

8-connected tiles: example

Foreground and background. Contrary to the previous case, we have to choose what is in the background and what is in the foreground. For the same game data, we can make two different choices:

8-connected tiles: foreground and background

We decided to add some ground in sea tiles in our game rather than the opposite. As a result, all ground tiles are always full: we don't plan to create navy units, so we better have more room for land units. This choice is purely visual; it has no impact on game logic.

Rendudant codes. Even if there are 256 codes, there are only 48 different cases. For instance, the two following combinations lead to the same border:

8-connected tiles: rendundant codes

The redundant cases appear when there is a one in a corner and a zero next to it. For example, in the first combination of the figure above, the top-left cell is not neighbored by cells of the same type. As a result, this cell does not influence the choice of the center tile. In other words, we can choose the same code as the second combination in the example.
The following convert any of a 256 possible codes into one of the 48 default codes:

mask = decode8(code)
mask = simplify8(mask)
code = code8(mask)

The decode8() function (line 1), defined in tools.tilecodes package in the attached program, converts a code into the corresponding binary mask. It uses usualy binary operations, like (code & x) // x with x a power of 2, x=2**k. It evaluates to 1 if bit k is 1, otherwise 0.

The simplify8() function (line 2) erases cells of a mask that do not affect the tile selection (like in the example above). Unfortunately, the implementation is not exciting and quite tricky.

The code8() function (line 3) computes the new code based on the simplified mak.

Random tiles. We still want to add randomness in the choice of sea and ground tiles. To get this result, we draw tile borders on top of full ones:

rects = tilesRects[value]
tileCount = len(rects)
rectIndex = self.noise[y][x] % tileCount
surface.blit(tileset, tile, rects[rectIndex])
if value == CellValue.GROUND_SEA:
    neighbors = self.layer.getNeighbors8((x, y))
    mask = mask8(neighbors, CellValue.GROUND_SEA)
    code = code8(mask)
    rect = self.__code2rect[code]
    surface.blit(tileset, tile, rect)

Lines 1-4 are the previous ones in the render() method of the GroundComponent class. It draws a ground or sea tile, depending on value. We randomly select one of the possible ground or sea tiles in each case.

If the current cell is a sea (line 5), we get the 8 neighbors (line 6), compute the binary mask sea/not sea (line 7), and the corresponding code (line 8). Finally, we draw the tile corresponding to the code (lines 9-10). Note that the code2rect maps the 256 codes to the rectangle in the tileset; we used code simplification when we built this array in the getCode8Rects() method of the Tileset class.

Connect different types of tiles

We can use the mask-based strategy to combine tiles of different types. For instance, we can connect dirt and stone roads:

neighbors = objectsLayer.getNeighbors4((x, y))
mask = mask4(neighbors, CellValue.OBJECTS_ROAD_DIRT)
mask = combine4(mask, mask4(neighbors, CellValue.OBJECTS_ROAD_STONE))
code = code4(mask)

We add line 3: it computes the mask for stone roads and combines it with the one for dirt roads. The combination in combine4() function ensures that if we find a road tile in one mask (or both), we always get a one in the final mask:

def combine4(
        a: Tuple[int, int, int, int],
        b: Tuple[int, int, int, int]) \
        -> Tuple[int, int, int, int]:
    return (a[0] or b[0], a[1] or b[1], 
            a[2] or b[2], a[3] or b[3])

We use the or logical operator: it returns zero if both values are zero and one otherwise.

We can connect more than two types and also types from different layers. For instance, for rivers in the impassable layer, we consider that they connect to mountains in the same layer, as well as sea tiles in the ground layer:

neighbors = impassableLayer.getNeighbors4((x, y))
mask = mask4(neighbors, CellValue.IMPASSABLE_RIVER)
mask = combine4(mask, mask4(neighbors, CellValue.IMPASSABLE_MOUNTAIN))
neighbors = groundLayer.getNeighbors4((x, y))
mask = combine4(mask, mask4(neighbors, CellValue.GROUND_SEA))
code = code4(mask)

Connect rivers to the sea with the directions trick

Concerning connected river and sea tiles, we need to draw a river flowing into the sea:

Connect river and sea tiles

It happens in the impassable layer when there is a sea tile below. If there is a river to the left, we draw a river flowing from the left. We also have to handle this in the other directions (top, right, and bottom). A naive implementation repeats four times the same code with different coordinates in each case. A better approach consists in using an enumeration that contains one direction and a tuple with all directions:

from enum import Enum
class Direction(Enum):
    LEFT = 0
    TOP = 1
    BOTTOM = 2
    RIGHT = 3
directions = (Direction.LEFT, Direction.TOP,
          Direction.BOTTOM, Direction.RIGHT)

Then, we extends the getValue() method in the Layer class. It has a new optional argument direction:

def getValue(self, coords: Tuple[int, int], 
      direction: Optional[Direction] = None) -> CellValue:
    x, y = coords[0], coords[1]
    if direction:
        if direction == Direction.LEFT:
            if x < 1:
                return self.__defaultValue
            return self.__cells[y][x - 1]
        if direction == Direction.RIGHT:
           ...

Thanks to this improvement, we can ask for a tile value next to one another. For instance, getValue(cell, Direction.LEFT) return the value to the left of cell. Furthermore, we handle world edges: if we ask for a cell that does not exist, we return the default layer value (lines 6-7).

Finally, we can handle all directions with a single loop:

for direction in directions:
    value = layer.getValue((x, y), direction)
    if value == CellValue.IMPASSABLE_RIVER:
        rect = self.__riverMouth[direction]
        surface.blit(tileset, tile, rect)

For each case, we get the value in the current direction (line 2). If it is a river (line 3), we get the corresponding tile (line 4) and blit it (line 5). The riverMouth attribute is a dictionary that maps a direction to a tile.

Final program

Download code and assets

In the next post, we introduce the minimap.