Design Patterns and Video Games

OpenGL 2D Facade (20): Automatic tile borders

I add more game content in this post to test the facade. This time, I want to automatically render borders when a region is updated.

Objective

We still edit a region as before, but now the renderer displays borders between cells of a different kind:

Note that it is the renderer that updates the display: the game state does not contain any data about these borders. In other words, the region's values in the game state are only the cell kind (grass, swamp, dirt, etc.) and the corresponding values in the renderer are one of the many possible tiles.

This approach is interesting because we don't introduce unnecessary complexity in the game state. When we consider game logic, the only information we need is the kind of region cell. For instance, if we are on the grass, elves can get a bonus, and orcs a malus. We don't need to know if the region cell is a top-left or bottom-right border.

Automatic borders

Automatic borders convert a binary map (foreground/background) into a map with tile borders:

Automatic tile borders

From neighborhood to tile

The choice of tile borders depends on the values of the surrounding cells. In this post, we consider height cells around the center at (0,0):

8-cell neightborhood

The following presents an example, where we choose a bottom-right green/blue corner:

Automatic tile borders

From binary mask to code

A naive approach consists of enumerating all the possible combinations. Since we have heights neighbors and two possibilities per cell, we have a total of 256 combinations.

Handling these combinations in a huge if/elif statement would be long to implement and very slow to execute. A usual approach proposes computing a code for each combination and then using a lookup table to get the tile quickly.

To compute this code, we assign a weight for each cell (a power of 2 from 1 to 128):

Then, we convert each foreground cell to a 1 and each background cell to a 0. With the previous example, it leads to the following binary mask:

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+8+32=43.

Finally, using a dictionary that maps a code to tile coordinates, we get the desired border. This dictionary can look like this one:

code2tile = {
    # Code 0
    # 000
    # 000
    # 000
    0: [0, 0],

    # Code 1
    # 000
    # 000
    # 000
    1: [0, 0],

    # Code 2
    # 000
    # 100
    # 000
    2: [3, 0],

    ...

Redundant codes

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

Automatic tile borders: redundant codes

The redundant cases appear when there is a one in a corner and a zero next to it. In the top combination in the example above, the northwest cell is not neighbored by cells of the same color. As a result, this northwest cell does not influence the choice of the border tile. In other words, we can choose the same code as the second combination in the example, where the northwest cell is blue.

For those who better understand logics with code, here are the tests to run to eliminate all redundant combinations:

if mask[0, 0] and (not mask[0, 1] or not mask[1, 0]):
    mask[0, 0] = 0
if mask[0, 2] and (not mask[0, 1] or not mask[1, 2]):
    mask[0, 2] = 0
if mask[2, 0] and (not mask[1, 0] or not mask[2, 1]):
    mask[2, 0] = 0
if mask[2, 2] and (not mask[1, 2] or not mask[2, 1]):
    mask[2, 2] = 0

The mask variable is a 2D Numpy array where mask[i,j] is 1 if the cell at coordinates (i,j) is in the foreground. Each test sets a corner to zero if ones do not surround it.

More than two region types

The previous approach works fine as long as we have two region types. If we apply this to more region types, strange results appear.

When considering a type as the background and another as the foreground, we make an essential assumption:

Automatic tile borders: background and foreground

For a given mask, there are two possibilities. In the example above, there is a single dark cell surrounded by light cells. If we consider the dark green color as the foreground, we get a small dark green area (a). If we consider the light green color as the foreground, we get a larger dark green area (b). Both cases are correct, and the choice for one is arbitrary.

We could imagine heuristics to automatically choose what is in the foreground and what is in the background, and thus manage all cases. For instance, we could choose the background based on the most frequent color. Unfortunately, it leads to inconsistent results. In the example above, this rule leads to strange borders, where sometimes the light cells are in the background and sometimes not (c).

A solution I propose is to order all regions kinds, for instance:

grass < swamp < dirt < sand < dead land

It means that "grass" is the background of all others, "sand" is the background of all but "grass", and so on.

It works fine as long as we have tile borders between any background/foreground combinations. For instance, we need "grass"/"swamp" tile borders but not "swamp"/"grass". These tiles are easy to create if we have the 48 tile borders for each kind on a transparent background. Then, we only need to paste these tiles on the "no-borders" tile of another kind.

This solution does not handle all cases but is sufficient for drawing large regions: try the program and experiment!

Implementation

Most of the code is as before, except for the regionCellChanged() method of the EditGameMode class:

def regionCellChanged(self, state: State, regionName: str, x: int, y: int):
    if regionName != self.__currentRegionName:
        return
    assert self.__groundLayer is not None

    region = self.__currentRegion
    for j in range(3):
        for i in range(3):
            xp = x + i - 1
            yp = y + j - 1
            self.__updateRegionTile(region, xp, yp)

Remind that we call this method when a region cell has changed, for instance, in the SetGroundValueCommand class.

It calls a new updateRegionTile() private method that computes a tile considering its neighborhood:

def __updateRegionTile(self, region: Region, x: int, y: int):
    if x < 0 or x >= region.width or y < 0 or y >= region.height:
        return

    neightbors = region.getGroundNeightbors(x, y)
    value = neightbors[1, 1]
    otherValue = min(value, neightbors[1, 0], neightbors[1, 2], neightbors[0, 1], neightbors[2, 1])
    if otherValue == value:
        otherValue = neightbors.min()

    tilesetLocation = self.groundTilesetLocations[value, otherValue]
    tileX = tilesetLocation[0] * 8
    tileY = tilesetLocation[1] * 6
    if value == otherValue:
        tileX += 6
        tileY += 1
    else:
        mask = neightbors != otherValue
        if mask[0, 0] and (not mask[0, 1] or not mask[1, 0]):
            mask[0, 0] = 0
        if mask[0, 2] and (not mask[0, 1] or not mask[1, 2]):
            mask[0, 2] = 0
        if mask[2, 0] and (not mask[1, 0] or not mask[2, 1]):
            mask[2, 0] = 0
        if mask[2, 2] and (not mask[1, 2] or not mask[2, 1]):
            mask[2, 2] = 0
        powers = np.array([1, 2, 4, 8, 0, 16, 32, 64, 128], dtype=np.int32)
        code = (mask.flatten() * powers).sum()

        shift = self.code2tile[code]
        tileX += shift[0]
        tileY += shift[1]

    self.__groundLayer.setTile(x, y, tileX, tileY)

Line 5 calls a new getGroundNeightbors() commodity method of the Region class. It returns the cell values of the nine cells around the one at (x, y). The returned object is a 3x3 Numpy array, where the center corresponds to the cell at (x,y).

Line 6 saves in value the cell value at (x, y).

Line 7 computes the smallest value between the center and four directions (north, south, east, and west). This computation aims to choose what we can consider as the background, value being the foreground. We assume a default ordering of the ground kinds to get a consistent result, whatever the combinations.

Lines 8-9 handle the case where the four directions are as the center value, in which case we consider all the neighbors to choose a background.

Line 11 uses the groundTilesetLocations static attribute to get the sub-tileset coordinates with all the borders between value and otherValue.

Lines 12-13 convert the sub-tileset coordinates into tile coordinates (each sub-tileset has 8x6 tiles).

Lines 14-16 handle the case where there is no border.

Lines 18-28 compute the code of the tile to render.

Lines 30-32 use the code2tile static attribute that converts a code (a value between 0 and 255) to tile coordinates in a sub-tilesets (between (0,0) and (7,5)).

Line 34 sets the tile in the ground layer. Remind that the renderer records all the tiles to render. Once we set a tile, we no more need to update anything to keep it drawing.

Final program

Download code and assets

In the next post, I'll show how to update shaders based on the current layer.