Level compression
Level compression refers to techniques that allow fitting more level data into a smaller space. Levels may easily reach several kilobytes of space uncompressed, and with the cartridge size constraints of an NES game, this is most likely unacceptable. These are some general techniques for NES-friendly level compression, and it is often possible to use multiple ones in the same game.
Object based
Object compression represents levels as a series of commands that represent individual elements of the level. Each "Object" generally consists of an object type, an X and Y position within the level, and a width and a height, where some of these may be implied by the type of object.
Mario series games tend to use this technique. There are many ways to go about storing the information for objects. Super Mario Bros 1 in particular (and the homebrew game Double Action Blaster Guys) store a "Length" within the object type, where a given range of values refer to the same object at different sizes. This tends to lead to a format like the following:
nttttttt xxxxyyyy |||||||| ||||++++- Y position within a screen |||||||| ++++----- X position within a screen |+++++++---------- Object type +----------------- Next screen flag, moves to encoding the next screen if 1
In this scheme, an object's width or height may be the bottom 3 or 4 bits of the Object Type, and some objects that do not need a size (doors, question mark blocks containing powerups) do not need a length. For games with one-screen levels, the "next screen" bit may be replaced with another object type bit.
For later games, widths and heights are usually given their own dedicated bits. A typical Super Mario World object looks like the following:
nBByyyyy bbbbxxxx hhhhwwww |||||||| |||||||| ||||++++- Width |||||||| |||||||| ++++----- Height |||||||| ||||++++---------- X position within a screen |++|||||-++++-------------- Object type | +++++------------------- Y position within a screen +-------------------------- Next screen flag, moves to encoding the next screen if 1
Super Mario World dedicates another bit to the level's Y position, as non-vertical levels are two screens tall.
Meta commands
With the level effectively made up of a series of commands, it is easy to include signals in the level format that do things other than encode level tiles alongside the actual level objects. For example, Super Mario Bros 1 has a set of commands (encoded as objects with high Y positions) that set pointers for pipe destinations and enable various backgrounds.
Reducing the grid size
One technique for reducing the amount of space the level takes up is to reduce the width and/or height of the level grid that needs to be stored. This is accomplished by making the chunks that the level is composed of larger, so that one byte encodes more space.
Vertical columns
In this scheme, the game stores a list of predefined columns of blocks. Through this method, the level is reduced down to a one dimensional array.
The Legend of Zelda is one game that stores its map data as a series of vertical columns. Super Mario Bros 1 has a library of vertical column "templates" that it can then place other blocks on top of.
Metametatiles
Vertical columns may not provide the flexibility needed for games, so another option is to make the level out of chunks that have a width as well as a height. If the level is composed of 32x32 tiles rather than 16x16 ones, the game only needs to store 25% as much information, plus the dictionary to turn larger metatiles into smaller ones.
Mega Man games and the Game Boy Pokémon games are examples of games that split their maps into 32x32 metametatiles (megatiles?), composed of four 16x16 metatiles. Blaster Master goes even further, using 64x64 chunks that are then composed of 32x32 metametatiles, that are then in turn composed of 16x16 metatiles. Sonic the Hedgehog 2 uses 128x128 metatiles composed of 16x16 metatiles. Another benefit of 32x32 metametatiles in games that don't scroll vertically is that this is the same size that an attribute table byte covers, so you can store premade color information that is ready to be copied directly into the attribute table.
Compressed tilemaps
Another option for level compression is to just start with the final, complete map of the level and use compression algorithms such as run-length encoding, or more advanced options like the LZ77 family.
Kirby's Adventure's levels are stored this way. This method allows complete flexibility with placing metatiles completely freely, but might not compress as well as other methods.
Other techniques
Repeating backgrounds
Super Mario Bros has a set of backgrounds that get placed onto each screen before tiles get placed on top of it. With the repeating backgrounds, the game can have a background without needing to specify where each cloud or other element goes.
Post-processing
Nova the Squirrel runs a filter over the level after it has been decompressed, adding edges and corners to ground tiles and performing other changes, such as adding the bottom parts of doors and other objects, or extending things to the ground.
Haunted: Halloween '85 and its sequel The Curse of Possum Hollow use vertical RLE modified with a Markov chain algorithm, which interprets a "run" as a mapping from each tile to the most common tile below it.
