The creation of a tileset for large character sets uses a lot of memory. This post shows an approach based on the Flyweight pattern to allow their usage with minimal memory footprint.

This post is part of the OpenGL 2D Facade series

Objective

The objective is similar to the previous one, except that we want to draw characters from large sets, possibly more than 10,000 characters:

With the previous approach, with 10,000 characters and tiles of 29 per 64 pixels, a tileset uses at least 74MB. Even if we save some memory using tricks (like using a single channel rather than four), it is still large. Furthermore, it is for one size and style: we have to create more tilesets for other sizes and styles (bold, italic, shadowed, etc.).

Thanks to this post's approach, we can create tilesets that only contain the characters we need for the current frame. It is unlikely that a frame has all the characters of a large set, and in usual cases, it is a tiny subset.

In the example above, the program creates the following tileset:

Dynamic tileset generator

We create a new class TextTileset that delivers instances of CharacterTile for any character. These instances contain the coordinates (x1, y1, x2, y2) of a tile in the tileset:

We must first initialize an instance of TextTileset with the setFont() method. Its arguments are as in the facade. Internally, it calls the resize() method to create an empty tileset.

Then, every time we have to draw characters, we first call the getCharacters() method to ensure that the characters are in the tileset. If it updated the tileset, it returns True, and we should call the toNumpyArray() method to get this new tileset in Numpy format, ready to be sent to the GPU.

Once the tileset is ready, the user can call the getCharacterTile() method to get the tile coordinates for a given character. These coordinates are pixel coordinates. They are not necessarily aligned on a grid, and tiles can be anywhere in the tileset.

This design is close to a standard Flyweight pattern since the getCharacterTile() method returns objects that share the same memory (actually, the tileset). The main difference is the dynamic behavior of this memory (the tileset) and the need to send it to the GPU.

Anyway, note that the implementation of these classes does not depend on OpenGL. We only use Pygame to draw the characters and create the tileset. Thus, you can use it in another context with or without OpenGL.

TextTileset implementation

Initialization

The setFont() method initializes the tileset for a given font:

def setFont(self, fontName: str, tileHeight: int, color: (int, int, int)):
    fontSize = int(tileHeight * 1.3)
    for iterations in range(100):  # Up to 100 tries
        font = pygame.font.Font(fontName, fontSize)
        surface = font.render("M", False, color)
        if surface.get_height() == tileHeight:
            break
        elif surface.get_height() > tileHeight:
            fontSize -= 1
        else:
            fontSize += 1
    self.__font = font
    self.__color = color
    self.__tileDefaultWidth = surface.get_width()
    self.__tileDefaultHeight = surface.get_height()
    self.__characterTiles = {}
    self.__resize(256, 256)

Lines 2-11 try to find the font with the closest required tile height. It also estimates the largest tile width.

We save the best font in the font attribute (line 12), the color in the color attribute (line 13), and the tile default size in tileDefaultWidth and tileDefaultHeight (lines 14-15).

We initialize the character map (line 16), and create a first tileset image of 256 per 256 pixels (line 17).

Add missing characters to the tileset

The most interesting part of this implementation is in the addCharacters() method:

def addCharacters(self, characters: str) -> bool:
    tilesetUpdated = False
    for character in characters:
        if character in self.__characterTiles:
            continue
        if character == "\n":
            continue
        tilesetUpdated = True

        # Render the character
        surface = self.__font.render(character, False, self.__color)
        characterWidth = surface.get_width()
        if self.__tileDefaultHeight < surface.get_height():
            logging.warning("The height of character {} is higher than the default.".format(character))

        # Ensure that next tile location in inside the tileset
        if (self.__nextTileX + characterWidth) > self.__tileset.get_width():
            self.__nextTileX = 0
            self.__nextTileY += self.__tileDefaultHeight
        if (self.__nextTileY + self.__tileDefaultHeight) > self.__tileset.get_height():
            self.__resize(2 * self.__tileset.get_width(), 2 * self.__tileset.get_height())
            if (self.__nextTileX + characterWidth) > self.__tileset.get_width():
                self.__nextTileX = 0
                self.__nextTileY += self.__tileDefaultHeight

        # Blit the character in the tileset
        self.__tileset.blit(surface, (self.__nextTileX, self.__nextTileY))

        # Compute and save the tile location
        self.__characterTiles[character] = CharacterTile(
            self.__nextTileX, self.__nextTileY,
            self.__nextTileX + characterWidth, self.__nextTileY + self.__tileDefaultHeight
        )

        # Update tile next location
        self.__nextTileX += characterWidth
    return tilesetUpdated

It processes all characters of the input string (line 3).

If the character is already in the tileset (line 4) or if the character is a carriage return (line 5), there is nothing to do. If not, then we update the tileset and set tilesetUpdated to True. We return this variable to tell the user whether we updated the tileset.

Lines 11-14 render the current character:

surface = self.__font.render(character, False, self.__color)
characterWidth = surface.get_width()
if self.__tileDefaultHeight < surface.get_height():
    logging.warning("The height of character {} is higher than the default.".format(character))

We save the width of the rendered character in characterWidth. This new approach works with characters of variable width; we no more have to use monospaced fonts.

However, the height should always be the same, or in the worst case, below a maximum value. If it is not the case, we print a warning.

Lines 17-24 ensures that we have enough room for the current character:

if (self.__nextTileX + characterWidth) > self.__tileset.get_width():
    self.__nextTileX = 0
    self.__nextTileY += self.__tileDefaultHeight
if (self.__nextTileY + self.__tileDefaultHeight) > self.__tileset.get_height():
    self.__resize(2 * self.__tileset.get_width(), 2 * self.__tileset.get_height())
    if (self.__nextTileX + characterWidth) > self.__tileset.get_width():
        self.__nextTileX = 0
        self.__nextTileY += self.__tileDefaultHeight

Variables nextTileX and nextTileY contain the next possible character location in the tileset. This possibility depends on the width of the current character. If it is too large, it may not fit in the current row, so we go to the next one (lines 17-19). The next row could be outside the tileset, in which case we enlarge the tileset (20-21). In this new tileset, all characters have a new location, and the last character could be at the end of a row. Consequently, we could have to go to the next row (lines 22-24).

The end of the method blits the current character (line 27), saves its coordinates (lines 30-33), and moves the next location right after it (line 36):

# Blit the character in the tileset
self.__tileset.blit(surface, (self.__nextTileX, self.__nextTileY))

# Compute and save the tile location
self.__characterTiles[character] = CharacterTile(
    self.__nextTileX, self.__nextTileY,
    self.__nextTileX + characterWidth, self.__nextTileY + self.__tileDefaultHeight
)

# Update tile next location
self.__nextTileX += characterWidth

Resize the tileset

The resize() method creates a larger tileset, but also redraw all the current characters:

def __resize(self, width: int, height: int):

    # GPUs prefer square image size with a power of two
    def nextPowerOfTwo(x: int) -> int:
        return 1 if x == 0 else 2 ** (x - 1).bit_length()
    imageWidth = nextPowerOfTwo(width)
    imageHeight = nextPowerOfTwo(height)
    imageSize = max(imageWidth, imageHeight)
    self.__tileset = pygame.Surface((imageSize, imageSize), flags=pygame.SRCALPHA)

    # Copy current characters in the new tileset
    currentCharacters = "".join(self.__characterTiles.keys())
    self.__characterTiles.clear()
    self.__nextTileX = 0
    self.__nextTileY = 0
    self.addCharacters(currentCharacters)

As explained previously, the GPU prefers texture image size with a power of two. Lines 4-8 compute the minimum size that satisfies this constraint.

Line 9 creates the surface with an alpha channel.

Line 12 saves the current characters. The join() method of the str Python class turns all characters of a list into a single string.

Lines 13-15 reset the character tiles and next location.

Lines 16 uses the addCharacters() method to add the current characters to the new tileset.

Convert to Numpy array

The toNumpyArray() method converts the Pygame surface to a Numpy array:

def toNumpyArray(self) -> np.ndarray:
    imageArray = np.zeros((self.__tileset.get_width(), self.__tileset.get_height(), 4), dtype=np.uint8)
    imageArray[..., 0] = pygame.surfarray.pixels_red(self.__tileset)
    imageArray[..., 1] = pygame.surfarray.pixels_green(self.__tileset)
    imageArray[..., 2] = pygame.surfarray.pixels_blue(self.__tileset)
    imageArray[..., 3] = pygame.surfarray.pixels_alpha(self.__tileset)
    return imageArray.transpose((1, 0, 2))

Get the tile of a character

The getCharacterTile() method returns the tile coordinates for a given character:

def getCharacterTile(self, character: str) -> CharacterTile:
    return self.__characterTiles[character]

We could call the addCharacters() method to automatically add missing characters. The problem is that the user would not know if the tileset is updated. A solution is then to send the tileset every frame. It is inefficient since we need to update the tileset only a few times during the game.

Update of OpenGLTextLayer

Overview

We can simplity the OpenGLTextLayer class since all text generation is in the TextTileset class:

The tileset attribute refers an instance of a TextTileset class and the transparentTile attribute is an instance of CharacterTile (so four coordinates values x1, y1, x2 and y2).

The setQuadLocation() and setQuadTile() now has four coordinates pixel-based values since tiles can be anywhere and of any size in the tileset.

The new updateTileset() method updates the tileset and sends it to the GPU if needed.

Set the font

The setFont() method initializes the tileset:

def setFont(self, fontName: str, tileHeight: int, color: (int, int, int)):
    characters = \
        " !\"#$%&'()*+,-./" \
        "0123456789:;<=>?" \
        "@ABCDEFGHIJKLMNO" \
        "PQRSTUVWXYZ[\\]^_" \
        "`abcdefghijklmno" \
        "pqrstuvwxyz{|}~"
    self.__tileset.setFont(fontName, tileHeight, color)
    self.__updateTileset(characters)

In this version, it initializes the tileset with common characters to save some time during the game. It is not mandatory: you can reduce this character set to one space (e.g. characters = " "). We need this character to get a transparent tile.

Update the tileset

The updateTileset() method updates the tileset given a set of characters:

def __updateTileset(self, characters: str):
    # Add characters to the tileset
    if self.__tileset.addCharacters(characters):
        # The transparent could have changed
        self.__transparentTile = self.__tileset.getCharacterTile(" ")

        # Send the tileset to the GPU
        self.setTileset(
            self.__tileset.toNumpyArray(),
            self.__tileset.tileDefaultWidth,
            self.__tileset.tileDefaultHeight
        )

If the tileset is updated (line 3), then we update the transparent tile (line 5) and send the new image to the GPU (lines 8-12).

Set the text

The setText() method is as before, except that we update the tileset and use coordinates with four values:

def setText(self, x: float, y: float, content: str):
    if len(content) > self.maxCharacterCount:
        content = content[0:self.maxCharacterCount]

    # Update the tileset (only for new characters)
    self.__updateTileset(content)

    x0 = x
    # Characters to display
    for charIndex, character in enumerate(content):
        if character == "\n":
            x = x0
            y += self.tileHeight
            continue
        tile = self.__tileset.getCharacterTile(character)
        self.__setQuadTile(charIndex, tile.x1, tile.y1, tile.x2, tile.y2)
        self.__setQuadLocation(charIndex, x, y, x + tile.width, y + tile.height)
        x += tile.width

    # Remaining characters are transparent
    for charIndex in range(len(content), self.maxCharacterCount):
        self.__setQuadTile(charIndex,
            self.__transparentTile.x1, self.__transparentTile.y1,
            self.__transparentTile.x2, self.__transparentTile.y2
        )

Final program

Download code and assets

In the next post, we'll see how to add styles and effects on text.