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&th...

Thanks again!  Until next time...

if u dont know what u are doing then DONT USE THE NERDY NIGHTS NAME damn people will think its an authority like the others.  u could at least fofrmat it right like the code and headers all good like the others

Thanks for the support!

Fun read even though I have no clue what you're talking about. Thanks for taking a stab at this. I plan to one day attempt all this mumbo jumbo.

Great work.

Let's insult moderators and valued community members!!  You could at least start sentences with capital letters, use periods, and spell-check before commenting on other peoples fofrmatting...

That bug is weird, only shows up some of the time.  This will be really helpful once I finish my current project.  Thanks alot MRN!

I almost want to go see what the other 7 of your posts are like.

Thank you, MRN.  I don't have a lot of repeating tiles in my game (since it's a pseduo-3d type thing) but I'll definitely learn this so I can hopefully apply it in some way.

Well done. You must be saving a ton of space this way.
The metatile approach is also heavily used when doing scrollers, since each pair of OAM bits affects a 16x16 region, and reduces the amount of memory you need when doing collision detection and other algorithms.

Al

Very cool, MRN! I had to learn this myself for the scrolling demo I've been messing around with, and the technique has been invaluable.

Thanks for putting in the hard work and doing a tut write-up!

Glad I swung by the Brewery today. I don't think there is anything wrong with the post because the first sentence is certainly a disclaimer. If you are scared that the advice may be buggy then you wasted a full 3 seconds of your life reading the first sentence and then close the thread. No harm no foul.

I miss programming but have no idea how you guys find time for it, especially with a wife and pursuing advanced degrees or certifications. I'm lucky to find 5 hours of gaming in a week, let alone the hundreds (thousands?) of hours necessary to create a well-polished game. Good write up though, always great to share information.

Why were the posts by deleteme removed? They were finally formatted well and brought up very valid points that nobody else would.

Why don't you PM me a list of said points and we'll see what we can do to fix them.

Fixed!

This technically fits into the space of "Number 5", like Johnny, in my Game Engine Building series. So, if you're following along, re-read it...nicely.

FOR SHAME!!!  I can't believe that no one figured it out!!

I just figured out what the freaking bug was in this program.  I didn't push/pop the registers during NMI.  How retarted.  Anyway, for those of you who don't know what I'm talking about, you need to add:

  PHA                              ;protect the registers
  TXA
  PHA
  TYA
  PHA

right after the "NMI" start.  And then add:

  PLA                              ;restore the registers
  TAY
  PLA
  TAX
  PLA

right before you do the "RTI" at the end of NMI.  See my other write ups for details.  Then it should work.

Hi MRN. 

Is there any chance that someone has a source of MRN's code?

It's all in the zip file attached to the OP, right?

Wow, I've looked at this thread st least 5 times and never noticed it was there. That really would have been helpful. Thanks

Yeah, you have to be signed in in order to see attached files, so if you happen to visit the site on multiple devices or when not logged in, just make sure to double check later. I missed a lot of stuff due to this at first.

Oh, and congrats on getting to the point of at least looking into this particular tutorial, it is one of my favorites and has made a huge impact in my own projects, particular when combined with the lesson on attribute handling (week 8 I believe).

Hello,

After having extracted it, I can drag and drop the file "Background compression" and open it in my emulator (fceuxd sp) as if it was a NES file (actually there's no extension) but no way to get ONLY the source code.

How can i get it ?

Thank you.