Zanac Map Graphics Guide

ZANAC (NES) MAP GRAPHICS GUIDE
			      by ManxomeBromide
			      v1.0, 23 May 2020


This document explains the data formats used by the NES game Zanac (Compile,
1986) to generate its level maps. It provides enough information to extract
the graphics from the game ROM and effect cosmetic changes in the levels. It
is not, as of v1.0, sufficient to inform a complete level editor. See chapter
9, "Open Questions", for the remaining work to be done to enable this.

In keeping with my understanding of ROMHacking.net's house style, addresses
will generally be presented in terms of ROM offsets. Zanac's graphics format
involves an alarming amount of pointer-chasing, however, so we will
occasionally need to convert these values to and from actual pointers to the
(bankswitched) runtime CPU address space.

Throughout this document hexadecimal numbers will be marked by prefixing them
with a dollar sign ($). $10 = 16, $200 = 512.

All multibyte values are little-endian, so the value $BEEF will appear in the
ROM dump as the byte $EF first, then $BE.

			===== TABLE OF CONTENTS =====

   1. Overview
   2. Pattern Data
     2.1. RLE Format
   3. Metatiles
   4. Render Tables
   5. Map Scripts
   6. Base Layer Blocks
   7. Greebles
   8. Map Generation, Step by Step
   9. Open Questions
  10. Revision History

			   ===== 1. OVERVIEW =====

The NES has two major chunks of memory: CPU and PPU. The first is code and
data intended for the main processor, while the latter is mostly reserved for
the graphics chip (or, as the NES architecture calls it, the "picture
processing unit"). Each has some RAM on the console for working space, to hold
the data the games needs as it runs. Usually, the program itself and its basic
graphics are stored in ROM, with a dedicated area of ROM for both the CPU and
the PPU.

All of Zanac's ROM chips, however, are hooked to the CPU's address space. The
PPU is instead equipped with RAM, allowing the pixel-level data for the game
to be edited on the fly by the game itself. These graphics---the "pattern
tables" in NES parlance---are stored in a compressed form in the CPU program
ROM and are decompressed into the PPU RAM as needed by the game. This mostly
only happens when moving to or from the title screen, and at the start of each
stage.

The fundamental unit of pattern data is a 8x8 block of pixels with a
four-color palette. At any given time, the NES has four palettes available for
a tile in the background to choose from. They share a background color with
the screen as a whole, but then each sets the other three independently from
the NES's overall palette of 56 colors. However, the PPU groups the background
tiles into blocks of four, requiring each 16x16-pixel area to use the same
palette to interpret its pixel data.

Zanac's map engine relies on this behavior, and uses 16x16 metatiles as its
fundamental unit of background graphics. These tiles are generated a row at a
time, as needed, as the player flies over the level.

Unlike many other games, though, the map data is not compressed in any usual
sense. The Zanac maps are so huge---the largest is over 70,000 pixels
tall---that just compressing the tile data won't really work. Instead, it
stores the map information as a script that is interpreted as the level
unfolds.

Each stage is generated out of an opaque base layer and then eight stacked
layers of partially transparent decorations over that. The map script
configures and reconfigures each layer at various points on the map, while
also independently configuring things like scrolling speed and palette
information.

			 ===== 2. PATTERN DATA =====

The pattern data is the raw material of all of the graphics in the game. It is
stored in a run-length-encoded format and decompressed into the PPU pattern
memory at $0000-$1FFF as needed by the game.

Bank 4 (ROM offsets $10010-$1400F) holds most of the pattern data for the
entire game. A table of two-byte pointers at $10040-$004D points to seven
blocks of pattern data:

 0: All sprite data except for 8 spots. This is always loaded into the
    region $0000-$0F7F.
 1: Alternate graphics for the player's ship, accessible via an Easter Egg
    code (hold A and B while pressing START to begin the game). This is
    loaded into $0140-$01FF, replacing the normal ship graphics in block 0.
 2: Title screen tiles, including two fonts and the title logo. Loaded into
    $1200-$1A0F.
 3: Ground features and enemy bases common to all levels. Loaded into
    $17F0-$17FF during gameplay, but into $19F0-$1FFF (with overspill
    truncated by the nametable data) on the title screen.
 4: Ground features and enemy bases for areas 1-4. Loaded into $1000-$153F.
 5: Ground features and enemy bases for areas 5-8. Loaded into $1000-$17AF.
 6: Ground features and enemy bases for areas 9-12. Loaded into $1000-$17CF.

Sprite patterns 248-255 are special. These 128 bytes of pattern data are
unique in that they are rewritten while levels run; sprites that use these
patterns are used to display temporary UI elements as the game runs. The
master table for these is in bank 6, at ROM offsets $189C1-$189DC, and it too
has 7 entries:

 0: Illegal entry, never used
 1: AREA
 2: TIME
 3: GAME OVER
 4: BONUS
 5: Pony Canyon logo on the title screen
 6: Empty data

The routine that does the decompression here has a special check to treat any
value over 6 as being the same as 6, but this sanity check does not extend to
0 despite that also being an illegal value.

RLE Format
----------

The run-length encoding scheme Zanac uses is mostly straightforward. At any
given time the decompressor is in either uncompressed mode or run mode. It
starts in uncompressed mode, which simply copies bytes from the source into
the target one at a time. In compressed mode, bytes are read in pairs, and the
first byte is copied into memory a number of times specified by the second
byte. The decompressor switches between compressed and uncompressed mode
whenever it encounters a special sentinel byte. Every byte is checked for
being the sentinel in uncompressed mode, while only every other byte is
checked in compressed mode.

This does mean that the sentinel value cannot appear anywhere in the actual
data. That's annoying, and it's a problem that wouldn't exist if they reversed
the byte order in compressed mode. Oh well.

Each block begins with the sentinel value to use for this block, and then a
secondary sentinel value that also must not appear in the graphical data but
which controls decompression features that are not used by Zanac. Each block
ends with two copies of the primary sentinel value.

			   ===== 3. METATILES =====

One level up from the 8x8 tiles of the pattern tables are the 16x16 metatiles
that are the real building blocks of Zanac's levels. Much like the pattern
data, there are three sets of metatiles, one for areas 1-4, one for areas 5-8,
and one for areas 9-12. The pointers to the metatile tables for these are at
ROM offsets $14060, $14062, and $14064 respectively. This is a pointer to an
array of five-byte structures.

The first four bytes are the indices of the 8x8 pattern tiles to use for, in
order, the top-left, top-right, bottom-left, and bottom-right. Background
tiles are always taken from the $1000-$1FFF pattern table.

The fifth byte holds a value from 0-7, indicating which palette to use. This
is not actually a directly index into the palettes---after all, there are only
four palettes available to background tiles---but instead an index into
another table of palette entries that say which palette (0-3) to actually use.
This extra layer of indirection allows the map to palette-swap a metatile by
altering the table without palette-swapping ALL metatiles that use those
colors.

WARNING: I've sort of blithely referred to the metatiles as being "an array of
five-byte values", but that's only true in a vague sense. These "arrays"
aren't complete or even continuous, and they also are entirely permitted to
overlap some. When a metatile index is processed, the base address is loaded
from the base pointer for area as described above, and then that base address
has the metatile index, multiplied by 5, added to it. That address, wherever
it is, is then used as the metatile data. However, even with all that chaos at
the ROM level, Zanac's map engine code is treating it basically the way C
manages accessing an array of structures. Oddities of data format will only
show up if you carefully trace each memory access and notice that they aren't
as separated as you'd expect, or that some values very pointedly never appear
at all.

			 ===== 4. RENDER TABLES =====

Zanac keeps CPU-side copies of most of the PPU data, refreshing it only when
needed. (Communicating with the PPU is kind of expensive and you can generally
only do it between frames, so this lets it build up a set of work to do as the
frame proceeds and then blitz through it all at once at frame end.)

A copy of the map palette is kept in RAM at memory locations $0145-$015D.
These thirteen bytes correspond to the sixteen bytes at PPU memory locations
$3F00-$3F1F; the value at $0145 is repeatedly copied into the "background
color" location of each of the four subpalettes and is not repeated.

The attribute table that metatiles use to look up which subpalette to use is
stored in $0163-$0175. Each of these eight bytes holds the subpalette to use
for that metatile color index, multiplied by $55. Using $00, $55, $AA, and $FF
instead of 0, 1, 2, and 3 makes some of the math easier when wrangling the
actual color specifications in the PPU. This attribute table's initial values
are [0, 1, 2, 3, 2, 3, 2, 3] and are specified by a table in the ROM starting
at offset $1D75B.

The map engine generates one row of metatiles at a time, which the graphics
code then interprets as actual name and attribute table entries to the PPU,
thus specifying the actual background graphics. That row of metatiles is
stored as 16 bytes from $0189-$0198. Each is a simple one-byte index into the
level's metatile array.

			  ===== 5. MAP SCRIPTS =====

Each of the game's 12 areas has its own map script. The master map script
table is at the top of bank 5, starting at ROM offset $14040. This is a
1-indexed, array, not a 0-indexed one, so area 1's map script pointer is at
$14042-$14043. (These pointers are little-endian, as the 6502 family's always
are, and also refer to locations in the banked ROM. To convert the pointers to
ROM offsets in bank 5, add $C010 to them. For example, $14042 is $11 and
$14043 is $A4, so the Area 1 map script is at ROM offset $A411+$C010=$16421.)

The map script is a series of map commands, of varying length. There isn't
really an easy way to get to, say, the 12th map command; you'd have to start
at the beginning and interpret your way past the first 11 commands to reach
it. (Zanac itself caches a pointer to where it is in the current level's map
script, and advances it as it reads its way through. Since it's consuming it
as a stream it never finds it necessary to backtrack or index.)

The first two bytes of every map command are a 16-bit little-endian integer
specifying where in the map this command is to be executed. 0 is the first row
of metatiles in the map (so, the very bottom of the very first screen), 1 is
the row above that, and so on and so forth. These map rows must be strictly
nondecreasing---you can have as many map commands on one row as you want, but
you can never try to edit the map "in the past".

The 16-bit data size puts a theoretical cap on level size of
65535*16=1,048,560 pixels. Zanac's real cap is more like 72,000 though.

The third byte is the command code, a number from 0 through 8. These indicate
what kind of map command this is, and thus how many more bytes are in the
command and what they mean.

 0: Throttle command. The rest of the command is a 16-bit integer, specifying
    the target scroll speed in units of subpixels per frame. Zanac subpixels
    are 1/256th of a pixel, so this can also be read as two 8-bit integers,
    the first specifying subpixel target speed and the second specifying whole
    pixels. The number of subpixels per frame in the target speed must be even.

    Changing scroll speed is not instantaneous. If the target and actual
    speeds differ, the ship will accelerate or decelerate as needed at a speed
    of 2 subpixels per frame per frame.

  1: Set base layer. This specifies the map pattern that underlies everything
     else. The argument is a single byte, which is a base layer block
     identifier. See Chapter 6 for details of how the graphics themselves are
     defined.

  2. Unknown purpose. Four bytes of arguments, probably two sixteen-bit
     values. Even more probably addresses. Sets control bytes $AF-$B1 and
     $6C-$6E, with $AF and $6E forcibly zeroed.

  3. Unknown purpose. None of Zanac's map scripts use this command, but it's
     capable of parsing it. The argument is two bytes long. It seems to be
     some kind of map reset command to splice multiple map scripts together.

  4. Palette assignment. This command rewrites the colors used by Zanac. The
     arguments are three bytes long; a two byte address declaring where the
     color data is, and then a third byte indicating which palette to update.
     If the map colors are being set, the third byte is 1. If the sprite
     colors are being set, the sprite colors are being set. At the address
     specified in this command, all four subpalettes are described with a
     13-byte sequence as described in Chapter 4: Render Tables.

  5. Stop Code. No map script commands will be interpreted past this row. All
     other map commands ON this row, including ones after the stop code, will
     still be executed. This command takes no arguments.

  6. Greeble Configuration. "Greebles" were the name used by Industrial Light
     and Magic to describe the detailing they put on the starship models in
     the original Star Wars, and the name has stuck for repeated detailing.

     The first argument byte is the number of greebles to configure in this
     command. It is followed by that many greeble specifications. We'll get to
     those next.

  7. Boss Greeble Configuration. If the first argument byte is zero, that's
     all there is to this command. Otherwise there are four additional control
     bytes and then a greeble configuration identical to map command 6.
     Processing this command rewrites the 9 control bytes in $C0-$C8.

  8. Attribute table configuration. Variable number of (index, value) pairs,
     where index is a value from 0 to 7 and value is one of $00, $55, $AA, or
     $FF as described in Chapter 4: Render Tables. The list is terminated by a
     single $08 byte, with no corresponding value attached.

Map Commands 6 and 7 include "greeble specifications." These are between four
and ten bytes long:

  <Ctl> [InitialDelay [CopySpacing]] [HStep] [Copies] <Column> <Addr> [H, W]

Arguments in <angle brackets> are always present. Arguments in [square
brackets] are only present depending on what bits are set in the <Ctl> byte.
If square brackets are nested, the inner arguments will only appear if the
outer arguments do.

The argument meanings are as follows:

 Ctl: The control byte. The low 3 bits specify which layer this greeble is
      rendered on, and may be any value from 0 (lowest priority) to 7
      (highest priority). The $10 bit is unused, and bits $20 through $80
      indicate which optional arguments are present.

 InitialDelay: Number of rows to wait before drawing the greeble. Present only
               when control bit $80 is not set; otherwise this is 0.

 CopySpacing: Number of rows between copies of this greeble. Present only when
              control bits $80 AND $20 are not set; otherwise this is 32.

 HStep: This is a SIGNED byte that indicates how many tiles to the right to
        move successive copies of this greeble. Present only when control bit
        $40 is not set; otherwise this is 0.

 Copies: Number of copies of this greeble to place. If this is 0, the greeble
         will repeat forever. Present only when control bit $20 is not set;
         otherwise this is 1.

 Column: SIGNED byte representing the X position on the map to draw the
         greeble. If this value is $80, the greebler is disabled immediately,
         interrupting any greeble being drawn on that layer. In this case all
         other arguments are ignored.

 Addr: If control bit $10 is set, this is the address of the actual greeble
       graphics. If control bit $10 is not set, the actual graphics are
       stored at <Addr+2>, with the first bytes replacing H and W below.

 H: Number of rows in one copy of the greeble. Present only when control bit
    $10 is set; otherwise it is the byte pointed to by <Addr>.

 W: Width of the greeble (more or less: see chapter 7). Present only when
    control bit $10 is set; otherwise it is the byte pointed to by <Addr+1>

		       ===== 6. BASE LAYER BLOCKS =====

Base blocks, like metatiles, are stored in a table that's shared between
groups of four levels, and also like metatiles, the base address of these
tables is stored at the top of bank 5. The address of the table used by areas
1-4 is at ROM offset $1405A, the one used by 5-8 is at $1405C, and the one
used by areas 9-12 is at $1405E.

The tables themselves are arrays of three-byte structures: the first two bytes
are the address of the metatile data, and the third byte is the number of
rows in the base block. The metatile data itself is uncompressed, so the
number of bytes at that location that are relevant can be computed simply by
multiplying the number of rows by 16.

Like metatiles, there is again no real guarantee that tables are disjoint or
contiguous; the argument to a map script's Map Command 1 is simply multiplied
by three, added to the base pointer, and then interpreted.

			   ===== 7. GREEBLES =====

Most of the details about any given greeble are given in its spec in Map
Commands 6 and 7. The only exception is greebles where the $10 bit in its
control byte was set; in those cases the greeble data begins with the width
and height before proceeding to the graphics data.

Greebles can be partially transparent, allowing lower-priority greebles or the
base map block to show through. This means that "width" is kind of a misnomer;
the "width" is really the maximum number of tiles that any row in the greeble
can have.

Tiles can be "skipped" in two ways. If tile 0 is specified in the graphics,
instead of rendering a tile, that 0 is skipped and the next byte specifies how
many tiles to skip ahead. These skipped tiles do not count against the tile
width. If tile 1 is specified, the line ends immediately.

So, for example, if a greeble was listed as width 4, and its graphics data
were $02 $00 $04 $03 $01 $02 $03 $04 $05, that would produce a pattern like
this:

    2....3
    2345..

Note how the actual graphics here end up being 6 tiles wide despite a stated
"width" of 4 tiles.

		 ===== 8. MAP GENERATION, STEP BY STEP =====

There are a lot of moving parts in the map generator, so here's all of it in
one place.

AT LEVEL START:
  - Decompress pattern data into $1000-$1FFF of PPU RAM based on area.
  - Initialize map script pointer, base tile array, and metatile array based
    on area number.
  - Reset attribute table to [0, 1, 2, 3, 2, 3, 2, 3].
  - Reset current map line to 0.
  - Reset all greeblers to "disabled" (column $80).

EVERY MAP LINE:
  - Execute map commands off the map script pointer until it's not pointing at
    a map command for the current line.
  - Copy the current line from the current base tile (set by command 1) into
    the current line.
  - Advance the current line for the tile, resetting to 0 if it's past the end
    of the tile.
  - For each greebler from 0 to 7, in that order:
    - If the greebler column is $80, skip to next greebler.
    - If the delay on the greeble is not 0, decrement the delay and skip to
      the next iteration.
    - Process the current greeble row, advancing the greeble pointer.
    - Decrement the greeble rows remaining. If it's not 0, advance to next
      iteration.
    - If the "number of copies" field is larger than 0, decrement it. If this
      *makes* it 0, disable this greebler by setting the column to $80 and
      proceed to next iteration.
    - Otherwise reset the greeble pointer, rows remaining, and greeble delay
      from the greeble spec.
    - If the horizontal step isn't 0, add that to the starting column. If this
      moves the starting column below -15 or above 15, disable this greebler
      by setting the column to $80.
  - Look up each tile in the row in the metatile array. Copy the four tiles
    into the PPU's name table. Look up the attribute for the metatile in the
    attribute table and copy that value into the PPU's attribute table.

			===== 9. OPEN QUESTIONS =====

In tracing through the map and pattern code, I encountered a number of
constructs whose purpose was not clear. I leave them here as jumping-off
points for further experimentation.

HIGH PRIORITY
-------------
High priority open questions involve code that obviously runs and is part of
the level logic but whose purpose has not yet been analyzed and understood.

 - What does Map Command 2 do? More generally, what do the four control bytes
   it overwrites actually control?
 - Similarly, what is the significance of the four extra control bytes Map
   Command 7 adds to Map Command 6?
 - Special processing triggered when placing metatiles of code $1B or less.
   What is this doing and where is it pulling data from?
 - Color 3 in background palette 1 sometimes goes through a color-cycling
   animation to make glowy bits glow. What controls this?

LOW PRIORITY
------------
Low priority open questions involve dead code within the Zanac ROM. The
organization of a lot of the logic surrounding these questions suggests that
large parts of Zanac were built by reusing code from some other, more general
engine. The implementation of those unused features are still present, though,
and modders might be able to take advantage of them.

 - The pattern-index tables at $189C1-$189DC are four bytes long instead of
   two. What are the other two bytes for?
 - What implemented-but-unused features does the secondary sentinel value
   control in the pattern data?
 - What does the implemented-but-unused Map Command 3 do?
 - The map script for Area 12 does not include a stop code. How does it know
   when to end?

BIG PICTURE
-----------
Big picture open questions are more at the level of how to put together the
things we know about the ROM to make it do different things.

 - To what degree are waves of enemies scripted? What controls enemies,
   generally?
 - How does map code know which map elements are interactible, or shoot at the
   player, or other behaviors?
 - One step beyond that: how does map code know which powerup is hiding within
   a destroyable treasure box, or where a warp hole goes?
 - How are boss fights specified? Their physical appearance is just another
   greeble, but there's clearly some extra logic. To what degree is this
   configurable?


		       ===== 9. REVISION HISTORY =====

v1.0: 23/05/2020. Initial publication. Enough data to reconstruct the
                  pattern and name tables for each level.