Forums

These days I felt the community really needed a new tilemap compressed format, a compressor and a z80 decompression routine ;)

So I worked on achieving this, starting from some cornerstones:
- the decompression to VRAM should use sequential writes (instead of interleaved ones as other decompressors).
- the format should exploit also the runs of sequential tiles (tiles numbered in sequential order) to achieve better compression.
- the format could eventually exploit the 3 unused msb bits in each 16-bit tilemap entry.
- the z80 decompression routine should use very little RAM.

what I achieved, and that I'm testing now, seems to work quite well.

The 1408 bytes (uncompressed) tilemaps I'm using as test samples got compressed to 539 and 589 bytes by Phantasy Star RLE and they got compressed to 510 and 335 bytes by the STM compressor, so I'm surely beating that.
The z80 decompression routine uses zero bytes of RAM. It doesn't even use the stack.

My plans now, when I'll be confident enough that both the compression routine and the z80 decompression one aren't hiding bugs, are to work on making the compressor available as a Bmp2Tile plugin... it shouldn't be very hard, hopefully. I might ask some help, eventually.

Full details of the format follow. Everything is stored as bytes.

1st byte -- other bytes (eventually)
%nnnnnn01 -- dd : marks a run of n+2 (2 to 65) same word value HHdd (a.k.a. "normal" RLE)
%nnnnnn11 -- dd : run of n+2 (2 to 65) successive word values (HHdd, HHdd+1, HHdd+2 ...) [will eventually change HH too!]
%nnnnnn00 -- dd kk pp ... : run of n (1 to 63) words using each of the following bytes (HHdd, HHkk, HHpp...)
(n=0 means end of compressed data)
%hhhhht10 : set new HH to %000hhhhh
t = 1 : set the value temporarily (revert to previous value after next run)
t = 0 : set it permanently

(HH is initialized to $00 at launch, both on compressor and on decompressor)

Please feel free to comment on all this.
Thanks!

I'm testing the Bmp2Tile plugin (wow, I thought that it would be harder to make a DLL...) with good results.
What I don't get is why when I select my plugin in the "save as" list, it doesn't change the extension of the filename it's going to create. It does that with all the other plugins I have, except mine. Strangely, BTW, it refreshes the window content showing only those files having that very same .stmcompr extension.
Could that be a bug in my code? I believe it's hard I put a bug in these simple lines:

__declspec(dllexport) const char* getName() {
return "Sverx's TileMap";
}

__declspec(dllexport) const char* getExt() {
return "stmcompr";
}

Unfortunately i can't help you. But i bet that your work will take good results for the future.

This is very interesting! I hope you're able to share the code. One request I have to make is the ability to 'skip' tiles, so that you can layer tilemaps on top of each other. Sonic 1 does this to place the island picture over differing backgrounds.

I was already preparing the repository, it's here: https://github.com/sverx/STMcomp (beware: it's very beta, there might be many bugs I still didn't find)

@Kroc:no, it can't skip anything. It's basically just a substitute for Phantasy Star RLE compression, hopefully with better compression ratio and faster decompression speed.

You could make the decompressor skip index zero for the same effect.

The extension changing code may be troubled by the ' in the name, maybe? It's a bit rubbish to be honest.

How does it compare to the Sylvan Tale compressor?

Maxim wrote

The extension changing code may be troubled by the ' in the name, maybe?

Yes, it's that. If I double that, it works (but it shows it twice in the name...).
I'm putting a different char there, now.
If you happen to fix that, please fix also that "(tiles)" written where "(tilemap)" is expected... that's the 2nd worst bug of that great tool.

I made (yet?) no comparison with Sylvan Tale compressor. I bet LZ will always win.

Well, there's CPU cycles, memory usage and code size to compare as well as compressed bytes.

Compressed size: 352 and 835 bytes. So Sylvan Tale compressor wins with my first test image, lose with my second test image.
Code size: mine it's a little bigger.
As for RAM usage, both decompressors uses none.
Sylvan Tale anyway has to read from VRAM, mine doesn't need that, writes are always sequential.

I've fixed the extension changing thing (https://github.com/maxim-zhao/bmp2tile/issues/3) and I couldn't make it say "tiles" when saving a tilemap. No binaries though :)

Good! :) Now if I only knew how to compile that...
If you've got few minutes left, can you also fix the most annoying bug?

Quote

Saving a tilemap with "in front of sprites" checked in bin format it actually saves it ignoring that, but it works when saving [the tilemap] as a inc

File a bug for it :) The program is slightly crazy (due to history) and needs some work to get into a decent state.

The only problem I have with the name of this compressor is that STM has been historically used for Scream Tracker Module files in its 2.0 version (version 3.0 used S3M instead), which might lead to confusion. Other than that, this is definitely promising, carry on :)

Tom wrote

The only problem I have with the name of this compressor is that STM has been historically used for Scream Tracker Module files in its 2.0 version (version 3.0 used S3M instead), which might lead to confusion. Other than that, this is definitely promising, carry on :)

When I first saw it, I thought it must have something to do with STMicro until I read the description.
Anyway, this does seem pretty useful! Multiple RLE compression methods can be useful. (Depending on how large a game is and how different of a compression ratio you end up with, having multiple routines in a single game could even be beneficial.)

Tom wrote

The only problem I have with the name of this compressor is that STM has been historically used for Scream Tracker Module

I thought just the same. Also, "Sverx's TileMap" is a very silly name.
So I'm open to good suggestions.

How about...
Sverx's Efficient TileMap Compression (SETMcompr)
Sverx's Run Length Compression (SRLC)
Sega Homebrew Run Length Compression (SHRLC)
Etc.

The hardest problem in computer science is naming things :)

Extension name doesn't matter much, it's not like people are going to share and releases lots of files outside of their own codetree (people will probably even just use .bin) - I kinda like stm that said.

BMP2Tile expects unique extensions per format, just so it can determine the compressor from the filename in commandline mode. I'd say Sverx's TileMap is a very sensible name and the extension it uses is fine given that. The "compr" suffix is a bit unnecessary, I mostly use that with a severely abbreviated game name because the game name refers to more than just the compression (and .ps was taken).

Also, you missed a chance to make the old joke about the number of hard problems in computer science...

“There are only two hard problems in Computer Science: cache invalidation, naming things, and off-by-one errors.”

I don't know if there's a different name for an RLE that uses a constant delta (but not zero) between values that need to be encoded.
After all, I'm just compressing runs of values with delta zero or one and RLE itself is just the same with delta equal to zero only...
Delta RLE? Google doesn't help here.

I've referred to them as incrementing runs when I've come across this, and thus RLE seems to be appropriate.

ishiyakazuo wrote

Anyway, this does seem pretty useful! Multiple RLE compression methods can be useful. (Depending on how large a game is and how different of a compression ratio you end up with, having multiple routines in a single game could even be beneficial.)

STMcompr should beat PScompr easily, as both are based on RLE but the latter can't compress incrementing indexes. As for LZ compression (as in Sylvan Tale) this will win if the uncompressed tilemap has a good deal of self-similarity.
I would say if the image uses lots of different tiles STM could win again, as Bmp2Tile assigns a new index for every new tile it creates while converting, thus decreasing self-similarity occurrences.

sverx wrote

ishiyakazuo wrote

Anyway, this does seem pretty useful! Multiple RLE compression methods can be useful. (Depending on how large a game is and how different of a compression ratio you end up with, having multiple routines in a single game could even be beneficial.)

STMcompr should beat PScompr easily, as both are based on RLE but the latter can't compress incrementing indexes. As for LZ compression (as in Sylvan Tale) this will win if the uncompressed tilemap has a good deal of self-similarity.
I would say if the image uses lots of different tiles STM could win again, as Bmp2Tile assigns a new index for every new tile it creates while converting, thus decreasing self-similarity occurrences.

Oops, just realized that I misspoke(mistyped?) when I said multiple RLE compression methods... meant to just say multiple compression methods ;)
Yes, there's not a lot of point in a number of RLE methods, unless they are tuned heavily toward a particular usage which is used often enough to make it worthwhile.

BMP2Tile tends to produce tilemaps with incrementing tile numbers in memory order, as you might expect. My feeling is that the need to decompress large chunks to VRAM is quite small, metatiles are likely to get in the way for actual gameplay. Only static backdrops benefit - in Phantasy Star, monster fighting and menu scenes have the whole scene in a block, but the overworld and dungeon screens are different.

Micro Machines compresses large amounts of data with a mixture of RLE, RLE for incrementing runs, LZ and LZ for reversed matches (with only lookback), with various ways to store different run /match lengths to save bytes, but its decompressor is quite large, and LZ is a speed killer for VRAM.

Please excuse the curtness of this as I'm using a dumbphone numpad. Why is LZ decompression slow? Could we not compile a large dictionary offline and store it in the ROM to reduce the RAM needed and hopefully the readbacks too. If feasible, it would be a trade-off of 1 KB for the dictionary (for example) over the gains made through a shared dictionary for all graphics across the ROM

Maxim wrote

Only static backdrops benefit

They surely will. Something like Twee2SAM images probably would also (hint, hint...;) )

Kroc wrote

Why is LZ decompression slow?

It becomes slow when it needs to read back from VRAM.

You can use LZ variants that only refer to the source data, but the compression tends to be worse. Using a shared dictionary across blocks can help if they have similarity, but otherwise it expands the size of the references.

Might explain why I haven't seen LZ often in 8bit games.
It wasn't until 16-bit they started putting enough RAM in consoles that the standard buffer size of 4KB was easily usable.

Although I think I saw a PCE (8K RAM) HuCard game use it. As I recall it used a 256-byte window size. Though I think that was a game that also stored its compressed data as a bit stream (not even byte-aligning the bits).
I suppose one could look at the compressed data and try to determine the "optimal" buffer size.

Some games do use an intermediate RAM buffer before copying to VRAM, plenty use 4KB for the level data so you can use it as a temporary buffer before that. You'd really like to have 16KB to play with though, to get the best compression.

Micro Machines decompresses tile data to RAM first, Phantasy Star decompresses tilemaps to RAM.

A fullscreen tilemap is only 1.5KB, not too hard to find the room for.

Maxim wrote

Micro Machines decompresses tile data to RAM first, Phantasy Star decompresses tilemaps to RAM.

A fullscreen tilemap is only 1.5KB, not too hard to find the room for.

STM format is meant mainly as a Phantasy Star replacement, faster in decompression and at least as much efficent in terms of compressed size. In 1.5KB you easily will fit 3 to 4 maps.

On a side note, it would be interesting to see someone re-compress Phantasy Star using STM and see how much space it ends up having.

I meant you can find 1.5KB of RAM fairly easily and then use a strong compressor with LZ to decompress into it.

I'm not finding fault in this idea - and it's good to have a tailored compressor, much as I like how PS Gaiden tile compression is tailored to the data - but I'm not sure tilemap decompression speed is a great concern, in Phantasy Star it's waiting for loads of time during palette fades so the time to load the graphics is almost negligible. Under other circumstances, I can see the importance in prompt loading, though - how many cycles does it take to decompress in your tests?

Maxim wrote

how many cycles does it take to decompress in your tests?

My two test images (256x176 pixels) got decompressed in 50298 and 46249 cycles. As expected the most compressed one takes less time to decompress (runs are a simple sequence of OUT, OUT, DJNZ...)

sverx wrote

The 1408 bytes (uncompressed) tilemaps I'm using as test samples got compressed to 539 and 589 bytes by Phantasy Star RLE and they got compressed to 510 and 335 bytes by the STM compressor, so I'm surely beating that.
The z80 decompression routine uses zero bytes of RAM. It doesn't even use the stack.

1408 bytes? is the compression method designed for single screen tilemaps?

psidum wrote

is the compression method designed for single screen tilemaps?

No, any size tilemap works. But it's meant to decompress the whole of it, not just a part of it, and the decompressor as it is now can't decompress data in a given area only, but of course you're free to modify that if you need it :)

Ahh cool, was curious. I hit my head against this issue for a while with my project.

The issue I found was not so much how to pack the data but rather how to get it out in a meaningful and efficient manner. For 8 way scrolling you need access to both row and column data.

I can think of a million ways to pack data but getting it out is completely different. For testing of things i went with the standard [tile]*[tilesubset]*[tilemap]. [tilesubset] was 4*4 but it could be any size, powers of 2 work best since you can use shifts for division to easily locate things.

I am not entirely happy with it tbh, the data can be compressed further for further gains but that means i have to decompress the whole tile map and store it somewhere in ram which I would rather be using for other things not to mention processing requirements between loads.

Would be nice to have a nice compressed format which is small on the rom yet can be accessed in a meaningful way for scrolling without needing decompression as a whole. My mind keeps going to a tree or hash table structure but again i have not worked a way to get data out in an efficient way.

There is not a lot of information on the net on efficient storage of tilemaps for these old systems at least that I could find. It is an interesting problem. Looking forward to seeing someone tackle it.

Yeah, it would be nice to have a compressed tilemap format and a decompressor routine that can decompress just the part of it that you need (say a column or a row for instance) so that to easily handle scrolling on a huge map.
Unfortunately such a format probably needs indexes to access the specific data, or you'll have to run thru the whole compressed data to extract only those bytes you need. It's not impossible, but it's probably overkilling.

It would be. A traditional compression method is obviously out of the question. Will possibly just switch the [tilesubset] to 8*8. At some point i will sit and think about the problem purely from the accessing side. Currently fighting other wars.

Bumping Old thread, but I was not sure which was the best topic for my question regarding stmcompr.

I've been trying to use stmcompr lately, and it doesn't work at all, filling the nametable with random values. I know the format changed a bit lately, but I'm using latest plugin from https://github.com/sverx/STMcomp/tree/master/compressor%20plugin and latest version of SMSLib. I tried to start a brand new test just to try that, and it was still failing.

Can anyone (sverx?) do a quick test and confirm it's working?(then it should be something in my setup)

I'm using that each day so I'm pretty confident it's working.
BTW check the files you're generating with an hex editor, the first byte should be the image width in tiles. If it isn't so, you're probably using the previous 'headerless' format/plugin. (also, in the file save dialog you should read "ShrunkTileMap (compressed)")

Bmp2Tile is certainly giving "ShrunkTileMap (compressed)" as the type of the tilemap file, but it's storing a fullscreen tilemap as a 24x32 tilemap, when it should be a 32x24 one, shouldn't it? I can confirm the first byte is 0x18 in the file.

PD: I just confirmed with a mate in elotrolado that stm is also not working for him.

oh, it's swapping rows and columns... it was a bug in BMP2Tile, see -> https://github.com/maxim-zhao/bmp2tile/commit/be96c94d27cd02ed01d8125bee9e641deb...

Please use version 0.43

ouch!, that sounds like the reason, I'll try this afternoon!

edit: It was that, it has been solved now!

Author	Message
sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	STMcompr: a new compression for tilemaps Posted: Tue Dec 30, 2014 4:33 pm
	These days I felt the community really needed a new tilemap compressed format, a compressor and a z80 decompression routine ;) So I worked on achieving this, starting from some cornerstones: - the decompression to VRAM should use sequential writes (instead of interleaved ones as other decompressors). - the format should exploit also the runs of sequential tiles (tiles numbered in sequential order) to achieve better compression. - the format could eventually exploit the 3 unused msb bits in each 16-bit tilemap entry. - the z80 decompression routine should use very little RAM. what I achieved, and that I'm testing now, seems to work quite well. The 1408 bytes (uncompressed) tilemaps I'm using as test samples got compressed to 539 and 589 bytes by Phantasy Star RLE and they got compressed to 510 and 335 bytes by the STM compressor, so I'm surely beating that. The z80 decompression routine uses zero bytes of RAM. It doesn't even use the stack. My plans now, when I'll be confident enough that both the compression routine and the z80 decompression one aren't hiding bugs, are to work on making the compressor available as a Bmp2Tile plugin... it shouldn't be very hard, hopefully. I might ask some help, eventually. Full details of the format follow. Everything is stored as bytes. 1st byte -- other bytes (eventually) %nnnnnn01 -- dd : marks a run of n+2 (2 to 65) same word value HHdd (a.k.a. "normal" RLE) %nnnnnn11 -- dd : run of n+2 (2 to 65) successive word values (HHdd, HHdd+1, HHdd+2 ...) [will eventually change HH too!] %nnnnnn00 -- dd kk pp ... : run of n (1 to 63) words using each of the following bytes (HHdd, HHkk, HHpp...) (n=0 means end of compressed data) %hhhhht10 : set new HH to %000hhhhh t = 1 : set the value temporarily (revert to previous value after next run) t = 0 : set it permanently (HH is initialized to $00 at launch, both on compressor and on decompressor) Please feel free to comment on all this. Thanks!

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Wed Dec 31, 2014 10:55 am
	I'm testing the Bmp2Tile plugin (wow, I thought that it would be harder to make a DLL...) with good results. What I don't get is why when I select my plugin in the "save as" list, it doesn't change the extension of the filename it's going to create. It does that with all the other plugins I have, except mine. Strangely, BTW, it refreshes the window content showing only those files having that very same .stmcompr extension. Could that be a bug in my code? I believe it's hard I put a bug in these simple lines: __declspec(dllexport) const char* getName() { return "Sverx's TileMap"; } __declspec(dllexport) const char* getExt() { return "stmcompr"; }

segarule Joined: 23 Jan 2010 Posts: 436	Posted: Wed Dec 31, 2014 11:15 am
segarule Joined: 23 Jan 2010 Posts: 436	Unfortunately i can't help you. But i bet that your work will take good results for the future.

Kroc Joined: 08 Dec 2013 Posts: 200	Posted: Wed Dec 31, 2014 12:38 pm
Kroc Joined: 08 Dec 2013 Posts: 200	This is very interesting! I hope you're able to share the code. One request I have to make is the ability to 'skip' tiles, so that you can layer tilemaps on top of each other. Sonic 1 does this to place the island picture over differing backgrounds.

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Wed Dec 31, 2014 1:12 pm
	I was already preparing the repository, it's here: https://github.com/sverx/STMcomp (beware: it's very beta, there might be many bugs I still didn't find) @Kroc:no, it can't skip anything. It's basically just a substitute for Phantasy Star RLE compression, hopefully with better compression ratio and faster decompression speed.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14740 Location: London	Posted: Wed Dec 31, 2014 1:31 pm
	You could make the decompressor skip index zero for the same effect. The extension changing code may be troubled by the ' in the name, maybe? It's a bit rubbish to be honest. How does it compare to the Sylvan Tale compressor?

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Wed Dec 31, 2014 1:55 pm Last edited by sverx on Wed Dec 31, 2014 2:03 pm; edited 2 times in total
	Maxim wrote The extension changing code may be troubled by the ' in the name, maybe? Yes, it's that. If I double that, it works (but it shows it twice in the name...). I'm putting a different char there, now. If you happen to fix that, please fix also that "(tiles)" written where "(tilemap)" is expected... that's the 2nd worst bug of that great tool. I made (yet?) no comparison with Sylvan Tale compressor. I bet LZ will always win.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14740 Location: London	Posted: Wed Dec 31, 2014 2:00 pm
	Well, there's CPU cycles, memory usage and code size to compare as well as compressed bytes.

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Wed Dec 31, 2014 2:06 pm
	Compressed size: 352 and 835 bytes. So Sylvan Tale compressor wins with my first test image, lose with my second test image. Code size: mine it's a little bigger. As for RAM usage, both decompressors uses none. Sylvan Tale anyway has to read from VRAM, mine doesn't need that, writes are always sequential.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14740 Location: London	Posted: Wed Dec 31, 2014 3:53 pm
	I've fixed the extension changing thing (https://github.com/maxim-zhao/bmp2tile/issues/3) and I couldn't make it say "tiles" when saving a tilemap. No binaries though :)

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Wed Dec 31, 2014 4:11 pm
	Good! :) Now if I only knew how to compile that... If you've got few minutes left, can you also fix the most annoying bug? Quote Saving a tilemap with "in front of sprites" checked in bin format it actually saves it ignoring that, but it works when saving [the tilemap] as a inc

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14740 Location: London	Posted: Wed Dec 31, 2014 4:17 pm
	File a bug for it :) The program is slightly crazy (due to history) and needs some work to get into a decent state.

Tom Joined: 16 May 2002 Posts: 1356 Location: italy	Posted: Wed Dec 31, 2014 5:00 pm
Tom Joined: 16 May 2002 Posts: 1356 Location: italy	The only problem I have with the name of this compressor is that STM has been historically used for Scream Tracker Module files in its 2.0 version (version 3.0 used S3M instead), which might lead to confusion. Other than that, this is definitely promising, carry on :)

ishiyakazuo Joined: 29 Oct 2014 Posts: 89 Location: Chicagoland, USA	Posted: Wed Dec 31, 2014 7:46 pm
	Tom wrote The only problem I have with the name of this compressor is that STM has been historically used for Scream Tracker Module files in its 2.0 version (version 3.0 used S3M instead), which might lead to confusion. Other than that, this is definitely promising, carry on :) When I first saw it, I thought it must have something to do with STMicro until I read the description. Anyway, this does seem pretty useful! Multiple RLE compression methods can be useful. (Depending on how large a game is and how different of a compression ratio you end up with, having multiple routines in a single game could even be beneficial.)

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Wed Dec 31, 2014 8:21 pm
	Tom wrote The only problem I have with the name of this compressor is that STM has been historically used for Scream Tracker Module I thought just the same. Also, "Sverx's TileMap" is a very silly name. So I'm open to good suggestions.

ishiyakazuo Joined: 29 Oct 2014 Posts: 89 Location: Chicagoland, USA	Posted: Wed Dec 31, 2014 9:05 pm
	How about... Sverx's Efficient TileMap Compression (SETMcompr) Sverx's Run Length Compression (SRLC) Sega Homebrew Run Length Compression (SHRLC) Etc.

Bock Site Admin Joined: 08 Jul 2001 Posts: 8649 Location: Paris, France	Posted: Wed Dec 31, 2014 9:11 pm
	The hardest problem in computer science is naming things :) Extension name doesn't matter much, it's not like people are going to share and releases lots of files outside of their own codetree (people will probably even just use .bin) - I kinda like stm that said.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14740 Location: London	Posted: Wed Dec 31, 2014 10:29 pm
	BMP2Tile expects unique extensions per format, just so it can determine the compressor from the filename in commandline mode. I'd say Sverx's TileMap is a very sensible name and the extension it uses is fine given that. The "compr" suffix is a bit unnecessary, I mostly use that with a severely abbreviated game name because the game name refers to more than just the compression (and .ps was taken). Also, you missed a chance to make the old joke about the number of hard problems in computer science...

haroldoop Joined: 25 Feb 2006 Posts: 874 Location: Belo Horizonte, MG, Brazil	Posted: Wed Dec 31, 2014 11:10 pm
	“There are only two hard problems in Computer Science: cache invalidation, naming things, and off-by-one errors.”

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Thu Jan 01, 2015 1:44 pm
	I don't know if there's a different name for an RLE that uses a constant delta (but not zero) between values that need to be encoded. After all, I'm just compressing runs of values with delta zero or one and RLE itself is just the same with delta equal to zero only... Delta RLE? Google doesn't help here.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14740 Location: London	Posted: Thu Jan 01, 2015 4:39 pm
	I've referred to them as incrementing runs when I've come across this, and thus RLE seems to be appropriate.

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Fri Jan 02, 2015 2:27 pm
	ishiyakazuo wrote Anyway, this does seem pretty useful! Multiple RLE compression methods can be useful. (Depending on how large a game is and how different of a compression ratio you end up with, having multiple routines in a single game could even be beneficial.) STMcompr should beat PScompr easily, as both are based on RLE but the latter can't compress incrementing indexes. As for LZ compression (as in Sylvan Tale) this will win if the uncompressed tilemap has a good deal of self-similarity. I would say if the image uses lots of different tiles STM could win again, as Bmp2Tile assigns a new index for every new tile it creates while converting, thus decreasing self-similarity occurrences.

ishiyakazuo Joined: 29 Oct 2014 Posts: 89 Location: Chicagoland, USA	Posted: Fri Jan 02, 2015 3:12 pm
	sverx wrote ishiyakazuo wrote Anyway, this does seem pretty useful! Multiple RLE compression methods can be useful. (Depending on how large a game is and how different of a compression ratio you end up with, having multiple routines in a single game could even be beneficial.) STMcompr should beat PScompr easily, as both are based on RLE but the latter can't compress incrementing indexes. As for LZ compression (as in Sylvan Tale) this will win if the uncompressed tilemap has a good deal of self-similarity. I would say if the image uses lots of different tiles STM could win again, as Bmp2Tile assigns a new index for every new tile it creates while converting, thus decreasing self-similarity occurrences. Oops, just realized that I misspoke(mistyped?) when I said multiple RLE compression methods... meant to just say multiple compression methods ;) Yes, there's not a lot of point in a number of RLE methods, unless they are tuned heavily toward a particular usage which is used often enough to make it worthwhile.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14740 Location: London	Posted: Fri Jan 02, 2015 5:30 pm
	BMP2Tile tends to produce tilemaps with incrementing tile numbers in memory order, as you might expect. My feeling is that the need to decompress large chunks to VRAM is quite small, metatiles are likely to get in the way for actual gameplay. Only static backdrops benefit - in Phantasy Star, monster fighting and menu scenes have the whole scene in a block, but the overworld and dungeon screens are different. Micro Machines compresses large amounts of data with a mixture of RLE, RLE for incrementing runs, LZ and LZ for reversed matches (with only lookback), with various ways to store different run /match lengths to save bytes, but its decompressor is quite large, and LZ is a speed killer for VRAM.

Kroc Joined: 08 Dec 2013 Posts: 200	Posted: Fri Jan 02, 2015 7:43 pm
Kroc Joined: 08 Dec 2013 Posts: 200	Please excuse the curtness of this as I'm using a dumbphone numpad. Why is LZ decompression slow? Could we not compile a large dictionary offline and store it in the ROM to reduce the RAM needed and hopefully the readbacks too. If feasible, it would be a trade-off of 1 KB for the dictionary (for example) over the gains made through a shared dictionary for all graphics across the ROM

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Fri Jan 02, 2015 8:30 pm
	Maxim wrote Only static backdrops benefit They surely will. Something like Twee2SAM images probably would also (hint, hint...;) )

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Fri Jan 02, 2015 8:32 pm
	Kroc wrote Why is LZ decompression slow? It becomes slow when it needs to read back from VRAM.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14740 Location: London	Posted: Sat Jan 03, 2015 4:48 pm
	You can use LZ variants that only refer to the source data, but the compression tends to be worse. Using a shared dictionary across blocks can help if they have similarity, but otherwise it expands the size of the references.

KingMike Joined: 14 Oct 2008 Posts: 510	Posted: Sun Jan 04, 2015 5:41 am
KingMike Joined: 14 Oct 2008 Posts: 510	Might explain why I haven't seen LZ often in 8bit games. It wasn't until 16-bit they started putting enough RAM in consoles that the standard buffer size of 4KB was easily usable. Although I think I saw a PCE (8K RAM) HuCard game use it. As I recall it used a 256-byte window size. Though I think that was a game that also stored its compressed data as a bit stream (not even byte-aligning the bits). I suppose one could look at the compressed data and try to determine the "optimal" buffer size.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14740 Location: London	Posted: Sun Jan 04, 2015 1:55 pm
	Some games do use an intermediate RAM buffer before copying to VRAM, plenty use 4KB for the level data so you can use it as a temporary buffer before that. You'd really like to have 16KB to play with though, to get the best compression. Micro Machines decompresses tile data to RAM first, Phantasy Star decompresses tilemaps to RAM. A fullscreen tilemap is only 1.5KB, not too hard to find the room for.

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Sun Jan 04, 2015 6:27 pm
	Maxim wrote Micro Machines decompresses tile data to RAM first, Phantasy Star decompresses tilemaps to RAM. A fullscreen tilemap is only 1.5KB, not too hard to find the room for. STM format is meant mainly as a Phantasy Star replacement, faster in decompression and at least as much efficent in terms of compressed size. In 1.5KB you easily will fit 3 to 4 maps.

ishiyakazuo Joined: 29 Oct 2014 Posts: 89 Location: Chicagoland, USA	Posted: Sun Jan 04, 2015 10:02 pm
	On a side note, it would be interesting to see someone re-compress Phantasy Star using STM and see how much space it ends up having.

Maxim Site Admin Joined: 19 Oct 1999 Posts: 14740 Location: London	Posted: Sun Jan 04, 2015 11:03 pm
	I meant you can find 1.5KB of RAM fairly easily and then use a strong compressor with LZ to decompress into it. I'm not finding fault in this idea - and it's good to have a tailored compressor, much as I like how PS Gaiden tile compression is tailored to the data - but I'm not sure tilemap decompression speed is a great concern, in Phantasy Star it's waiting for loads of time during palette fades so the time to load the graphics is almost negligible. Under other circumstances, I can see the importance in prompt loading, though - how many cycles does it take to decompress in your tests?

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Mon Jan 05, 2015 8:52 am
	Maxim wrote how many cycles does it take to decompress in your tests? My two test images (256x176 pixels) got decompressed in 50298 and 46249 cycles. As expected the most compressed one takes less time to decompress (runs are a simple sequence of OUT, OUT, DJNZ...)

psidum Joined: 01 Jan 2014 Posts: 331	Posted: Mon Jan 12, 2015 2:10 am
psidum Joined: 01 Jan 2014 Posts: 331	sverx wrote The 1408 bytes (uncompressed) tilemaps I'm using as test samples got compressed to 539 and 589 bytes by Phantasy Star RLE and they got compressed to 510 and 335 bytes by the STM compressor, so I'm surely beating that. The z80 decompression routine uses zero bytes of RAM. It doesn't even use the stack. 1408 bytes? is the compression method designed for single screen tilemaps?

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Mon Jan 12, 2015 8:37 am
	psidum wrote is the compression method designed for single screen tilemaps? No, any size tilemap works. But it's meant to decompress the whole of it, not just a part of it, and the decompressor as it is now can't decompress data in a given area only, but of course you're free to modify that if you need it :)

psidum Joined: 01 Jan 2014 Posts: 331	Posted: Mon Jan 12, 2015 10:31 am
psidum Joined: 01 Jan 2014 Posts: 331	Ahh cool, was curious. I hit my head against this issue for a while with my project. The issue I found was not so much how to pack the data but rather how to get it out in a meaningful and efficient manner. For 8 way scrolling you need access to both row and column data. I can think of a million ways to pack data but getting it out is completely different. For testing of things i went with the standard [tile][tilesubset][tilemap]. [tilesubset] was 4*4 but it could be any size, powers of 2 work best since you can use shifts for division to easily locate things. I am not entirely happy with it tbh, the data can be compressed further for further gains but that means i have to decompress the whole tile map and store it somewhere in ram which I would rather be using for other things not to mention processing requirements between loads. Would be nice to have a nice compressed format which is small on the rom yet can be accessed in a meaningful way for scrolling without needing decompression as a whole. My mind keeps going to a tree or hash table structure but again i have not worked a way to get data out in an efficient way. There is not a lot of information on the net on efficient storage of tilemaps for these old systems at least that I could find. It is an interesting problem. Looking forward to seeing someone tackle it.

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Mon Jan 12, 2015 11:17 am
	Yeah, it would be nice to have a compressed tilemap format and a decompressor routine that can decompress just the part of it that you need (say a column or a row for instance) so that to easily handle scrolling on a huge map. Unfortunately such a format probably needs indexes to access the specific data, or you'll have to run thru the whole compressed data to extract only those bytes you need. It's not impossible, but it's probably overkilling.

psidum Joined: 01 Jan 2014 Posts: 331	Posted: Mon Jan 12, 2015 11:25 am
psidum Joined: 01 Jan 2014 Posts: 331	It would be. A traditional compression method is obviously out of the question. Will possibly just switch the [tilesubset] to 8*8. At some point i will sit and think about the problem purely from the accessing side. Currently fighting other wars.

kusfo Joined: 29 Mar 2012 Posts: 886 Location: Spain	Posted: Tue Jul 03, 2018 7:53 am
kusfo Joined: 29 Mar 2012 Posts: 886 Location: Spain	Bumping Old thread, but I was not sure which was the best topic for my question regarding stmcompr. I've been trying to use stmcompr lately, and it doesn't work at all, filling the nametable with random values. I know the format changed a bit lately, but I'm using latest plugin from https://github.com/sverx/STMcomp/tree/master/compressor%20plugin and latest version of SMSLib. I tried to start a brand new test just to try that, and it was still failing. Can anyone (sverx?) do a quick test and confirm it's working?(then it should be something in my setup)

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Tue Jul 03, 2018 8:28 am
	I'm using that each day so I'm pretty confident it's working. BTW check the files you're generating with an hex editor, the first byte should be the image width in tiles. If it isn't so, you're probably using the previous 'headerless' format/plugin. (also, in the file save dialog you should read "ShrunkTileMap (compressed)")

kusfo Joined: 29 Mar 2012 Posts: 886 Location: Spain	Posted: Tue Jul 03, 2018 9:09 am
kusfo Joined: 29 Mar 2012 Posts: 886 Location: Spain	Bmp2Tile is certainly giving "ShrunkTileMap (compressed)" as the type of the tilemap file, but it's storing a fullscreen tilemap as a 24x32 tilemap, when it should be a 32x24 one, shouldn't it? I can confirm the first byte is 0x18 in the file. PD: I just confirmed with a mate in elotrolado that stm is also not working for him.

sverx Joined: 05 Sep 2013 Posts: 3827 Location: Stockholm, Sweden	Posted: Tue Jul 03, 2018 9:20 am
	oh, it's swapping rows and columns... it was a bug in BMP2Tile, see -> https://github.com/maxim-zhao/bmp2tile/commit/be96c94d27cd02ed01d8125bee9e641deb... Please use version 0.43

kusfo Joined: 29 Mar 2012 Posts: 886 Location: Spain	Posted: Tue Jul 03, 2018 9:29 am
kusfo Joined: 29 Mar 2012 Posts: 886 Location: Spain	ouch!, that sounds like the reason, I'll try this afternoon! edit: It was that, it has been solved now!

Forums

View topic - STMcompr: a new compression for tilemaps