1 / 1000th of a Picture

Hello! In our ongoing effort to replace temporary systems with more solidly designed ones, I recently converted all player-visible text in Backworlds to Unicode and as a result was forced to rethink how the font rendering works. We do not have a lot of text in Backworlds, practically none in the game itself, but the text that is needed for menus is all the more important.

For a short background, most programming, scripting and markup can be done (and subsequently is) with ASCII,  a character map where every character is represented by a number from 0 to 127 and thus fits within a single byte. Unicode, on the other hand, is made to allow anyone to use a computer regardless of language and for that purpose it supports over 1.1 million different characters. There are several different ways to encode Unicode strings, we chose to use UTF-8 which essentially works by using ASCII and having any characters over the 127 index set the high bit and use several bytes to represent the index instead of just the one. This keeps the strings compact in memory, and has the added benefit of making sure any ASCII-encoded string is also a valid Unicode encoding so we did not have to change any existing string data.

For some historical context around Unicode I recommend reading Joel Spolsky’s Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets post, and for a more hands-on description of how the format looks, where the characters reside and what exceptions there are I recommend Nathan Reed’s Programmer’s Introduction to Unicode.

While Unicode is a necessity for localized games – something we want to keep ourselves open to – and having access to the entirety of human written expression is nice, it does create something of a problem for rendering text. Previously we had used an old-school solution of building a map with every ASCII character in it, and then rendering every letter individually in an overlapping fashion. This was not feasible for a project where we could potentially use thousands of different characters.

One possible solution to this would be to simply parse all the text displayed in the game and render only the characters used to a character map instead of every possible one, but I instead opted to keep a cache for rendered strings around and simply render them when they are needed. We use Sean Barrett’s  stb_truetype for text rendering, like his other code it is public domain and very easy to use. There is a slight performance hit to re-rendering a string – we do not show text in any performance-critical areas of Backworlds so hitching is not a major concern for us, but if it would become one it would be a simple matter to pre-process the strings before entering a menu page.

Since we do not have a lot of text, only a single texture is used for the text cache and it is divided into a fixed number of equally-sized rows. When we need to render a string, we first check if that string rendered with the given size and font already exists in the map, otherwise we go through steps to figure out the best place to render it while keeping as much of the texture in use as possible;

  1. See if any text lines using the same amount of rows as the string can fit the new string at the end
  2. See if a new line can be created that would fit the string
  3. See if any text lines using more than the amount of rows as the string can fit the new string
  4. Check all strings that exceed the width of the new string and use the same amount of rows, remove the oldest one to make place for the new one
  5. If we still have no place for the new string (for instance, if the entire texture is populated by small or short strings and we need to enter a large one), clear out all the strings on enough rows in sequence to make place for a new row with the string. The rows that are to be removed are determined by the age of the most recent-used string that would be removed.

We could probably pack strings more tightly using a binpacker as described in my notes on content optimization from a while back, but this kind of structure is overly complex for the common case in font rendering where a lot of strings have the same font size and height. It is also more complex to figure out how to remove multiple blocks when rendering large new strings, and as such is more suitable for immutable data.

There are additional optimizations we could do – better heuristics for font usage and evaluating more areas for space, but these are more than enough for the cases we encounter in Backworlds.

In addition, I would recommend watching Anna Kipnis’ presentation on Dialog Systems in Double Fine Games, it treats dialogue broadly rather than just text and has some really good ideas in there.

Also, if you are interested in dialogue systems in games, Campo Santo gave a talk about the Dialog System in Firewatch last year with some more interesting insights, the video recording is part of GDCVaults exclusive content still but the slides and notes are available for free.

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.