10 PRINT NES

Porting randomness

The 10 PRINT book is now available for purchase and download. Its full title is a single line of BASIC code, written for the Commodore 64, that generates a random maze pattern comprised of two PETSCII characters:

10 PRINT CHR$(205.5+RND(1)); : GOTO 10

The output looks something like this (in an emulator):

From those humble beginnings, the book’s ten (!) authors (writing in a single voice) explore computer platforms, programming, porting, labyrinths, random number generators, art history, and more. It’s great fun to dip into. And unless you’re some kind of weirdo, it’s worth checking out, since the PDF version is free to download. Moreover, buying the print version contributes to the PLAYPOWER charity. Don’t be a weirdo—check it out.

The book’s topic fascinates me for a number of reasons, but predominantly because I write about the Nintendo Entertainment System, which shares the same CPU core as the C64: the 6502. Despite this shared heart, the platforms are wildly different, dictated in part by their distinct uses. One is meant to be a personal computer while the other is a videogame console. Over the years, their purposes overlapped: the C64 was a great games machine, while the NES (and especially its older Japanese sibling, the Famicom) took on some PC tasks—BASIC programming, telecommunications, disk storage, etc.

Nonetheless, I thought it’d be a fun weekend project to port the single-line BASIC program to the NES, partly as a learning exercise (I’m not much of an assembly programmer, but I can get around) and partly as a means to draw out their platform differences. 10 PRINT has a nice section called ‘What Porting Reveals,’ that outlines the motivations behind such a project:

Porting a program is always an act of translation and adaptation. As such, porting reveals what in a program is particular to its source context, suggests many potential approaches to what is essential about the program, and explores how that essence may be portable to a specific target context. Each port is unique, whether to a related platform, to a modern scripting language, or even to a weird, minimalist language. Each involves different constraints, and once realized each offers different insights. (61)

Agreed. But I would also add that porting is really hard, especially in an era when code was measured in kilobytes and ROMs were something you burnt rather than download.

So what is essential in a port of the 10 PRINT program? I pared it to the following two points:

• The NES port should approximate the look, including color and character shapes.
• The NES port should emulate the random number generator used to generate the maze.

After two days of work, I ended up with the following:

So how did I get there? And why did it take two days to port a single line of code?

First, there is no one-line code that can generate visual output on the NES. Minus spacing and comments, my source is about 130 lines, give or take. A better coder could likely compress this to a smaller percentage of the original, but a single line is impossible. In part, this is because the NES does not natively run a higher-level language like BASIC (though it can do so on a cartridge). One must code the console in its particular dialect of assembly, catered to the 6502 microprocessor.

The other problem is that the NES must be initialized before it can do any graphical work. When the console boots, much of its internal contents are unknown. Circuitry has a fascinating tendency to exhibit organic behavior—remnants of data from prior programs can stick around in data buses even when a cartridge is absent, for instance. The NES’s PPU (Picture Processing Unit) in particular must be allowed to settle for a few milliseconds before it’s ready to send graphics to the screen. As such, several dozen lines of code are expended simply waiting around for the NES to settle down and signal, ‘OK, I’m ready to work.’ Of course, to human eyes, this wait is instantaneous.

Once the NES is ready, there is still much prep work to be done. For the same reasons described above, the contents of RAM must be manually reset, typically to all 0’s. Once done, the NES is a clean slate.

10 PRINT on the C64 also has the advantage of a built-in character set. For a PC, this makes a lot of sense. Most users will want to type letters, numbers, and symbols onscreen, whether to input code, write a letter, or work on a spreadsheet. The NES can make no such assumption. Any graphics seen onscreen must be drawn and stored in a portion of cartridge memory called CHR-ROM (sometimes RAM), short for character read-only memory. When you open an NES cart, you will see at least two large ICs: one holds the program code and the other holds the tiles used for background and sprite graphics. The latter is CHR-ROM.

When you insert a cartridge, the PPU can then fetch the tiles in CHR-ROM to draw game graphics. There are 256 background and sprite tiles apiece, stored in two memory locations known as pattern tables. Sprites are typically used for elements that move around the screen independently, e.g. Mario, Mega Man, Samus Aran, etc. The drawback is that there can only be eight of these on a single scanline; exceeding that amount requires flickering the excess sprites in and out of existence—an NES trademark. Background tiles are more restricted in movement, but face no per-scanline restrictions. They live on a pixel grid that can only be moved by scrolling. The PPU grabs background tiles and stores them in a name table, the 960-tile mosaic that makes up the entirety of the play screen (and a few sections you can’t see, depending on the television).

To draw the full screen of maze slashes, background tiles make sense, but we have to create them by hand. To do so, I looked up a pixel-by-pixel reproduction of PETSCII characters 205/206 (back and forward slashes) and reproduced them as background tiles with the YY-CHR graphics utility:

As you can see above, the characters are colored with YY-CHR’s default palette. Oddly enough, the tiles stored in CHR-ROM do not carry their own inherent palette data. Instead, the programmer assigns palette data in code and stores it in a designated PPU register. In other words, NES tiles are naturally ‘colorless.’ The pattern tables simply describe rainbow-agnostic bitplanes of data that are later assigned their color information. This grants the programmer a certain measure of flexibility within a game. When Mario grabs a star power-up, for instance, his invincibility animation is simply a looping cycle between the four available sprite palettes.

Also note that my pattern table also includes a set of alphanumeric tiles and four solid blocks. These are remnants of the Super Mario Bros. CHR-ROM dump that I used as my base file. I erased all but those tiles in order to accomodate my custom characters. Though I ultimately only need two tiles to generate the entire maze, I left the others to help test my random number routine (since repeating letters and numbers were easier to read than two slashes).

Loading the tiles in CHR-ROM is not enough; they have to be assigned the appropriate palette and placed onscreen. Since I was mimicking the two-tone look of the C64 program, the former was straightforward—but non-trivial. Matching palettes is a tricky task on early processors, since your range of available colors are constrained. PCs today can choose from millions of colors. The NES had sixty-four, though that is both an exaggeration and an underestimation. First, a few of those colors are duplicates, notably in the black range. And second, despite the range of available colors, the NES only had eight usable palettes, with four colors each, half assigned to sprites and the other half to background tiles. Based on that restriction, we’ve now cut our colors in half. The other catch is that one entry in each palette was mirrored—i.e., shared—in memory. The upside is that the shared color serves as transparency, allowing tiles to sit atop one another without noticeable borders. The downside is that we lose another seven colors, dropping our available pool to twenty-five.

However, the NES also had several color emphasis bits that could manipulate the palette in interesting ways. You might recall that many games used subtle color fades to transition between screens, make bosses dissolve or disappear, and so on. Programmers typically manipulated color emphasis to do so. Factoring in color emphasis expands the NES’s available colors significantly.

But there is one final factor: the display. The NES PPU does not generate objective colors per se, but combinations of luminance and chroma expressed as fluctuating voltages that televisions interpret as color. Add to that the various color tolerances of myriad television models and manufacturers and you end up with a game of approximations. The red of a Trinitron CRT does not equal the red of a Samsung LCS does not equal the red of a modern NES emulator.

Fortunately, I only had to choose two colors. And I did so unscientifically, simply eyeballing my best guess at the C64’s dark and light blue. I picked NES palette entries $12 and $22, which looked blue in emulation, but purple on my television. Such is life.

To get the characters onscreen, I simply had to feed the appropriate sequence of tiles to name table memory and enable the PPU. But what sequence would I use? To adhere to the base program, I needed a random sequence.

Again, unlike the C64 BASIC routine, the NES has no pre-built randomizing function. I had to insert my own. This poses a problem for the 6502, since the random number generator (RNG) must be sufficiently ‘random’ without being too computationally expensive. In other words, I don’t have time for a complex calculation. I need the graphics onscreen with little delay. This is less of a problem when I’m displaying a single static screen, but for gaming, a few frames of delay could ruin an engine’s performance. Likewise, the 6502 is limited to binary mathematics—essentially adding, subtracting, and bit-shifting operations. Multiplication is for wimps.

I eventually stumbled upon a ‘fast, 8-bit pseudo-random number generator (PRNG) in 6502 assembly’ available at CODEBASE64. As the site explains, the PRNG is a linear feedback shift register—basically a means to shift and scramble bits within a byte—that works on an initial seed value. Once you feed the function a seed, it can spit out a random series of 256 values (between $00 and $FF in hex notation). The problem is that it takes 960 tiles to fill the NES’s name table, so I needed a means to re-seed the function after each 256-digit iteration. When I tested my first draft of the program, there was a clear repetition evident in the resulting maze. It was subtle, but it was there:

Resetting the seed value each iteration turned out to be less reliable than I initially thought. Loading the function with a new seed only starts the random series at a different point along an identical byte chain. In short, you get the same pattern, slightly shifted. The proper solution is outlined on the CODEBASE64 site: ‘To get a different chain (essentially a different PRNG altogether), the value of the EOR would have to be changed.’ And based on the site’s tests, there are only 16 possible values that generate different chains.

To fill my 960 name table tiles, I loaded a new EOR value based on a small lookup table that was used each time the PRNG function ran. It’s not the most elegant solution, but it worked.

The end result is a decent approximation of a single line of BASIC, but it could use a lot of improvements. My results are pseudo-random, but they are static. Each time you load the ROM, you get the same results. The reason is that my seed is hardcoded (as $01). A better technique would be to seed the program with a predictably dynamic variable, something that changes each time the console resets. One example is to load a title screen and have the user press a button to generate the maze. A simple counter could increment each frame until controller input occurred. The authors of 10 PRINT (presumably Montfort and/or Bogost) describe a similar strategy in their Atari VCS port:

The Atari’s random number generator has to be seeded somehow. It could be given a fixed seed, but in order to ensure that different seeds are chosen (resulting in different mazes), the program starts with a blank screen and increments a counter each frame. The user starts the program by depressing the console’s RESET switch, at which time the frame counter is put to use as a random number seed. Every subsequent flick of the Reset switch will reset the seed and the diagonal graphics pointer data, resulting in a different maze. (206)

Porting on constrained platforms is more about strategy than mimicry. As in language, there is no one-to-one correspondence, no automatic translation. It’s creative approximation. And it’s hard work. Remember that the next time you play the ‘same’ version of Call of Duty on your Xbox 360, PC, or PS3. Someone had to do the translation work.

If you’d like more info about NES programming, check out the excellent Nerdy Nights tutorials at Nintendo Age (I used one of the tutorial templates to get started on this project). My thanks to the NesDev community for helping me with my PRNG woes. They are some serious code wizards.