Algorithm to populate background name table

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
DedGzus
Posts: 11
Joined: Sat Jan 07, 2023 10:11 am

Algorithm to populate background name table

Post by DedGzus »

So for my first attempt at an NES game I am making something where each level is only two screens wide so I don't have to mess with loading in new background while scrolling, etc. I've developed a formula for the way I want to store the binary data for each level as follows.

Each levels binary is formatted as follows:
$00-$3f => 64 bytes of meta-tile definitions formatted in 2 32 bytes rows. 16 total meta-tiles per level.
$40-$7f => 64 bytes defining screen A ($2000) attribute table
$80-$bf => 64 bytes defining screen B ($2400) attribute table
$c0-$cf => 16 bytes defining 4 background palettes for the level
$d0-$xx => Starting at this address the algorithm for the meta-tile layout begins. Each byte defines a meta-tile and how many times it is repeated. For example a byte of $48 would mean meta-tile number 4 repeated 8 times. $30 would mean meta-tile 3 repeated 16 times. A tile can never be repeated more than 16 times in a row because that is the width of a screen and there are only 16 meta-tiles to choose from per level. Screen A ($2000) is stored first and then Screen B is stored next.

The algorithm will, in my best guess, fill Screen A's name table first. When it reaches 960 bytes it will start filling Screen B until it also is full. Then it will write in the attribute tables for each screen. Finally it will set the background palettes for the level.

I guess my question is, is this a decent approach to this issue knowing that each level will only be the two screens wide? In my calculation for a simple level it take my storage size down from 2Kb for the level uncompressed down to roughly 300-400 bytes in this format. I haven't written the algorithm in 6502 asm yet but I will. Not looking for someone to do the code for me just asking if this is worth doing I guess. Thank you.
User avatar
Dwedit
Posts: 4924
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Algorithm to populate background name table

Post by Dwedit »

Usually the attributes are part of the metatile, not really separated.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Re: Algorithm to populate background name table

Post by Drag »

The algorithm you're describing is called Run-Length Encoding (or RLE), and yes, it's a good algorithm for what you're doing.

If you're curious about what else is available, LZ77 is another common encoding scheme where you have two commands: (1) output X amount of raw bytes, (2) copy X amount of bytes from earlier in the output stream (which can also turn into RLE if your copy source is output-1).

RLE is great if you want something simple that you can encode by hand, where LZ77 might compress better in certain circumstances, but you'd really want to write a tool to encode your data for you.
Post Reply