Compression in Full Quiet
Compression in Full Quiet
By Pino on 2024-04-25 in Retrotainment
How does Retrotainment Games' Full Quiet squeeze a vast open world into an NES cartridge half a megabyte in size? It uses several layers of compression to squash the world as flat as a pancake.
🌎️ + 🗜️ = 🥞️
Mmm... pancakes
Data compression refers to transformations on repetitive data to reduce the storage size while allowing the original data to be recovered, either exactly or approximately. It allows a large adventure to be stored in a program cartridge of modest capacity. The engine of Full Quiet takes advantage of various forms of repetition to store its world in what by 2020s standards is a tiny storage medium.
Text compression: DTE 🔗
Look at the repetition in the following 27-character string of text:
the fat cat sat on the mat
The 3-character sequence at , including the trailing space, appears four times in the string. We can replace it with a shorter code and store what the code expands to. This definition consists of the abbreviation @, the expansion at , and a symbol to mark the end of the expansion |. It totals 5 characters: @at |.
Adding the definition and the compressed text produces a 24-byte string:
@at |the f@c@s@on the m@
The sequence the likewise appears more than once. However, if we were to add another definition # that expands to the , that wouldn't save any bytes because we'd still need to store the definition.
@at |#the |#f@c@s@on #m@
Text compression doesn't work well with a single sentence in isolation. It works better with a longer text, where each entry in the dictionary represents something that appears much more often.
Much of the text in Full Quiet is compressed, including radio transmission dialogue, the "subtunnel" text during a dream, occasional dialogue with Pap, and the credits. This uses a codec called DTE, or "digram tree encoding", which has also been called "digram coding", "dual tile encoding", or "byte pair encoding" in various sources. DTE turns the 128 most common sequences of 2 characters into a reference to that pair. Because ASCII uses only code units 0 through 127, this leaves the rest of the byte range (128 through 255) for references. The "tree" part comes in when one or both of each pair of characters is itself a reference to another pair earlier in the dictionary.
The dictionary takes 256 bytes to store 128 pairs. The first 37 pairs might be as follows:
128: "E "<br>129: "TH"<br>130: "S "<br>131: "T "<br>132: "IN"<br>133: "ER"<br>134: "OU"<br>135: "AN"<br>136: "D "<br>137: "ON"<br>138: "TO"<br>139: "LL"<br>140: "RE"<br>141: " ",129 ; that is, " TH"<br>142: ". "<br>143: "Y "<br>144: "ST"<br>145: "EN"<br>146: "Y",134 ; that is, "YOU"<br>147: 132,"G" ; that is, "ING"<br>148: "RI"<br>149: " H"<br>150: ".."<br>151: " W"<br>152: " S"<br>153: "OW"<br>154: "I",130 ; that is, "IS "<br>155: " C"<br>156: "LA"<br>157: "OR"<br>158: "HA"<br>159: " B"<br>160: " A"<br>161: "CH"<br>162: "IT"<br>163: 129,128 ; that is, "THE "<br>164: "'",130 ; that is, "'S "
With this dictionary, the string PULL THE ORANGE RING (20 bytes) can be encoded as PU GR (11 bytes). (The notation denotes a reference byte.) Replacing each reference with its definition, such as with LL, results in PULL ORANGE RG, which in turn expands to PULL THE ORANGE RING.
This method compresses the 21 transmissions, 17 subtunnels, 2 Pap dialogue scripts, and the credits from 12,704 bytes to 7,822 bytes with the dictionary included, a savings of 38 percent. There exist other, stronger methods of text compression. Many of them rely on building a dictionary in RAM, something a personal computer has quite a bit of but the NES does not. We chose DTE because it is relatively quick to decode with a dictionary in ROM.
Indexed color 🔗
Duwago, a common enemy, with the index of each dot making it up
Modern computers usually operate in a 24-bit color space. Each dot has 8 bits for red level, 8 bits for green level, and 8 bits for blue level. Full Quiet has a total of 238 different maps, covering 77,418,496 dots. Each map has daytime, evening, and night. If it stored the exact color of each dot, that would total over 232 megabytes per daypart, or over 696 megabytes in total.
The 52 colors that an NES PPU produces, each with a hexadecimal code from 00 to 3F
The NES PPU can't even generate all those colors. It can generate about 52 different colors. This lets us reduce the colors from 24 bits to 6 bits, or 58 megabytes per daypart, or 174 megabytes in all. For each area, we also store a palette translation table that maps each day color to its corresponding evening and night colors. These tables total 351 bytes, letting us store only the images for the day.
Plateau lookout in day, evening, and night
We use no more than 16 of the 64 colors in each map. Each map has a palette that maps indices 0-15 to PPU color codes 00 to 3F, and this can be packed into 10 bytes per map or 2380 bytes in total. Using a palette lets us store 4 bits per pixel instead of 6, and the daypart palette translation operates on this palette,...