How Porytiles Works

Below is a whirlwind tour of the inner workings of the Porytiles compiler. In many places, I have simplified the data structures and compilation algorithm for purposes of explanation. E.g. I removed all the animation specific types/code from this tutorial, since it unnecessarily complicates the general thrust of the algorithm. It goes without saying that the actual source code is always the final word on how Porytiles works.

Compiler Inputs And Outputs

Porytiles makes use of quite a few custom types. We will first discuss the compiler's input and output types before outlining the general compilation algorithm. If you don't understand the types, you can't understand the algorithm. Check out include/types.h to see the type definitions in full detail.

Colors

Porytiles makes use of two different color formats, the 32-bit RGBA format and the 16-bit BGR15 format:

struct RGBA32 {
  std::uint8_t red;
  std::uint8_t green;
  std::uint8_t blue;
  std::uint8_t alpha;
};

struct BGR15 {
  std::uint16_t bgr;
};

The BGR15 format recognized by the Game Boy Advance hardware uses 5 bits for each of the blue, green, and red channels, respectively. The top bit is unused. Your tile assets, on the other hand, use RGBA32 format. This means that there will be precision loss when converting an RGBA color to a BGR color. Two unique colors in your RGBA tile assets may collapse into the same BGR color when compiled by Porytiles. This won't break your tileset, but it usually indicates an unintentional user oversight. Porytiles provides a warning to detect color precision collapse: -Wcolor-precision-loss. I suggest you enable it.

Input-Related Types

Porytiles uses two different raw tile types (raw as opposed to normalized tiles, which we will see shortly).

Raw RGBA32 tiles are represented as:

struct RGBATile {
  // Tiles are always 8*8, so 64 pixels
  std::array<RGBA32, 64> pixels;
};

RGBATiles are used to represent unprocessed image data, that is, the image data from your source tile assets.

Decompiled Tileset

struct DecompiledTileset {
  std::vector<RGBATile> tiles;
};

A DecompiledTileset is just a list of RGBATiles in a well-defined order. The Porytiles importer populates this structure by reading the source layer PNGs in Metatile Order. The compiler doesn't actually care about these semantics -- it just takes the list of source tiles and processes them into a compiled tileset, which includes a list of Assignments, in the order that they are given. It's the job of the importer and the emitter to worry about the ordering of inputs and outputs.

Output-Related Types

struct GBATile {
  std::array<std::uint8_t, 64> colorIndexes;
};

GBA tiles are indexed, that is, each pixel is an 8-bit index into a particular palette. For Porytiles these indexes will always be valued between 0 and 15, since Porytiles is designed to work with overworld graphics which always use 4bpp tiles. GBATiles are the format ultimately written to the output tiles.png file.

(For the special case of -tiles-output-pal=true-color, Porytiles technically writes out a combination of the 4-bit GBATile pixel value with a 4-bit palette index to the 8-bit PNG pixel. But that is beyond the scope of this document.)

We'll also need a way to represent the data in metatiles.bin. Luckily that is pretty straightforward. metatiles.bin is simply a list of assignments, where a metatile is made of 12 total assignments, one for each subtile (assuming triple-layer). We define the assignment below like so:

struct Assignment {
  std::size_t tileIndex;
  std::size_t paletteIndex;
  bool hFlip;
  bool vFlip;
};

Here, tileIndex is the index into tiles.png and paletteIndex tells us which of the hardware palettes this assignment should use. Finally, we define some flip variables, since tiles.png will only contain the Normal Form of each unique tile.

Compiled Tileset

struct CompiledTileset {
  // this field will become tiles.png
  std::vector<GBATile> tiles;

  // this field will become palettes/*.pal
  std::vector<GBAPalette> palettes;

  // this field will become metatiles.bin
  std::vector<Assignment> assignments;
};

We haven't covered GBAPalette, but note that it is just an array of BGR colors that represents a final hardware palette.

Metatile Order

Metatile order, i.e. the order of a valid metatiles.bin, is metatile-wise left-to-right, top-to-bottom; layer-wise bottom, middle, top; subtile-wise left-to-right, top-to-bottom. So what the heck does that mean?

In the following diagram, each "metatile" is one 16x16 pixel square of your corresponding layer PNG. The squares labeled S0, S1, S2, and S3 are the 4 8x8 subtiles that make up your metatile. They are elsewhere referred to as the northwest, northeast, southwest, and southeast subtile, respectively. For the sake of example, assume your source metatile sheets are 2 metatiles tall.

BOTTOM.PNG

     Metatile 0                                          Metatile 7
-------------------                                 -------------------
|        |        |                                 |        |        |
|   S0   |   S1   |                                 |   S0   |   S1   |
|        |        |                                 |        |        |
|--------|--------|  .. (6 metatiles not shown) ..  |--------|--------|
|        |        |                                 |        |        |
|   S2   |   S3   |                                 |   S2   |   S3   |
|        |        |                                 |        |        |
-------------------                                 -------------------

     Metatile 8                                          Metatile 15
-------------------                                 -------------------
|        |        |                                 |        |        |
|   S0   |   S1   |                                 |   S0   |   S1   |
|        |        |                                 |        |        |
|--------|--------|  .. (6 metatiles not shown) ..  |--------|--------|
|        |        |                                 |        |        |
|   S2   |   S3   |                                 |   S2   |   S3   |
|        |        |                                 |        |        |
-------------------                                 -------------------

MIDDLE.PNG
Same as above...

TOP.PNG
Same as above...

Given the above diagram, we can restate metatile order in the following way:

bottom metatile 0 S0, bottom metatile 0 S1, bottom metatile 0 S2, bottom metatile 0 S3,
middle metatile 0 S0, middle metatile 0 S1, middle metatile 0 S2, middle metatile 0 S3,
top metatile 0 S0, top metatile 0 S1, top metatile 0 S2, top metatile 0 S3,

bottom metatile 1 S0, bottom metatile 1 S1, bottom metatile 1 S2, bottom metatile 1 S3,
middle metatile 1 S0, middle metatile 1 S1, middle metatile 1 S2, middle metatile 1 S3,
top metatile 1 S0, top metatile 1 S1, top metatile 1 S2, top metatile 1 S3,

....

bottom metatile 15 S0, bottom metatile 15 S1, bottom metatile 15 S2, bottom metatile 15 S3,
middle metatile 15 S0, middle metatile 15 S1, middle metatile 15 S2, middle metatile 15 S3,
top metatile 15 S0, top metatile 15 S1, top metatile 15 S2, top metatile 15 S3,

Algorithm

Now we will outline some key elements of the compilation algorithm, so you can understand how it works at a high level. Many of the code snippets here are C++ pseudocode, intended to give you the feel of the algorithm without bogging you down in minutiae. Check out compiler.cpp to see the full compilation algorithm in more detail.

An Aside On Normalization

Before we discuss the compilation algorithm, let's take a brief detour to cover normalization. The normalization process and its associated types are an important intermediate representation that helps the compile algorithm handle flips and color allocation.

Normalized Types

The normalization process is Porytiles's secret sauce (thanks to the genius ideas of mrgriffin). Let's take a look at what these normalized types are, and then we will discuss what they mean.

struct NormalizedPalette {
  int size;
  std::array<BGR15, 16> colors;
};

struct NormalizedPixels {
  std::array<std::uint8_t, 64> colorIndexes;
};

struct NormalizedTile {
  NormalizedPixels pixels;
  NormalizedPalette palette;
  bool hFlip;
  bool vFlip;
};

A NormalizedPalette is the collection of BGR-converted colors present in an source tile, with one additional constraint. The NormalizedPalette is constructed by iterating over the tile pixels in left-to-right, top-to-bottom order. Each unique encountered color is added to the NormalizedPalette, in order. This means that a NormalizedPalette has a well-defined order for any given source tile. Two identical source tiles will always map to identical NormalizedPalettes.

The NormalizedPixels for a tile are the indexes into a tile's NormalizedPalette, defined in left-to-right, top-to-bottom pixel order. Note that the NormalizedPalette of a given tile fixes its NormalizedPixels, such that two identical tiles with the same NormalizedPalette will always have the same NormalizedPixels. It is also important to understand that these values are relative to the NormalizedPalette. They will not necessarily match the pixel indexes for the final GBATile.

Finally, we have a NormalizedTile, which is a tile representation that is "normalized" via the NormalizedPalette and NormalizedPixels types. Additionally, a NormalizedTile contains some flags which specify if this tile is flipped in any way. We will see more on this below.

Normal Form Definition

Suppose we have some source RGBATile T. This tile can be flipped horizontally, vertically, or both, giving us T_h, T_v, and T_hv respectively. We define the normal form of T, a NormalizedTile called T_norm, using the following method:

Compute the NormalizedPalette for T, which fixes a value for its NormalizedPixels.
Compute NormalizedPalette (and thus NormalizedPixels) for T_h, T_v, and T_hv.
Find the minimum value of NormalizedPixels for T and all the flips, where the minimum is the smallest value according to the "lexicographic" ordering. This is the order given by C++20's spaceship operator (operator<=>).
The tile with the minimum value of NormalizedPixels becomes T_norm, the normal form of T. We set the flip bits for T_norm according to which version of T ended up having the minimized NormalizedPixels (it could be T itself, but it also could have been one of the flip tiles).

Thus the NormalizedPalette and NormalizedPixels for T_norm are the "canonical" NormalizedPalette and NormalizedPixels for T. Note that it is possible (and quite common) that the normal form of some tile T is one of the flips of T.

If you'd like to understand more about "lexicographic" ordering for arrays, please see the C++ documentation here: https://en.cppreference.com/w/cpp/container/array/operator_cmp

Step 1 - Normalize The Source Tiles

The first compilation step is to take the decompiled RGBATiles and transform them into NormalizedTiles. As part of this normalization process, we may end up with some repeat NormalizedTiles in our final vector. That's OK! We'll deal with those later.

// A convenience definition, we want to tag each tile with a unique integral index
using IndexedNormTile = std::pair<std::size_t, NormalizedTile>;

/*
 * Build indexed normalized tiles, order of this vector matches the decompiled iteration order.
 */
std::vector<IndexedNormTile> indexedNormTiles = normalizeDecompTiles(decompiledTileset);

normalizeDecompTiles here is doing a lot of work, but effectively it just follows the basic algorithm laid out in the Normal Form Definition section above. Please see the source code for more details on how this algorithm is actually implemented.

Step 2 - Build The Color Index Map

The next step is to build a map from each unique BGR color present in the source to a unique integer index. The process is fairly straightforward. If this is a secondary tileset, we start by carrying over the colors present in the paired primary set. Then we simply iterate over all the normalized colors and save each unique color we see into the map, incrementing an index as we go. The index range is between 0 and 240. 240 because we have 15 colors per palette (recall the first palette slot must be reserved for the transparency color), and 16 total BG palettes (in practice, none of the Generation 3 Pokémon games actually let you use all 16 BG palettes for overworld graphics).

/*
 * Map each unique color to a unique index between 0 and 240 (15 colors per palette * 16 palettes MAX)
 */
std::unordered_map<BGR15, std::size_t> colorIndexMap = getPrimarySetColorIndexesIfPresent();
colorIndexMap.insertAll(buildColorIndexMap(indexedNormTiles));

// A rough idea of what this function looks like
auto buildColorIndexMaps(const std::vector<IndexedNormTile> &normalizedTiles) {
  std::unordered_map<BGR15, std::size_t> colorIndexes;
  std::size_t colorIndex = 0;
  for (const auto &[_, normalizedTile] : normalizedTiles) {
    // i starts at 1, since first color in each palette is the transparency color
    for (int i = 1; i < normalizedTile.palette.size; i++) {
      const BGR15 &color = normalizedTile.palette.colors[i];
      bool inserted = colorIndexes.insert(std::pair{color, colorIndex}).second;
      if (inserted) {
        indexesToColors.insert(std::pair{colorIndex, color});
        colorIndex++;
      }
    }
  }

  /*
   * This error is merely a fail-early heuristic. I.e. just because a primary tileset passes this check does not mean
   * it is actually allocatable.
   */
  std::size_t allowed = (PAL_SIZE - 1) * config.maxAllowedPalettes;
  if (colorIndex > allowed) {
    throw;
  }

  return colorIndexes;
}

Step 3 - Match NormalizedTiles With Their ColorSets

First, let's take a look at the ColorSet:

using ColorSet = std::bitset<240>;

If you aren't familiar with std::bitset<N>, that's OK. Basically, it's just a giant array of N bits that we can easily access and toggle via its provided access functions. For example, we can do something like the following:

std::bitset<5> bitset1{}; // 0 0 0 0 0
std::bitset<5> bitset2{}; // 0 0 0 0 0

// set bit 0 to true
bitset1.set(0); // 0 0 0 0 1
// now set bit 3 to true
bitset1.set(3); // 0 1 0 0 1

// set bit 1 to true
bitset2.set(1); // 0 0 0 1 0

// We can OR two bitsets together to get a third, this will come in handy
std::bitset<5> bitset3 = bitset1 | bitset2;
// bitset 3 now looks like:
// 0 1 0 1 1

Now you might see where we are going with this. The colors present in a NormalizeTile's palette can be easily represented by a ColorSet, i.e. a std::bitset<240>. Since we have a map of unique colors to unique indexes between 0 and 240, each bit position can represent the presence of a particular color in our tile. Example diagram:

NormalizedTile 0 Color Set

Color Index: 239 238 237     7 6 5 4 3 2 1 0
Bit:           0   0   0 ... 0 1 1 0 0 1 0 1

NormalizedTile 0 contained the BGR colors at global index 0, 2, 5, and 6
Remember, these global indexes came from our color index map in Step 2

Let's look at a bit more pseudocode:

using IndexedNormTileWithColorSet = std::tuple<std::size_t, NormalizedTile, ColorSet>;

/*
 * Here, colorSets is a vector: this enforces a well-defined ordering so tileset compilation results are identical
 * across all compilers and platforms. A ColorSet is just a bitset<240> that marks which colors are present (indexes
 * are based on the colorIndexMaps from above)
 */
auto [indexedNormTilesWithColorSets, colorSets] = matchNormalizedWithColorSets(colorIndexMap, indexedNormTiles);

The matching process is fairly straight forward:

auto matchNormalizedWithColorSets(const std::unordered_map<BGR15, std::size_t> &colorIndexMap,
                                  const std::vector<IndexedNormTile> &indexedNormalizedTiles)
{
  std::vector<IndexedNormTileWithColorSet> indexedNormTilesWithColorSets;
  std::unordered_set<ColorSet> uniqueColorSets;
  std::vector<ColorSet> colorSets;
  for (const auto &[index, normalizedTile] : indexedNormalizedTiles) {
    // Compute the ColorSet for this normalized tile, then add it to our indexes
    ColorSet colorSet{};
    for (int i = 1; i < normalizedTile.palette.size; i++) {
      colorSet.set(colorIndexMap.at(normalizedTile.palette.colors.at(i)));
    }
    indexedNormTilesWithColorSets.emplace_back(index, normalizedTile, colorSet);
    if (!uniqueColorSets.contains(colorSet)) {
      colorSets.push_back(colorSet);
      uniqueColorSets.insert(colorSet);
    }
  }
  return std::pair{indexedNormTilesWithColorSets, colorSets};
}

Now, every NormalizedTile is tagged with a ColorSet that represents its constituent colors. Additionally, we have a bare list of all the ColorSets, which we will use in the next step.

Step 4 - Assign All The ColorSets To Logical Output Palettes

For the purposes of this explanation, we'll focus on primary tilesets, but the process for secondary tilesets is very similar. See the code for details.

Now that we have a ColorSet for each NormalizedTile, we can try to find a palette configuration that allows for every tile to be represented by at least one logical output palette. We call it a logical palette because at this stage, the colors don't have their final palette indexes.

The first step is to initialize a blank ColorSet for each logical output palette. In pokeemerald, primary tilesets can use six output palettes. So we'll initialize six ColorSets, which initially look like:

Output Palette 0 Color Set

Color Index: 239 238 237     7 6 5 4 3 2 1 0
Bit:           0   0   0 ... 0 0 0 0 0 0 0 0


Output Palette 1 Color Set

Color Index: 239 238 237     7 6 5 4 3 2 1 0
Bit:           0   0   0 ... 0 0 0 0 0 0 0 0

.
.
.

Output Palette 5 Color Set

Color Index: 239 238 237     7 6 5 4 3 2 1 0
Bit:           0   0   0 ... 0 0 0 0 0 0 0 0

Now, we can begin the assignment. The algorithm uses recursive backtracking to find the first viable solution. The general process is:

Check if our unassigned ColorSet stack is empty. If so, we have found a solution!
Pull an unassigned ColorSet s from our stack.
Sort the output palettes according to a couple heuristics, more details below.
Assign s to the first of the sorted palettes, if that palette has enough room. Otherwise, go to step 5.
Recurse down a level and go back to step 0. Pass into the recursive call:
1. an updated slate of output palettes, one of which contains the new assignment
2. an updated list of unassigned ColorSets with s removed
If we get here, that means our recursive branch from step 4 did not have a solution. So try the next sorted palette and repeat step 4.
If we exhaust all the sorted output palettes, then this branch had no solutions and we must bubble back up.

Step 2 above referenced a couple of sort heuristics. Those heuristics are:

The algorithm will always first try to place a ColorSet into a palette that shares the most colors with that ColorSet
If two different palettes have the same intersect size, we break the tie by choosing the palette with the fewest assigned colors so far

In the future, we may add optimization flags that change the assignment heuristics. Also, if the algorithm takes too long without finding a solution, it will bail the entire assignment and generate a compilation error. This threshold can be adjusted with the -assign-explore-cutoff option, but the default setting should be sensible for most cases.

For the nitty-gritty details of this process, check out the code in palette_assignment.cpp. You'll notice that this process is a bit more complicated than I let on here. In addition to the depth first search algorithm described above, Porytiles also has a breadth first search implementation which it may decide to use. Additionally, the palette assignment may run multiple times until Porytiles finds a valid combination of parameters that can successfully assign your ColorSets.

Step 5 - Transform The Logical Output Palettes Into Hardware Palettes

Now that we have successfully assigned each ColorSet to a logical output palette, we need to convert those palettes to hardware output palettes. We call these hardware palettes because these represent the final palettes that get loaded into the GBA's palette memory. In a hardware palette, each color has a well defined index, with index 0 reserved for the transparency color. Below is the basic pseudocode of the algorithm.

// Iterate over each hardware palette i
for (std::size_t i = 0; i < numPalettesInPrimary; i++) {
  // Grab logical output palette i
  ColorSet palAssignments = assignedPalsSolution.at(i);
  // Set the first hardware palette slot as transparency, 'compiled' is the CompiledTileset
  compiled->palettes.at(i).colors.at(0) = rgbaToBgr(transparencyColor);
  // variable to track current index in hardware palette
  std::size_t colorIndex = 1;
  // Iterate over each of the 240 bits in the ColorSet corresponding to logical output palette i
  for (std::size_t j = 0; j < palAssignments.size(); j++) {
    // If bit j is set, push the color at global color index j into the hardware palette
    if (palAssignments.test(j)) {
      compiled->palettes.at(i).colors.at(colorIndex) = indexToColor.at(j);
      colorIndex++;
    }
  }
  // set logical size of hardware palette
  compiled->palettes.at(i).size = colorIndex;
}

Step 6 - Build The Tile Assignments

The last step is to construct the actual assignments, that is, the tiles and assignments fields of our CompiledTileset. We'll iterate over our original indexed NormalizedTile vector, but this time with each tile tagged with its ColorSet. The basic assignment algorithm looks like:

For each [index, normalizedTile, colorSet]:
Find which palette index matches this tile, by checking colorSet against each logical output palette (recall that both operands here are bitsets, so we can easily check which logical output palette is a super-set of colorSet)
Take the normalizedTile and the palette index computed in step 2, and compute a GBATile by comparing the colors in the normalizedTile's palette to the colors in the hardware palette at the given palette index. See makeTile in compiler.cpp for the full implementation.
If this normalizedTile was not seen before, insert it to the tiles field. If we have seen it before, the insert will fail. Either way, the insert operation will return the index of this tile in the tiles field. So we save off that index.
Create an Assignment using the palette index from step 2, tile index from step 4, and the normalizedTile's hFlip and vFlip fields. Add this assignment to our assignments vector.

Again, check compiler.cpp for more details, specifically the assignTilesPrimary function.

Thanks For Reading!

I hope you now have a better idea of how Porytiles works. As I said at the top of the page, the final word on the inner workings of Porytiles is the actual source code. Feel free to dive in, armed with the knowledge you gained in this tutorial!

To wiki home page.

To project home page.