Background Compression

BACKGROUND

First off let me say that I am a noob programmer and I don’t know what I’m doing.
However, this tutorial should give you a good start towards simple background compression.
Also, there is a minor bug in the final program. I’m tired of messing with it, but if someone
finds it, I’d love to fix it. This tutorial also assumes a working knowledge of NES programming.

The purpose of background compression is just that: to make your program smaller. It works
best with a large number of rooms, but can be beneficial to most anything. For example,
in my personal program, I did not design it to support this routine, and as a result, the
compression took up a shit ton more space than it would have knowing what I know now, but
it still shrank the stuff down to 25% of its original size. In this example, we will make
4 rooms. Uncompressed, this would run you 960 bytes per room (or 3840 bytes total). Compressed,
the 4 rooms take up about 663 bytes, or 17.3% of their original size. The point is obvious.

Compressing stuff is not very complicated, there are just a bunch of little steps. In this
example, we are going to steal and build on BunnyBoy’s “background” program and “mario” CHR
file.

Assuming that you are making your own game, you would want to make all of your tiles and put
them into a CHR file like the mario one that we are using. You want to be able to view them
in a PPU viewer for use in construction of meta tiles that will come later.

We see that most of the 8*8 tiles in this tile set are used to construct 16*16 blocks. We
just take this natural tendency and use it to make stuff smaller. Once you have your nice tile
set, we need to make what are called “Meta Tiles”.

Note that you can have up to 128 meta tiles in each meta tile “bank”. But what if you needed
more than 128, like 1000??? You will need multiple meta tile banks, this will come later.
I just split them up this way to demonstrate the multiple bank function.
I’m not sure how to explain this better than the picture. You can see how neatly the
tiles fit into meta tiles and Walla! Now you only have to specify one byte for
every 4 bytes written to the PPU! Savvy?

After you have all of your meta tiles defined, start building rooms. You can build as many
rooms as you have the patience to build. We will look at this example:

You can see that you have this giant ass room made up of 8 meta tiles. Easy, no?

META TILE BANK SWITCHING

First, let me explain the meta tile bank switching flag. For this, we will use
binary (only to set it apart and make it easy to see what we are doing). For each
meta tile bank, we need to assign a number. We are going to call the top one, creatively
enough, “MetaTileSeta” and the second “MetaTileSetb”. This will come later, but we need to
use the following for these meta tiles sets:

MetaTileSeta = %11000000
MetaTileSetb = %11000001

The first two bytes specify stuff that will come later and the bottom ones specify the meta
tile bank number, see that a is bank 0 and b is bank 1.

REPEATING META TILES

Okay, next we need to specify repeats of meta tiles. If you look at the picture, there
are a bunch of places where meta tiles are repeated. So, for the top row, wouldn’t it
be easier to have only a repeat number and the tile number rather than having to repeat the
tile number 16 times?? The thing to note is that the way I have my program set up, you need
to specify the number of repeats – 1. (i.e. if you want to repeat it 16 times, you have to use
15, 3 times, use 2, etc.) Here we are going to use “binary” as well, but with this one, we
only need to have bit 7 = 1, bit 6 = 0, and the other 6 can be used to specify the repeat numbers.
So, this makes it easier to use $8(repeat number). Or:

Repeat 6 times, $85
Repeat 16 times, $8F

When specifying meta tiles, you will only go up to $7F in any given bank, so the 8 stands out
just like the binary.

SPECIFYING META TILES

Okay, now we know how to specify repeats and tile set switching sets, what about meta tiles?
Well, this is the easy part. See the fancy picture? The numbers down the side are the first
digit in hex and the numbers across the top are the second. EX:

Tile in row 5 and column 9 would be $59
Tile in row 0 and column 0 would be $00 and so on.

COMPRESSING A ROOM

We’ll learn how to read this data later, but for now let’s make a room and we’ll hopefully understand
it a little better. Looking back at that picture, we see that there are rows of tiles. I have
found that it makes sense to me to leave the data string in these rows for later debugging and/or
copying parts of rooms into other rooms. So, first we need to specify the meta tile bank for the
program to pull meta tiles from. So, here we see that the first tile is $06 of the first bank and
it is repeated 16 times. So, the first row would be:

.db %11000000(bank 0),$8F(repeat 16 times),$06(the tile in row 0, column 6)

Pretty simple, right?

Second row:

.db $06,$03,$03,$82,$04,$83,$03,$82,$04,$03,$03,$06

See if you can decode what the data string is saying. If you can’t, the rest of this won’t make sense.
Please re-read up to this point until you get it, or ask me a question. Note that you only need to
specify meta tile bank switches when you switch banks, not every row.

So, the completed room data string would look like this:

.db %11000000,$8F,$06
.db $06,$03,$03,$82,$04,$83,$03,$82,$04,$03,$03,$06
.db $8F,$06
.db $06,$8D,$04,$06
.db $8F,$06
.db $06,$00,$06,$00,$06,$00,$06,$00,$06,$00,$06,$00,$06,$00,$06,$06
.db $06,$8D,$02,$06
.db $06,$03,$03,$82,$04,$83,$03,$82,$04,$03,$03,$06
.db $8F,$06
.db $06,$8D,$04,$06
.db $8F,$06
.db $8F,$06
.db $06,$05,$06,$05,$06,$06,$05,$06,$06,$05,$06,$06,$05,$06,$05,$06
.db %11000001,$8F,$00
.db $8F,$01,$FF

Again, if you can’t decode what this means, you should go back and study a little more, cause the rest
of this won’t make sense to you.

THE “$FF” FLAG

Also, we see the first appearance of $FF. This simply signifies the end of a data string and tells
the subroutine that it is done. Poweryay!!! Our first room!

CODING IN THE META TILES

Okay, now we have this happy little string, what do we do with it? Well, here we will learn how
to tell the processor to decompress the stream and write to the PPU.

First, we will cover basic decompression. If you didn’t use any bank switches, or repeats, your
program would look pretty simple.

Here, you need to code in your meta tiles. This is the part where having your plain tiles in the
PPU will be most helpful (especially if you have the afore mentioned 1000.) Pretty simple, you simply
take the top row then the bottom row in a series of bytes using the normal tile numbers from your
original tile set (i.e. what you see in the PPU viewer). For example, meta tile bank a:

MetaTileSeta00:
.db $44,$49,$5F,$7A

MetaTileSeta01
.db $AB,$AD,$AC,$AE

MetaTileSeta02
.db $53,$54,$55,$56

…and so on till you get all of them done.

I usually keep them at the top of my meta tiles in ROM space for easy access, but you can put the
following wherever. You can see that you will have to use some sort of look up table to find
the data for each meta tile, so we may as well do this now.

;————-

MetaTileSeta:
.word MetaTileSeta00,MetaTileSeta01,MetaTileSeta02,MetaTileSeta03,MetaTileSeta04,MetaTileSeta05,MetaTileSeta06

;————-

MetaTileSetb:
.word MetaTileSetb00,MetaTileSetb01,MetaTileSetb02,MetaTileSetb03,MetaTileSetb04,MetaTileSetb05,MetaTileSetb06

;————-

Note that this is a table of addresses! This is why you can only put 128 meta tiles in each bank (even if
we are using Deniz sized tile sets here, the full sets would be bigger….)

And eventually, you will need a look up table for the meta tile bank you want the program to read from, so we
may as well put that here as well:

;————-

meta_tile_sets:
.word MetaTileSeta,MetaTileSetb

;————-

Make sense so far? At this point, we have all the data we need to decode all the data streams. Now, onto
actual decoding.

SIMPLE DECOMPRESSION

For reasons of my sanity, I will skip the stuff that I think is pretty basic…like disabling NMI while
writing to the background, turning off the PPU, specifying which room to load, and how to set up the PPU
to receive a new room. This will focus on the important decompression stuff.

If we didn’t have any repeats, or bank switches, we would be able to hard code the pointers and that would
be that, let’s assume for a moment that is the case. When writing our meta tiles to the background, we
run into the problem of trying to write two rows at one time, when the PPU accepts data only one row at a
time…. What to do? Here we should buffer our writes. So, we need to reserve 32 variables in
zerospace, one for each tile what we are writing to the background.

background_row .rs $20 ;the second row that each meta tile contains

So, now we take our meta tile and write the first two entries to the PPU, then the second two entries
to our buffer. Now, to keep our positions in the meta tile and in the buffer straight, we need to use
the registers X and Y. We need to reserve Y for pointer use, so X will be used for the buffer. To keep
them straight, we will use simply:

data_y .rs 1 ;y counter
data_x .rs 1 ;x counter

So, after our buffer fills up, we need to write the second row to the PPU, then jump to the next row of meta tiles.
This is pretty easy, so I won’t go into it. (It should be noted here that the Y register is used for
multiple things. It uses the data_y for reading the room data stream, and here we see that it uses the register
y to decode the meta tiles.) Here is our code up to now:

;————-

decompress:
LDY #$00
LDX data_x
LDA [meta_tile_ptr],y ;write the first tile of the meta tile to 2007
STA $2007
INY
LDA [meta_tile_ptr],y ;write the second tile of the meta tile to 2007
STA $2007
INY
LDA [meta_tile_ptr],y ;write the third tile of the meta tile to memory for later use
STA background_row,x
INY
INX
LDA [meta_tile_ptr],y ;write the forth tile of the meta tile to memory for later use
STA background_row,x
INX
STX data_x
CPX #$20 ;see if we are at the end of a row. If so, we need to use the tiles stored in memory, if not, jump to the top.
BEQ .next
JMP background_start

.next
LDY #$00
row_start: ;write the tiles stored in memory to the background
LDA background_row,y
STA $2007
INY
CPY #$20
BNE row_start
LDX #$00
STX data_x

JMP background_start ;jump back to the start of the routine and continue on

;————-

Not all that difficult, got it? Okay, now onto bit testing. Back when we specified our repeats, end of data
string, and bank switches, we set up the data string to be bit tested. First, the end of the string. Simply
tell the routine that if it encounters:

%11111111

it is done and that it should “RTS”. Simple enough. Next, we tell the program that if it encounters:

%1xxxxxxx

it needs to do something special.

%10xxxxxx means that it needs to repeat the meta tile
%11xxxxxx means that it needs to switch meta tile banks

I guess rather than my beating it to death, it would be easier for you to spend a couple minutes with this
part of the program and either make a flow chart or just convince yourself that it is working. It should
be noted that there are 3 pointers at work here:

ptr1 .rs 2 ;pointer to the background information. This is loaded in the part we skipped
;about which room you want to load at a given time

meta_tile_sets_ptr .rs 2 ;pointer to which meta tile set you want to read from at any given time

meta_tile_ptr .rs 2 ;pointer to the meta tile/repeat number/bank number in the data stream

Take a look through this bit of code and see if you understand what it is doing. If not, please ask
questions. Here we need to define a variable for the number of meta tile repeats.

repeat_meta_tile .rs 1 ;times to repeat the current meta tile

All this section of code does is:

-test if you are in the middle of repeating meta tiles, if so repeat till it is done
-test if you are at the end of a data stream, if so, skip to the end
-test if it is a repeated meta tile or a bank switch
-test if it is a switch, if so switch meta tile banks and jump back to the start and load the next entry in the stream
-if it is not a switch, it is a repeat, load the number of repeats and load the next meta tile in the stream
-then decompress the data as shown above

;————-

background_start:

LDA repeat_meta_tile ;see if you are repeating a tile
BEQ .jump
DEC repeat_meta_tile ;decrement the repeated tile and jump back to the decompression routine
JMP decompress

.jump

LDY data_y
LDA [ptr1],y
CMP #$FF ;see if it is at the end of the data string
BNE .next
JMP background_complete
.next
LDA [ptr1],y
AND #%10000000 ;see if this is a repeated tile or a switch of meta tile banks
BNE .next1
JMP .loadtile

.next1
LDA [ptr1],y
AND #%01000000 ;see if this is a switch of the meta tile banks
BNE .next2
JMP .repeat

.next2
LDA [ptr1],y
AND #%00111111 ;switch meta tile banks
ASL A
TAX

LDA meta_tile_sets,x ;load the new meta tile bank
STA meta_tile_sets_ptr
LDA meta_tile_sets+1,x
STA meta_tile_sets_ptr+1
INY
STY data_y
JMP background_start ;jump to the next entry in the data table and return to the start of the routine

.repeat
LDA [ptr1],y
AND #%00111111 ;load number of repeats for this meta tile
STA repeat_meta_tile ;note that this is set up so that you need to have the number of repeats – 1
INY
STY data_y

.loadtile
LDA [ptr1],y ;load the meta tile number
INY
STY data_y
ASL A ;this is a table of addresses, so multiply by 2
TAY

LDA [meta_tile_sets_ptr],y ;load the address of the meta tile in question
STA meta_tile_ptr
INY
LDA [meta_tile_sets_ptr],y
STA meta_tile_ptr+1

decompress:

;————-

That’s it. There’s not much to it. For your convenience, you will find an attachment entitled “blankmetatiles”.
I made this when I was making my last backgrounds because I kept doing it over and over. If you label your meta
tiles as we did here, all you have to do is paste “MetaTileSetX” in front of all the freaking letters and you’re done.

For practice, the attached picture “Graphics” has the other three rooms that are compressed in the attached program.
I would suggest that you practice with these and then make your own. Using the D-PAD in the program will load
each of the Four Rooms. Like I said at the top, there is a weird bug, but I’m too lazy to look for it.

I guess that’s it. Post here or PM me if you have questions.

On a side note, I haven’t got into scrolling too much, but a working example of compression and scrolling can
be found:

http://nintendoage.com/forum/messageview.cfm?catid=22&threadid=31898

Thanks again! Until next time…8==D