How did Satoru Iwata compress Pokemon GS to fit two regions on a single cartridge?

Question

Satoru Iwata's story of saving the development of Pokemon Gold & Silver by compressing its assets to fit on the GameBoy Color cartridge is something of a legend. Iwata optimised the game so much that GameFreak was even able to include two whole regions in the game.

However, when I was looking around, the story is bereft of details of exactly how Iwata was able to do so. Is there any speculation of how Iwata was able to do this?

Answer 1

The code for the decompression system has been decompiled and partially commented here.

Essentially the compression used is a form of run-length encoding, with a few modifications to make it more efficient for Gameboy graphics.

The main improvement is that graphics are split into bitplanes rather than being compressed as single bitmaps. That is, each pixel has a 2 bit value (one of four possible shades of grey), and rather than store them together (121212) the first and second bits are stored separately (111222). This has the advantage of making larger runs of same bits.

Answer 2

According to the Iwata Asks for G/S, Iwata created compression tools for the graphics in G/S (as well as other parts of other Pokémon games).

Morimoto: What's more, there were the tools for compressing the Pokémon graphic code…

Iwata: Ah yes, the compression tools.

Morimoto: You were kind enough to create those tools.

Iwata: Yes. (laughs) Well, I had heard from Ishihara-san that you’d been rather concerned about it.

Morimoto: At that point, we got a little carried away and were making all sorts of demands, saying: “This part isn’t quite right – do you think you could fix it?” We had some nerve to be making those requests to a company president… (laughs)

Iwata: Well, I was willing to do whatever I could! (laughs)

If he had produced an outrageous last minute save-the-day bit of unusual, cutting-edge compression that allowed them to include the other region, I expect they would have mentioned it in the article. From the text, it seems more likely that Iwata contributed to a lot of varying things across the games, and as the subject of compressing graphics came up in a meeting for G/S, he knew he could produce something of use in the timeframe available to help keep the momentum of the project going*.

Given the era, this would most likely have taken the form of a C, C++ or Pascal** command-line program that takes in graphics and some text data and spits out compressed blocks with symbol annotations together with some Z80 decompression routines that could be put into the ROM. Either that would integrated be in a huge project build script to make the full ROM stage-by-stage with all its assets, or a more ad-hoc 'we've converted this, now copy pokemon.dat into this folder...' arrangement.

Looking at reverse engineered ROM maps of Red/Blue and Gold/Silver, Gold/Silver is 2Mbyte and Red/Blue is 1Mbyte, so there would be a little extra space for the new region too!

I've heard claims that Red/Blue contain a more heavily unusual and cryptic compression method than Gold/Silver.

--

To work out what effect a new compression algorithm could have, as a back of the envelope calculation, let's consider the battle images of the Pokémon:

• Each Pokémon has a front and a back image consisting of an 8 by 8 grid of 8px*8px tiles at 2 bits-per-pixel, which is 8*8*8*8*2 = 8192 bits = 1024 bytes per Pokémon portrait. (2048 bytes considering the pair.)
• In this thread at pokecommunity.com, there's a list of the ROM addresses of every trainer and Pokémon battle portrait. Assuming the list is consecutive, taking a couple at random, we can see that a portrait is about 400 bytes compressed.
• 400/1024 = 39% of the original size. (Or alternatively a reduction of 61%.)
• There's 251 Pokémon in G/S, but there's 26 Unown so that makes 276 different party Pokémon, or 552 portraits total.
• 552 * 1024 = 565,258 bytes uncompressed.
• 552 * 400 = 220,800 bytes compressed.
• Difference = 344,448 bytes.

So as a calculated guess, just compressing all the Pokémon portraits recovers 1/3rd of a megabyte, which is a sixth of the whole cartridge. That's also ignoring the few dozen trainer portraits that are used the same as Pokémon in the battle scenes***. It's conceivable therefore that Iwata replaced some preliminary compression system and his contribution recovered anywhere between 1%-15% cartridge space through some improvement in the algorithm used in R/B.

(* or he could have been incredibly humble about it :) )

(** or perhaps a GUI, maybe even in VB)

(*** And there are lots of other kinds of graphics stored in other ways - tiles, attack graphics, menus, title screen.)

Edit - Given the information given by @user in the comment below, if the article is to be taken exactly - that Iwata only worked on G/S' compression, then either Iwata's contribution resulted in faster or more convenient or more reliable compression compared to their old tools saving in development time rather than space, or they compressed some other part of G/S that is different to R/B.