| « Long time no see... | C++: The Fastest foreach loop? (Hacking references again) » |
Few days ago, I got an idea for tile image compression for 2D isometric games like Arcanum, whose tiles are all in same shape, so today, I thought that it would be nice to try to implement it, and compare it with current compression algorithm, the RLE.
For those who don't know anything about Arcanum's file formats, in the Arcanum, all tiles has same dimension, 78x40 pixels, and it's colors are reduced to 256 color palette, then resulting indices are compressed by RLE compression, and saved with palette into Art file.
The idea about the new tile compression is very simple: save only what's visible, which means that the compression algorithm will remove all transparent pixels (mask) from left and right side of the rows in the image, and then save trimmed rows to output (raw) stream.
Anyway, I did implemeted it today, and I can say that the compression/decompression is very simple and fast, since the algorithm consist only of two single for loops and one memcopy call for every row, so it's even faster than RLE compression. Also the algorithm has fixed compression, so the compression ratio is constant, and it's not required to save any meta information for decompression, thus some space gets saved.
So I tried to compress and then decompress one tile (more precisely, it's indices) 100 000 times. And speed?
Tile compression:
Compression: 274 ms
Decompression: 433 260 ms
Compared to RLE:
Compression: 4 041 ms
Decompression: 2 447 ms
Oh yeah, in this case, the compression is almost 15 times faster than RLE compression, and more importantly, decompression is also faster, more than 5 almost 10 times faster.
The reason why decompression is slower than compression is that, it's required to fill output buffer with zeros (i.e. transparent pixels) before actual decompression, plus I'm using own memory fill function that is optimized for larger blocks (SSE2), thus making decopression slower. (Optimized!)
About compression ratio, one tile image has 3 120 (78*40) pixels, where 1 596 pixels are always transparent, so compressed files has 1 524 (3 120 - 1 596) pixels, thus the ratio is 0.488 (~1:2).
If you multiply those numbers by size of one pixel (in bytes), for example 3 for 24bit images, then you get almost 5KiB (4 788B) saved per tile. Now multiply that by 100 000...
What about RLE? well, it don't have fixed compression ratio, so it's hard/impossible to culculate/guess those numbers, but in the Arcanum, terrain is very varied and colorful, and most of the colors in palettes are used, so the RLE won't be as much effective as my tile compression.
Anyway, with such fast tile decompression, it's possible to decompress the tile on fly, when requested, no need to keep them decompressed in RAM anymore.
Pixel get/set functions can also work on compressed tiles very fastly using precalculated lookup table (for row offsets).
Also, all the tiles can be stored into one big tileset bank, and compressed with deflate or huffman compression, so we get even more space saved, and loading will be also faster.
The whole bank can be now loaded into memory for superfast access!
...
8 comments
Hi, crypton. May I kindly ask you to do something for the fans craving for OpenArcanum? :)This would be awesome getting to know some news through your facebook page: https://www.facebook.com/ArcanumAlive
And some links to your FAQ and toodledo page might also be of some use for such fans as I am. =)
And the most important, I think you might put your paypal account somewhere, where people can know about it, so that we get to pay you some money and you be motivated.
By the way, is that really true that radzh does another open Arcanum engine (Arc.: Revol.)? Why not joining your efforts?
Thank you very much!
Hi soshial,I'll be posting any news through the facebook page, however I'm not going to post there any implementation specific or technical details, since most of the fans there aren't game devs at all, I guess.
Anyway, I'm planning to post on facebook page a big update after I finish the implementation of new GUI system, probably with some screenshots and video, to preview the work that I have done so far, since the last update.
About the links, thanks for letting me know, I'll add them somewhere visible. Also thanks for any futher donations, they will be very helpful!
And yes, Radzh is working on new engine for Arcanum as well, however, his version won't clone all the features of original Arcanum engine, and probably the maps and gameplay style will be completely different too. Our aims and ideas splits in many aspects, we can't cooperate together, so we're working on own projects instead. So there will be more Arcanum clones, but his version will probably be finished sooner, because he has a team and support from community, and I don't have any of that, so I'm working on it alone, but everyday, as much as possible to balance their advantage in number of developers.
Anyway, check A:R's wiki for more details: http://arcanumrevolution.ru/wiki/
There is also more Arcanum related projects: http://arcanum.game-alive.com/forums/viewtopic.php?f=2&t=129
Thanks for your interest!
See you around.
How does that speed compare to saving the image un-isometrically then using a rotation matrix or such to move it?I know a lot of games merge all tiles into single files, what is your opinion on this?
That's a good idea! Especially for generating new tiles, since the original tiles are already rotated and scaled, and converting them back to rectangular shape would probably decrease the image quality.I don't know how the resulting tile would look like, hopefully it won't be blurry/glitchy or slower to render, but I'll definitely try this method, and then I'll post the results here as well.
Thanks for the tip!
Could you explain how RLE data should be decompressed? I'm having (and several people I asked about it) a hard time trying to get to frame data, even with your tutorial on the forum. I'm sorry, but I don't have time to fully explain the decompression algo, however I can suggest you to look at the ArtView's source code, AFAIR, there you can find both comp and decomp algos.Search at Terra Arcanum forums for the download link, hopefully it will be still online, since I don't have it anymore.
Hope it helps :)
Yup, I found it. Thanks. I have a different question now. Where are water tiles stored? Can't find them in art\tile :(What I want to do is auto-generate some biomes on an island. Right now I'm into Bezier curves :-)
Oh, there are art\tile\sw3*.art files. Sorry :-)Good luck on your project! I'm presently writing an Arcanum MMO with auto-generated map full of different biomes and world-building like Haven & Hearth. Hopefully I'll be able to finish it :-)
Comment feed for this post
