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

My map compression scheme.

My map compression scheme.
by on (#100833)
Hi.
I was thinking about a map compression for my game. Every map is 0xE0 bytes long in it's uncompressed state.
We'll be unpacking it to RAM(for various reasons). Also, keep in mind that number of meta tiles I use is 0x1D.
So here it is:

Game assumes that map is all 0x00 at start. Also, we assume that our first Metatile number to unpack is 0x01.

Byte0: Coordinates
bit7-bit4 are used as Y coordinate.
bit0-bit3 are used as X coordinate.
*note* If this byte is FF, then it is end of map unpacking routine.
*note* If this byte is EF, then next byte will not be a "Size" byte, but a "Control" byte.

Byte1: Size.
bit7-bit4 number of Metatiles to unpack vertically
bit0-bit3 number of Metatiles to unpack horizontally

Byte2: Control Byte. Do not appear unless called by Byte0.
bit7:Used as end of current Metatile ID. Uses AND on control byte (So we get rid of bit7) to draw the next Metatile ID number. Max metatile number is 0x7F.
bit6:Repeat last "Size" byte. AND Control byte and use bits 4-0 as number of repetition. Max number of repetition is 0x1F
bit5:Use vocabulary. AND and use bits 4-0 as X to read a small array from vocabulary. Max number of vocabulary entries is 0x1F.(more than enough, to be honest).

bits 4-0:Multi purpose bits.

Example:
Coordinate byte: 0xA0. Size byte: 0x3F.
Coordinate byte: 0xEF. Control Byte: 0x81
Coordinate byte: 0xA2. Size byte: 0x38
Coordinate byte: 0xEF. Control Byte: 0x82
Coordinate byte: 0xA5. Size Byte: 0x32
Coordinate byte: 0xAB. Size Byte: 0x32
Coordinate byte: 0xEF. Control Byte: 0x92
Coordinate byte: 0x91. Size Byte: 0x00
Coordinate byte: 0xEF. Control Byte: 0x86
Coordinate byte: 0x9E. Size Byte: 0x00

Will result in this:
Image

So, results are like this:

Uncompressed: 0xE0 bytes.
RLE: 0x48 bytes.
My scheme: 0x14 bytes.

Yeah, results will vary from map to map.
The reason I'm writing this is that maybe can someone give me a hand with improving this..."compression" method?
It's unconventional to use "repetition flag" 'cause I'll need to call control byte for second time for example.
Re: My map compression scheme.
by on (#100834)
It reminds me of the object based encoding of SMB1/SMB3/SMW. Have you ever played with Lunar Magic?
Re: My map compression scheme.
by on (#100835)
Nope. So SMB1 do familiar thing? I'll take a look into Lunar Magic, maybe there's something interesting.
Re: My map compression scheme.
by on (#100840)
I noticed you never called FF for byte 0. Does that mean this is not necessary, or that it wasn't done unpacking yet?
Re: My map compression scheme.
by on (#100841)
How about boxes with 'patterns' in them? You can specify a box, then include 1 bit for each tile in the box, indicating whether it gets drawn or not.
Re: My map compression scheme.
by on (#100842)
One thing that I this reminds me is that Ecco uses... a weird format for the metatiles. Instead of being a raw tilemap, it has metatiles of varying sizes and tells the game where to draw them. In many cases it uses a bunch of large metatiles for the overall shape then uses smaller metatiles overlapping them to add extra detail.
Re: My map compression scheme.
by on (#100846)
CareerOfEvil wrote:
I noticed you never called FF for byte 0. Does that mean this is not necessary, or that it wasn't done unpacking yet?

Ah, you are right. I forgot to end the buffer in my example. There should be an 0xFF at the end.

Dwedit wrote:
How about boxes with 'patterns' in them? You can specify a box, then include 1 bit for each tile in the box, indicating whether it gets drawn or not.

That's interesting approach, but you still need to point the box coordinates, next byte would be a ID number for box. and then, third byte is required for bits. Not to mention that you can have only 8 Metatiles in a box, unless you use fourth byte, so you can specify next 4 metatiles....
In this example I could, but actually never did, use the vocabulary bit in Control Byte for bottom middle Metatiles.
The entry in vocabulary would be:
.db $05 ;Lenght of this vocabulary entry
.db $01,$01,$01,$02,$02,$02 ;the contents of this vocabulary entry.

Combined with Size byte, I need not to set 0x02 Metatiles twice....
But still, it's uneffective in this case-it'll use the same number of bytes as without using dictonary.

Sik wrote:
In many cases it uses a bunch of large metatiles for the overall shape then uses smaller metatiles overlapping them to add extra detail.

I see, I might make use of this technique, if I'll ever learn to make good art ;)
Re: My map compression scheme.
by on (#100847)
Sik wrote:
[Ecco the Dolphin] uses a bunch of large metatiles for the overall shape then uses smaller metatiles overlapping them to add extra detail.

SMW does the same thing to put berries on bushes and the like.
Re: My map compression scheme.
by on (#100908)
It just hit me.
Coordinate byte never will be 0xF0-0xFF so...I'll get rid of Control byte and reconfigure Coordinate byte to support control byte's functions.
This is so simple that I'm surprised why I have'nt thought about it earlier.Here's my new opcodes:

0xF0:Change Metatile ID number.Next byte after this is MT ID.
0xF1:Use vocabulary. Next byte after this is Number of vocabulary entry.
0xF2:Repeat next size 2 times. Next byte is Size byte, then two coordinate bytes that uses the same size byte.
0xF3-0xFA: Same as 0xF2 but one more repetition cycle with every next opecode number.(eg.0xF5 is 5 repetition number, 0xF8 is 8)
0xFB:Custom number of repetition. Next byte after this is number of the repetitions.
0xFC-0xFE: unused.
0xFF: End of buffer.

And this is it. It will not decrease map's size very much:
Quote:
Coordinate byte: 0xA0. Size byte: 0x3F. ;Place a 4x16 square made of MetaTile 0

Coordinate byte: 0xF0. Data byte: 0x01 ;Change MetaTile ID

Coordinate byte: 0xA2. Size byte: 0x38 ;Place a 4x9 square made of MetaTile 1

Coordinate byte: 0xF0. Data Byte: 0x02;Change MetaTile ID

Coordinate byte: 0xF2 ;Set repetition number to 2

Size Byte: 0x32. Coordinate Byte: 0xA5. Coordinate byte: 0xAB. ;Set two squares.

Coordinate byte: 0xF0. Data Byte: 0x12 ;Change MetaTile ID
Coordinate byte: 0x91. Size byte: 0x00 ;Place doors

Coordinate byte: 0xF0. Data Byte: 0x06 ;Change MetaTile ID
Coordinate byte: 0x9E. Size Byte: 0x00 ;Place The Key.

Coordinate byte: 0xFF ;End of Map.

But will dispose of limits. (previous scheme had limit in control bytes, like only 1F vocabulary entries.)
There's 3 opecodes (FC, FD, FE) free. Anyone have an idea how can I use it effectively?