You're right in that the method you outlined wouldn't be terribly useful. But you are thinking along the right lines! Use smaller parts of a byte to define what you might normally take a whole byte or more to do. The best ways to save space include both the graphical consolidation known as metatiles, and a more literal compression that you might think of in terms of zip files.
As Memblers said, "metatiles" are a great technique that is used pretty much universally on the NES and many other game platforms. Considering a single 8x8 tile being the smallest piece a NES can think about, a metatile combines several of those so you can refer to them as one logical piece. Here are three examples of ways to represent your tiles:
The first is probably what you are doing now, literally storing the ID number of every single tile, 32 across by 30 down. Very wasteful.
The second combines each block of four tiles into a metatile. The graphics are all the same, but the way you store the data changes. With this method you have a table that records what tiles make up each tile - you're saying "tile 1 = 1, 2, 5, 6" etc. You have to write a routine to decode this and store the literal tiles in the NES memory as before, obviously.
The third example is something you might see in Super Mario Bros. You can compress your data as much as you want, and if you have a lot of large chunks of blocks that always go together you might just want to record that a single ID number results in one huge background object. Or another way to look at it is, having multiple levels of metatiles. In the picture, we've already said that "tile 1 = 1, 2, 5, 6" and so forth; then we go to the next level and say that "big tile 1 = 1, 2, 3, 2, 4." It can get quite complicated to decode, depending on how far you take it.
Me, I stopped at the second level this time. Here is the table I have for my current test ROM:
Code:
metadata:
.db $00,$00,$00,$00 ;00 - empty
.db $E3,$E6,$E6,$E3 ;01 - solid center
.db $F2,$F3,$F4,$F5 ;02 - solid variant (big bubble)
.db $F6,$F7,$F8,$F9 ;03 - solid variant (medium bubbles)
.db $E8,$E6,$E2,$E3 ;04 - right wall
.db $E3,$EB,$E6,$E7 ;05 - left wall
.db $E4,$E1,$E6,$E3 ;06 - floor
.db $E3,$E6,$EC,$EA ;07 - ceiling
.db $E0,$E1,$E2,$E3 ;08 - top left corner
.db $E4,$E5,$E6,$E7 ;09 - top right corner
.db $E8,$E6,$E9,$EA ;10 - lower left corner
.db $E3,$EB,$EC,$ED ;11 - lower right corner
.db $E3,$E6,$E6,$EE ;12 - top left bend
.db $E3,$E6,$EF,$E3 ;13 - top right bend
.db $E3,$F0,$E6,$E3 ;14 - lower left bend
.db $F1,$E6,$E6,$E3 ;15 - lower right bend
And having recorded that, here is an example of a map screen taking advantage of it:
The next type of compression I apply is called RLE compression, or Run Length Encoding. It's very simple. See all the zeroes in a row up there? Rather than storing "0, 0, 0, 0, 0, 0" etc., you can just store "16, 0" - that is, just saying "there are 16 zeroes in a row here."
Now obviously this does not make sense if you have a lot of individual tiles. You are wasting space if you have to say "1, 4, 1, 2, 1, 5" (there is 1 four, 1 two, 1 five...) That is why you program in special cases that let you say "there are 16 zeroes in a row" when you need to, but otherwise you can just store the IDs literally.
My own rule that I have coded is this: if the current byte is less than 128, then that is simply the next tile in the sequence. if the current byte is greater than 128, subtract 128 from it and repeat the next byte that many times.
In other words, I am using the highest bit as a flag to tell the program how to treat this byte. If a byte is in the format %0xxxxxxx, that means the ID number is just whatever the byte is, which in compression terms is called a "literal." Since I'm using less than a hundred metatiles this isn't a problem. If however it is in the format %1xxxxxxx, then ignore that 1 and use the rest of the byte as a loop counter for the following byte. As an example, %10000101 means repeat the next byte 5 times.
So knowing that, here is what the above map looks like compressed:
Code:
bg:
;simple RLE compressed background using 2x2 metatiles
.db 131,0,4,2,5,0,0,4,3,1,1,2,1,3,2
.db 131,0,10,7,11,0,0,4,1,2,3,1,2,1,1
.db 136,0,10,131,7,13,1,1,2
.db 140,0,10,131,7
.db 144,0
.db 6,9,142,0
.db 1,5,0,0,8,9,138,0
.db 2,5,0,0,4,5,138,0
.db 3,14,6,6,15,5,138,0
.db 1,2,2,1,1,14,6,6,9,132,0,8,6,6
.db 12,131,7,13,3,1,2,14,9,131,0,4,3,1
.db 5,131,0,10,132,7,11,131,0,4,2,1
.db 5,140,0,4,1,2
.db 5,140,0,4,3,3
.db 14,140,6,15,2,1
You should be able to visibly compare the two and see how it works.
So with these two systems working together, we went from 32x30 tiles, which is 960 bytes to store one screen, down to 134 bytes for the screen and 64 bytes for the table that helps define it. That doesn't include the size of the subroutines that interpret the data but it definitely saves us a lot of space.
Just for good measure, here is the subroutine I use to unpack the above RLE-compressed map into RAM:
Code:
unpack_screen: ;unpack an RLE compressed screen into RAM (2x2 metatiles)
;tmpada = address of compressed screen data
;tmp8y = index of compressed screen data
;SCREEN = constant address in RAM where data is unpacked
;tmp8x = index of RAM location
;x = loop counter for RLE runs
;a = tile data being loaded and stored
;*** make section to detect current screen and get address from table
;*** for now, load a single temporary bg
lda #<bg
sta tmpada ;store address of screen data in tmpada
lda #>bg
sta tmpada+1
ldy #0
sty tmp8x ;index of how many metatiles have been unpacked
-- ldx #1 ;used to handle RLE bits
lda (tmpada),y
bpl + ;if last bit not set, it's a literal
and #%01111111 ;clear last bit
tax ;x becomes the loop counter
iny
lda (tmpada),y ;load tile to be repeated
+ sty tmp8y ;back up data index
- ldy tmp8x
sta (SCREEN),y ;store tile in screen RAM
inc tmp8x ;increment RAM index
dex
bne - ;loop if we're in an RLE run
ldy tmp8y ;restore data index
iny
ldx tmp8x
bne -- ;we are done copying data when RAM index wraps
rts
If this can be written more efficiently, I am all for hearing it, by the way.
I can get stuff to work but I am not very confident in my finesse.