Choosing a Tile Compression Method?

[TylerBarnes 183]

So, I am slowly easing my way into more complicated aspects of NES ASM, and was curious about compression. I am still not really what you would call experienced. (only a simple project under my belt, with no games physics, mechanics, or levels)

I'm going to play with a simple level uncompressed, much like the Nerdy Nights week about scrolling, however I know the next step is compression. 

I was curious to what is the general opinion for what compression method a beginner should look at first? 

If it matters, for arguments sake, lets say it is a platformer and I want to compress nametables/level data. 

[Parisoft 23]

Take a look at metatiles and RLE

[toggle switch 26]

for a beginner, i strongly suggest using a simple method consisting of 4x4 metatiles, each one made up of 4 2x2 metatiles. 

4x4 metatiles are wonderful to work with as a programmer because they vastly simplify the process of setting up palette data. 

additionally, each 4x4 metatile takes 2 bytes to define and defines 17 bytes within your nametable, leading to a better than 87.5% reduction in data. of course, there is overhead to consider, but it's actually fairly minimal - the amount of space it takes to define all the 2x2 and 4x4 structures is roughly equivalent to a few screens of uncompressed data. 

[TylerBarnes 183]

Thank you both for the suggestions. I see many more resources about how to setup meta tiles so that seems to be the common way to go. For arguments sake, if RLE is the way I want to go is there a decompression routine that is standard? or just build one purpose built to your program? 

I'm not sure how would be best to set it up, but here is how I imagine a theoretical decompression routine to work (untested). For clarity I'm only compressing/decompressing a 32 tile row, and I'm imagining the PPU is off and NMI disabled.

More or less the concept? 
 

data  = $10                ; Address Pointer
dataH = $11
arrayLength = $12 

LoadStream: 
	LDA #<RowData      ; Setup pointer to data stream
	LDX #>RowData
	STA data
	STX dataH
Init:
	LDA #$20           ; Load PPU address to write
	LDX #$00
	STA $2006
	STX $2006

	LDY #$00           ; Init an index counter
	LDA (data), y      ; Load first byte in stream
	STA arrayLength    ; Declare size of array to read
	INY
Fetch:
	LDA (data), y      ; Fetch segmentLength
	TAX                ; Set as decrimentor 
	INY                ; Incriment Index
	LDA (data), y      ; Fetch tile
Loop: 
	STA $2007          ; Write Tile
	DEX                ; Decriment segmentLength
	BNE Loop           ; Loop segemt until #$00
	INY                ; Incriment Array Index
	CPY arrayLength    ; Compare with total array length
	BNE Fetch          ; Keep fetching until array end

Forever: 
	JMP Forever
	
RowData: 
	.db $09            ; arrayLength 
	.db $08            ; segmentLength
	.db $02            ; tile 
	.db $04            ; segmentLength
	.db $2A            ; tile
	.db $0A            ; segmentLength
	.db $34            ; tile
	.db $0A            ; segmentLength
	.db $00            ; tile

 

Edited December 4, 2019 by TylerBarnes

[chromableedstudios 24]

On 12/3/2019 at 5:44 PM, TylerBarnes said:

RLE is the way I want to go is there a decompression routine that is standard

I think shiru includes an asm RLE example with NES screen tool

[TylerBarnes 183]

11 hours ago, chromableedstudios said:

I think shiru includes an asm RLE example with NES screen tool

I have been meaning to download that tool. I'm still using a very basic flash based tile editor. Doesn't even have an undo function, lol. Only really chose it cause it would run on mac. 

[gauauu 79]

RLE makes a lot of sense on something like a screen-by-screen game, or a title screen, but (I think?) is harder to deal with on a large scrolling level.  You can decompress the level data quickly, but going the other direction (from a screen coordinate back to source data) is harder and slower.  So when you want to look up collision data for a certain tile, it will probably be more complicated than a metatile approach would be.

[Orab Games 97]

On 12/9/2019 at 12:40 AM, chromableedstudios said:

I think shiru includes an asm RLE example with NES screen tool

It does and I have used it. It works great with the proper decompress code. However, it's designed for tile by tile and not metatiles (that I know of, I haven't figured out any other way). I know plenty of programmers who just use RLE compression and call it a day. Some will write their own tools to compress metatiles with RLE as well, which can eat a lot of CPU time. From what i gather, you are trading CPU time for storage space with compression. With the advantages of homebrew mappers like GTROM and UNROM512, storage space is not much of an issue anymore unless your game is overly huge!

If I were you, I would start with RLE and go from there. NESScreenTool does a great job. Do some research to understand how it works. For example, let's say that you have 2 tiles next to each other that are the same, the other tiles on either side are different. So, you have a pair ($03,$08,$08,$01). Some RLE compression tools will compress the $08 and others won't. It is actually faster to write the $08 twice than it is to uncompress it in some RLE tools. It simply comes down to how much more code do you want to write.

Edited December 13, 2019 by Orab Games

[Orab Games 97]

On 12/3/2019 at 6:44 PM, TylerBarnes said:

For arguments sake, if RLE is the way I want to go is there a decompression routine that is standard?

Here are the 2 common ways (in my short research form a couple years ago) that I saw RLE work for different tools. There are variations of this, but these were the basic concepts that I grasped.

;First way: Using an indicator flag to tell your code when you are decompressing. Otherwise, just write the value
uncompressedBackgroundTable:
.db $11,$11,$11,$11,$11,$05,$07,$1f

decompressFlag  = $ff                ; You can't store tiles at $FF if you do this.
tileValues = $11,$05,$07,$1f
arrayLength = $05 

compressedBackgroundTable:
.db $ff,$11,$05,$07,$1f

Here, you would write your code pointing at the compressedBackgroundTable to say if table value is $ff, then write tile $11 five times. Then write tiles $07 and $1f next. The result on the screen would look like the uncompressedBackgroundTable. You saved 3 bytes of storage in this example. Most RLEs using this format will just write single tiles and paired tiles to the screen without compression as it is faster and saves space. I forget how shiru's tool exports the tables for pairs.

;Second way is not to use an indicator flag and always compress, even if it is 1 tile or a pair of tiles
;You would decide that if the first byte in the table is length or tile. In this example, I went length, tile.

uncompressedBackgroundTable:            ;Tiles on the screen
.db $11,$11,$11,$11,$11,$05,$07,$1f

compressedBackgroundTable:				;Same tiles compressed
.db $05,$11,$01,$05,$01,$07,$01,$1f

Here, you would write your code to look at the first value in compressBackgroundTable and store the array length ($05). Then you would look at the second value to see what tile to write ($11). Then you would repeat until the end of the table. As you can see in this example, no bytes were really saved. The coding is much easier for this, but the compression can be worse depending on your screen. Busy screens could take up more data.

 

Finally, you will have to write in your code some way to tell the system to exit the background writing loop. Since the table is compressed, the tables will be different lengths. You can figure out the best way for you, but I like to end my tables with a flag. In Example 1, I would use $FE as the last value in the table. If the code sees that value, it will exit the loop. However, now you can't store any tiles in $FE or $FF (well, technically you can if you use a third flag to ignore these 3 flags as flags). In the second example, you could just use $FF as the table ending flag.

;From the first example, $fe tells the code to stop writing tiles.

compressedBackgroundTable:
.db $ff,$11,$05,$07,$1f,$fe

 

[TylerBarnes 183]

Thank you that makes a lot of sense. Instead of having an array length (Which can possibly be larger than $FF, so extra logic would have to be written), it is a better idea to just have an ending marker and detect it's value to end the stream. And a starting marker to tell if it is a compressed stream or uncompressed. 

However,  the syntax you are using is confusing to me; This took me a few moments to realize what you meant.

In ASM6 using "decompressFlag = $FF" would designate location $00FF in RAM as a variable, and then leave the value #$00 unless initialized in setup or in a routine before hand. It is not for value assignment.

If the idea is to declare a constant for the decompression routine to detect, you would have to use decimal numbers like

decompressFlag = 255    ; Assigned the label with value $FF

or use EQU to equate the label to a string

decompressFlag EQU $FF   ; ASM6 assembler replaces label with $FF

However if the idea is to detect $FF as a flag, I do not feel declaring this a variable or constant is too necessary. I would just implement that $FF detection this way with a raw coded value; Set it and forget it. 
 

	LDY #$00                         ; Set index into Level Data 
DetectCompress:
	LDA LevelData, y                 ; Load first item in array 
	CMP $FF                          ; Compare with value $FF
	BEQ Decompress                   ; If equal decompress
Uncompressed:                            ; Otherwise load uncompressed
	[Load data uncompressed] 
	RTS
Decompress: 
	[Do decompression] 
	RTS 

LevelData: 
	.db $FF,$11,$05,$07,$1F,$FE

---------------------------------------------------------
 

5 hours ago, Orab Games said:

However, now you can't store any tiles in $FE or $FF

This is actually might not be true, at least the way I'm picturing it.

So the routine has two main sections after detecting the compressed/uncompressed value, One is fetching the segment length, the other is fetching the tile number. You only need to detect flags for ending the decompression routine while it is attempting to fetch a segment length. Once a length is actually loaded in, it then just blindly loads the tile value and writes that tile N number of times (based on the segment length). This holds true because there is no reason to load a segment length without any tiles to follow. So the end will always be fetched as if it was a segment length and never a tile value. 

So tiles $FF and $FE in CHR rom are perfectly fair game. It is just that those segment lengths would not be allowed. 

So if I take my original simplistic RLE example that could look like:
 

Fetch:
	LDA (data), y          ; Fetch segmentLength
	CMP #$FE               ; Detect if end of Array
	BEQ EndDecompression   ; Exit if true
	TAX                    ; Set as decrimentor 
	INY                    ; Incriment Index
	LDA (data), y          ; Fetch tile
	.
	.
	.
	.
EndDecompression: 
	RTS

All these different factors makes me realize there would not be a one size fits all, and writing/modifying something tailor made is the way to go for this stuff. 
 

Edited December 13, 2019 by TylerBarnes

[Orab Games 97]

Yeah, there are many different ways to do it. But if you use someone else's compression tool (like shiru's), then you are bound by how they export the data. I do believe for values of 255 tiles in a row, they just do 255 and then start over with the same tile. So, if it was 275, you would write it 255 times and then do it again for 20 times.

36 minutes ago, TylerBarnes said:

This is actually might not be true, at least the way I'm picturing it.

Again, this all depends on the exported code and how you program it. For some reason, this was sticking in my head for what I had to do. I'd have to check the code.

[FrankenGraphics 104]

One argument against 4x4 meta-meta-tiling: it pretty much squares the time it takes to make a level, because manually looking up and placing meta-metatiles (and the metatiles within) consumes a lot of time, despite your best efforts to organize them (and the organization always end up half done because you want to be practical and move quickly). 

Additionally, often you find yourself in a situation where you absolutely need to modify a tile, or a metatile. Now you need to make sure the meta-metas placed on your screens look and function okay. Often, they will not. then you need to solve those problems as well. 

It seems convenient at first when you populate the first handful of screens, but is best suited if the metas and meta-metas are defined for small levels or divided-up stages. The more screens you add using the same meta library, the slower your process making them will be.

If you write an editor that will handle the sorting and metatile making for you, you can save a lot of time - up until you hit the hard limit of how many you can make. then it will become a puzzle solving excercise. 

Edited February 9, 2020 by FrankenGraphics

[toma 66]

On 2/9/2020 at 9:44 AM, FrankenGraphics said:

One argument against 4x4 meta-meta-tiling: it pretty much squares the time it takes to make a level, because manually looking up and placing meta-metatiles (and the metatiles within) consumes a lot of time, despite your best efforts to organize them (and the organization always end up half done because you want to be practical and move quickly). 

Additionally, often you find yourself in a situation where you absolutely need to modify a tile, or a metatile. Now you need to make sure the meta-metas placed on your screens look and function okay. Often, they will not. then you need to solve those problems as well. 

It seems convenient at first when you populate the first handful of screens, but is best suited if the metas and meta-metas are defined for small levels or divided-up stages. The more screens you add using the same meta library, the slower your process making them will be.

If you write an editor that will handle the sorting and metatile making for you, you can save a lot of time - up until you hit the hard limit of how many you can make. then it will become a puzzle solving excercise. 

I definitely agree with using metametatiles on a per-area basis. Eskimo Bob and Alfonzo both used huge sets of 256 metametatiles for the entire game. For Mall Brawl I used smaller sets of varying sizes depending on what was required for the level and it really helped simplify things, especially when I wanted to make changes.