This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Background compression: How to do it right?

Background compression: How to do it right?
by on (#153907)
In my game, the levels will be generated randomly, so I don't need to save them in the ROM.

But the game will have two screens worth of background data that simply loop.
During gameplay, they will be saved uncompressed in RAM, so that they can be quickly redrawn whenever an actual foreground/gameplay element appeared in front of them.

But what is the best way to save the layout in the ROM, so that it takes little space? And how do I do this best?

I think that I will not save the individual tiles, but abstract values that stand for a 16 x 16 element. This way, I can save 3/4 of the space.
How do I do this best? Do I declare a two-dimensional array where the Y dimension is the abstract value and the X dimension has four entries for each actual tile? Or is there a better way?

Also, how else can I compress it? I guess RLE doesn't work here since I probably won't have many identical elements next to each other. (The background will be some skyline of a city with skyscrapers, factories, cranes etc.)

Another problem: The compression algorithm and the mapping array shouldn't be bigger than the data if I just saved it uncompressed. Since I just have onebackground for the whole game, this might be an issue.


And how do I write the palettes the best?
While I understand that you can only map a palette for each 16 x 16 area instead of each tile, I never understood why one byte of the palette data is
a) mapped to a 32 x 32 pixel area instead of a 64 x 16 area (i.e. four blocks in a square instead of four blocks right after another).
b) the palette appears at the end of the background data instead of right after each tile collection that it belongs to.

What is the best way to access the correct palette value for any 16 x 16 pixel area? I mean, if palette data 1 referred to the 16 x 16 pixel blocks number 1, 2, 3 and 4 while palette data 2 referred to block 5, 6, 7 and 8, the calculation would be quite simple. But palette data 1 refers to blocks 1, 2, 17 and 18. And palette data 2 refers to 3, 4, 19 and 20.
What is the best way to set any of these palette entries in the PPU?
Re: Background compression: How to do it right?
by on (#153908)
To suggest an ideal codec, I'd need to see the 512x240 pixel background. Or I can explain how Super Mario Bros. stores its 768x208 pixel hill and cloud patterns.
Re: Background compression: How to do it right?
by on (#153910)
Quote:
I think that I will not save the individual tiles, but abstract values that stand for a 16 x 16 element. This way, I can save 3/4 of the space.
How do I do this best? Do I declare a two-dimensional array where the Y dimension is the abstract value and the X dimension has four entries for each actual tile? Or is there a better way?

You're describing metatiles. I JUST did my first one and I did it in a non-standard way but I'm sure there are some great threads on here about them.

Quote:
Also, how else can I compress it? I guess RLE doesn't work here since I probably won't have many identical elements next to each other. (The background will be some skyline of a city with skyscrapers, factories, cranes etc.)

I'd think that if you had one background and metatiles, you wouldn't need any other space saving techniques. You probably wouldn't even need metatiles. Two screens is just 2KB uncompressed.

Quote:
What is the best way to access the correct palette value for any 16 x 16 pixel area? I mean, if palette data 1 referred to the 16 x 16 pixel blocks number 1, 2, 3 and 4 while palette data 2 referred to block 5, 6, 7 and 8, the calculation would be quite simple. But palette data 1 refers to blocks 1, 2, 17 and 18. And palette data 2 refers to 3, 4, 19 and 20.
What is the best way to set any of these palette entries in the PPU?

Did you do the Nerdy Nights on scrolling? It's a decent starting point but attributes are pretty tricky.
Re: Background compression: How to do it right?
by on (#153911)
I don't know yet what the background will look like. My graphics designer will see what she can come up with based on the palette limitations. But all in all, it will be something like this:
Image
(Drawn by me, not by her.)

"Super Mario Bros." is probably totally different since most of the background there is just blank space. If I had to program that game, I would probably do it like this:
1 = cloud
2 = double cloud
3 = bush
4 = double bush
5 = hill
and then use three bytes per graphical item:
index (the above value), x and y.

darryl.revok wrote:
Did you do the Nerdy Nights on scrolling? It's a decent starting point but attributes are pretty tricky.

Yes, I did this chapter. But it got quite complicated, at least when I first tried it. However, scrolling itself and updating the data doesn't seem too complicated for me now. I also know how to access the attribute data. I'm just a little stuck with the following:

block 0 = attribute 0, bit 0 and 1
block 1 = attribute 0, bit 2 and 3
block 2 = attribute 1, bit 0 and 1
block 3 = attribute 1, bit 2 and 3
block 4 = attribute 2, bit 0 and 1
block 5 = attribute 2, bit 2 and 3
...
block 16 = attribute 0, bit 4 and 5
block 17 = attribute 0, bit 6 and 7
etc.

As long as I just hardcode the values, everything is fine. But when it comes to dynamically updating the attribute data for a specific block X, it becomes complicated. I'm sure there's a good mathematical formula for it, but I don't know it yet.
Re: Background compression: How to do it right?
by on (#153913)
A few games I know, have pointers to level data, which starts a list...3 byte per object, terminating in FF. The 3 bytes are...
1. Which object
2. Starting x
3. Starting Y
The object # indexes to another pointer to a list of tiles which goes in that object. It buffers it to RAM, then draws it line by line to the name table.

Edit: and the first byte of the object could be how many tiles wide it is, and the last byte terminates with ff again.
Re: Background compression: How to do it right?
by on (#153914)
I don't know if what I did was "good" so I hope someone will correct if I give bad advice, but what I did was something like this: (my metatile engine draws in vertical columns as they come on the screen)

    Set a variable as 11001100 or 00110011 depending on whether the attribute is on a multiple of 32 or just 16
    Use that to AND out the locations you're overwriting in the attribute byte preload
    Load the metatile number from map
    Load the color from the metatile list
    AND out the (theoretical) collision data
    Load the next color
    ASL that one over four spaces
    ORA the previous one to that (they have to be in this reverse order just because that's how the NES wants them)
    If your "attributeFlipFlop" variable (from the first step) is positive, ASL them over two more.
    ORA them to the byte in the preloader

The part that I thought was tricky is when I realized that I'm going to need to draw a split attribute every other time with half of the color from one side and half of the color from the other side. :) (This wouldn't actually be a problem most of the time. If you use vertical mirroring for a horizontal scrolling game you don't have this issue)

Edit: I thought it was confusing when I said that I +32 increment for drawing tiles when I was talking about attributes which are at +8 increment, so they have to be set manually. All I really needed to say is that I draw vertical columns. Also realized that the last part won't be a problem if you use vertical mirroring.
Re: Background compression: How to do it right?
by on (#153918)
Actually, if you're using vertical mirroring I don't think you'd need to do anything near as complicated as I described. You should be able to draw full attributes off-screen in intervals of 32 pixel scrolls. Then I'd imagine you'd just ORA the four color bytes from your different metatiles. It's still kind of a pain.

11001100 is a vertical arrangement
11110000 is a horizontal arrangement

The last attribute byte on the screen only uses the 4 lowest bits. It only controls two rows of tiles.

Surely others here have better advice but I hope this little bit helps.
Re: Background compression: How to do it right?
by on (#153929)
I'm sorry for doing self-advertisement, but have you looked at CompressTools?

This tool was really meant for situation where you have no idea what kind of compression algorithm works well with your data, so it try to compress them with all and shows how well it does.
Re: Background compression: How to do it right?
by on (#153935)
@Bregalad:

Thanks. I will check this out. But maybe darryl.revok is right: I have only one background for the whole game. If I save this as metatiles of 16 x 16 pixels, I have an array of 16 x 15 x 2 = 480 bytes plus an array of number_of_different_metatiles * 4 bytes plus all the attribute values. So, maybe it doesn't even need another compression algorithm. (If I don't have more than 16 meta tiles, I could even compress the 480 bytes into 240.)


@darryl.revok:

I'm still a bit lost. I actually wanted to update the offscreen background every 16 pixels. While I know (or at least can look up) which part of the attribute table belongs to which tile collection (i.e. I know how to write the code to update, let's say, the attributes for the 27th meta tile), I still don't really know how to write a general function that calculates me the current attribute address.

I'd need something like this:
Code:
GetAttributeAddress(in tileAddressLowByte, in tileAddressHighByte, out attributeAddressLowByte, out attributeAddressHighByte, out shift)


I guess I could write down all tile addresses and then write all attribute addresses and necessary shifts next to it and try to work out a mathematical formula. But I assume other people know the answer already.
Re: Background compression: How to do it right?
by on (#153940)
Quote:
number_of_different_metatiles * 4 bytes plus all the attribute values.

Your color values will generally be tied to the metatile. At least this is how I did it. You only need two bits for color, but those have to go somewhere, so it's a good idea to share that byte with collision data.

attributeAddressHighByte = opposite nametable start address plus three, always. So if the player is on nametable $2000, and you are drawing offscreen, your attributeAddressHighByte is $27. (I just noticed a big problem with Nerdy Nights in this aspect is that it describes the base attribute location as $20C0. This is incorrect and would explain why I couldn't figure it out when I did the tutorial the first time and probably why you had trouble as well. The attributes are at the end of the nametable. $2000-$23BF are your tiles)

The Nerdy Nights formula for attribute nametable address low byte is perfectly fine. That's pretty much exactly what I did except I started with my tileNametablePosition low byte first to save a few steps since it had already been LSRed three times.

If you use the nerdy nights calculations for tile nametable location and attribute nametable location, they should be in the same position. If you're drawing a vertical column, with PPU in +32 mode, an increment of 8 aligns with the tile. That's probably what you're missing.

My attribute uploader looks something like this:

Code:
DrawNewAttributes:

  LDX #$07
 
DrawNewAttributesLoop1:

  LDA #%00000000                  ; Set to increment +1 mode
  STA $2000
 
  LDA $2002                     ; Read PPU status to reset the high/low latch

  LDA #$23
  STA $2006                     ; Write the high byte of column address

  LDA nametableColumnAttributesLo
  STA $2006                     ; Write the low byte of column address

  LDA preloadNametable01Attributes, x           
  STA $2007                                                     ; Write combined attribute data from preloader ( must combine from multiple tiles

  LDA nametableColumnAttributesLo
  CLC
  ADC #$08
  STA nametableColumnAttributesLo                ; Increment write position by 8 for next attribute in vertical arrangement
 
  DEX
  BPL DrawNewAttributesLoop1


The formulas I used were only very very slightly modified versions of the Nerdy Nights formulas and you wouldn't have to do any modifications other than the correction I described earlier. With one little tweak, this is the formula from Nerdy Nights. It will work now since I changed $20 to $23:

Code:
 LDA nametable
  EOR #$01          ; invert low bit, A = $00 or $01
  ASL A             ; shift up, A = $00 or $02
  ASL A             ; $00 or $04
  CLC
  ADC #$23          ; add high byte of attribute base address ($20C0)
  STA columnHigh    ; now address = $23 or $27 for nametable 0 or 1
 
  LDA scroll
  LSR A
  LSR A
  LSR A
  LSR A
  LSR A
  CLC
  ADC #$C0
  STA columnLow     ; attribute base + scroll / 32


Does that help any?

So, basically, you have 64 attributes, 8 horizontal and 8 vertical. They are laid out the same as your tiles in this sense that they progress in horizontal rows, which is why +8 is a vertical progression.

http://wiki.nesdev.com/w/index.php/PPU_programmer_reference#Attribute_tables Has a great visual reference for the sake of understanding, but using simple formulas will handle the positioning for you.
Re: Background compression: How to do it right?
by on (#153945)
Super Mario Bros. has four different metatile definition tables: one for metatile values $00-$3F, one for $40-$7F, one for $80-$BF, and one for $C0-$FF. This lets it use bits 7-6 directly to form metatile numbers.

You plan to have randomly generated terrain in front of a 512x240-pixel repeating background. Will it scroll in both directions? And how are you representing the terrain for collision? Is it a 32x15-metatile sliding window like SMB1 uses or something else? The strategy for forming attributes may differ based on your answers to these questions.
Re: Background compression: How to do it right?
by on (#153964)
I guess I'll have to do that chapter from Nerdy Nights again. I was hoping that I can skip it, but it looks like I have to do it after all. Maybe then I'll understand better what you told me.

tepples wrote:
You plan to have randomly generated terrain in front of a 512x240-pixel repeating background. Will it scroll in both directions? And how are you representing the terrain for collision? Is it a 32x15-metatile sliding window like SMB1 uses or something else? The strategy for forming attributes may differ based on your answers to these questions.

My game shall look like this:

We have three background sections:
The status bar (six tiles high)
The upper background (12 tiles high).
The lower background (12 tiles high).

The two background parts are two screens wide and are repeated when the level scrolls.

The upper background never overlaps with the actual foreground gameplay stuff. That means this background can be written once when the level starts and never needs to be touched again.

The lower background overlaps with the foreground. That means this background regularly has to be drawn anew since the background stays the same, but the foreground is always new and doesn't simply repeat. So, the overlapping between foreground and background can happen differently every time the screen loops.

The foreground is built very simple: The game plays on rooftops of houses. So, the level data is nothing more but the following:
Length of a foreground house.
Height of a foreground house.
Length of a gap between this house and the next house.
Repeat.

The level data will probably be put into some generic array. This array is used for deciding where a character has to stand and where he falls down. And this array is also used to draw the tiles for the house when it's time. The content of the array is generated randomly according to specific rules.

The game only scrolls in one direction and it uses auto scrolling. If your character stands still, the left screen border will come closer. And if the character is put outside the screen on the left side, you lose a life. (So, it's neither like in a shoot em up where your character automatically moves forward with the same speed as the screen when you don't do anything. Nor is it like SMB3-like auto-scrolling levels where the character is simply pushed forward when he stands at the left border.)


By the way: Meta-tiles only have a meaning at the start of the level when the background data is extracted and written to the PPU. When the level is actually played, I guess I will put the whole uncompressed lower background in an array in the RAM and just copy the parts 1:1 that need to be updated in the PPU whenever the time is right. Unless you tell me this is a bad idea.
Re: Background compression: How to do it right?
by on (#154075)
Quote:
The two background parts are two screens wide and are repeated when the level scrolls.


If what you mean by this, is that two screen will simply repeat, you can do this very easily. Just draw two nametables. No complex scrolling code at all, for that part. The parallax effect will take some work, especially with the status bar as well. Hopefully someone more qualified can help with that part.

Quote:
The foreground is built very simple: The game plays on rooftops of houses. So, the level data is nothing more but the following:
Length of a foreground house.
Height of a foreground house.
Length of a gap between this house and the next house.
Repeat.


This is where you'll need some sort of new column drawing as well as a routine for procedurally drawing the roofs. This much I know you know as well.

Quote:
By the way: Meta-tiles only have a meaning at the start of the level when the background data is extracted and written to the PPU. When the level is actually played, I guess I will put the whole uncompressed lower background in an array in the RAM and just copy the parts 1:1 that need to be updated in the PPU whenever the time is right. Unless you tell me this is a bad idea.


Okay, I'm trying to look at what you've asked from a few different perspectives. Are you talking about PPU RAM or CPU RAM? Let's talk about the upper background first. You say that is two screens and that's all. Now, I don't know much about doing the sprite 0 hit or parallax, but unless that changes the equation, these two backgrounds can go into PPU RAM and stay there throughout the level. When your hScroll wraps back around, you'll be at the start of the background, which is what you want. You'll just have to make it switch nametables like they show you in the nerdy nights so that you don't keep popping back to the beginning of the first nametable when hScroll wraps to 0.

So, whether they come from metatiles or individual tile definitions, the tiles in your upper background can get uploaded to the PPU RAM nametable at the start of the level and never be touched again. That may have been what you meant but I'm not certain.

Now, for the lower background, those will of course have to be drawn since the height and length of gap for the buildings is random. Whether or not those are drawn from individual tile definitions or metatiles is up to you, but there are advantages of each. The main reason for using metatiles is to conserve map space, but I don't honestly think this is too much of a consideration for your game. Let's consider the space that your backgrounds will take up uncompressed. Your upper background has to be stored in ROM, and that's 12 tiles high, times 64 tiles wide for 2 screens. That's 768 bytes. Your status bar is six tiles high and 32 tiles wide, so that's 192 bytes. You've now got one screen's worth of uncompressed tile data, add attributes for all of those background tiles and you've got one kilobyte of ROM space used for your predefined background areas.

The lower background, won't be stored in the same way. You can use metatiles for drawing those and there are good reasons to consider that, but I don't think space is really one in your situation. Here's why: The lower background arrangement will not be stored in a predefined array like your upper background. You need 1 KB of predefined map layout array to do what you described. The data for drawing your lower background will be stored in a manner that is built around your random roof drawing routine. I'm not going to get deep in speculating how that will work, but I know the routine will build houses from things like height and width. It won't be reading them like a map layout from Mario that was hardcoded into the game. I'm guessing it will have things like definitions for the tile that defines the side of a house, the corner, the roof, then when it hits the end of the length, it draws another corner and another side.

Metatiles could even safe space on that, but it depends on how your houses are designed, and other things. My point is that you probably don't need to do it for the sake of saving space. Let's say uncompressed that the definitions of your individual house parts are another KB. That's still just 2 KB you've used for maps and that's probably plenty small.

Other reasons to consider metatiles asides from space might include but would certainly not be limited to: color, and the fact that one attribute can only define 2x2 tiles and not less. Especially with randomly generated buildings, you don't want it to generate a house with bizarre color artifacts. I think the size of the parts that define your houses would play into the decision of whether or not to use metatiles. You may want to consider how many actual tiles it takes you to define something like the corner of a roof, or like a section of brick. If it's all broken up into 8x8 then that might be an argument for not using metatiles, however, If it takes 16x16 pixels to build a roof corner, you'll have to tell your house factory to draw the leftmost column first, which only draws the left side of your roof corner, and then follow that with the next column to draw the right side of your roof corner. It would be more cumbersome. I'm guessing that things like windows, chimneys, just general parts that define a house, may be bigger than 8x8 pixels.

I hope all of that wasn't too confusing. It is a complicated topic with a lot of things to consider so I tried my best to be concise yet cover what I would be thinking about to approach that task. I still have a lot to learn though so if someone else can give you better advice please take it. Hope this helps!
Re: Background compression: How to do it right?
by on (#154108)
Thanks for your elaborated explanation. Some things of it I already know, like how scrolling works in general, nametable switches etc. and that I don't have to touch the upper background once it is written to the PPU. I even have a method for parallax scrolling.

The only problems were the following:


How do I dynamically map the color values to the correct tiles?

The actual tiles are laid out differently from the color values:
In the PPU memory, the tiles are ordered in a straight line: First come the 32 tiles of the first row, then the 32 tiles of the second row etc.
But the color values are mapped as squares of 4 x 4 tiles. So, the first color value doesn't map to the tiles from 0 to 15, but to the tiles 0, 1, 2, 3, 16, 17, 18, 19, 32, 33, 34, 35, 48, 49, 50, 51. And then the second color value maps to 4, 5, 6, 7, 20, 21, 22, 23 etc.
That's why I have to read the Nerdy Nights chapter on scrolling again. And in the meantime, I came up with an own possible solution. But I'll have to try this out.


And my second question was this: Since the the lower background has to be re-written every time since the foreground draws in front of it, shall I save the values in RAM (CPU RAM) uncompressed or shall I leave it as meta-tiles?

I.e. it was referring to what you mentioned here:
darryl.revok wrote:
Now, for the lower background, those will of course have to be drawn since the height and length of gap for the buildings is random. Whether or not those are drawn from individual tile definitions or metatiles is up to you, but there are advantages of each.


When it comes to the ROM, I'll save all background as meta tiles, so that I have a 2 * 16 * 15 map (plus some color values and meta tile mappng data) instead of a 2 * 32 * 30 map.

The upper background of it gets extracted and is written directly into the PPU. That's easy. We don't need the ROM data anymore and we don't need CPU RAM to store it.

But now my question was:
Since the lower background (2 * 16 * 6 meta tiles) has to be written more than once, shall I
a) extract the data from the ROM into an array in RAM at the beginning (which would need 2 * 32 * 12 bytes) and then update the PPU with the already extracted data?
or
b) access the ROM data whenever a new column needs to be written and extract the corresponding data on the fly before writing it into PPU?

The first method saves time: I only need to extract the data once and then I can put it into the PPU directly.
On the downside, I have to reserve an array of 768 bytes that permanently occupies the CPU RAM and that cannot be used for anything else.

The second method requires that I extract data from the ROM whenever the screen has moved 16 pixels. And then I can write the extracted data into the PPU.
But the advantage is: For this extraction, I only need an array of 2 * 12 = 24 bytes since I only need to put one column into the PPU. Or, if I optimize it, I don't even need this if I extract one tile at a time from the ROM's meta tile data and put it into the PPU.
But this whole procedure takes more time since the extraction has to be done every 16 pixels instead of once at the beginning.


Now, there's something that I don't understand from your statements:
darryl.revok wrote:
The lower background, won't be stored in the same way. You can use metatiles for drawing those and there are good reasons to consider that, but I don't think space is really one in your situation. Here's why: The lower background arrangement will not be stored in a predefined array like your upper background.

Well, yes, it will be stored in the same way. Well, at least the "master data" will be.

We basically have this layout (I omit the color data here for simplicity):

- One array in ROM that describes the meta tiles for the lower background (32 * 6 bytes).

- If I use method a) from above, one array in RAM that describes the whole background (64 * 12 bytes) and that gets filled with the extracted data from the ROM.

- One array in RAM for two tile columns (i.e. the screen gets updated every 16 pixels) (2 * 12 bytes) that saves the combination of lower background and foreground for writing into the PPU.

darryl.revok wrote:
Metatiles could even safe space on that, but it depends on how your houses are designed, and other things. My point is that you probably don't need to do it for the sake of saving space.

Right. The houses etc. and the combination of foreground and lower background has nothing to do with meta tiles anymore. These are saved as-is.

My only question was:

The "panorama" picture of the lower background, shall I extract this into CPU RAM once at the beginning and then take a slice of it whenever the screen has moved 16 pixels and combine this slice with the foreground whenever it's time?

Or shall I take one slice of the compressed panorama picture from ROM every 16 pixels, extract this slice on the fly and then combine this slice with the foreground?

darryl.revok wrote:
Other reasons to consider metatiles asides from space might include but would certainly not be limited to: color, and the fact that one attribute can only define 2x2 tiles and not less. Especially with randomly generated buildings, you don't want it to generate a house with bizarre color artifacts.

This shouldn't be a problem. I already condsidered the fact that the smallest graphical item on a house that doesn't use the general "house palette" has to be a multiple of 16.
This means: Windows with a width and height of 8 or 24 aren't a problem since I'll abuse the global background color (the blue of the sky) as the color for the windows, so windows use the same palette as a blank house wall and the house borders.
But if there's some kind of dirt on the house that appears in another color, I'm aware that it has to be 16 * 16 or 32 * 16 or 32 * 32 etc. and never 8 or 24 pixels.