Map compression

I will have a somewhat huge map, and I cannot afford to use all of the ram for that.

First I have tried to compress it with the simple RLE method. Because I did't want to store every map "pixels", but only the number of occurrences and the current pixel data itself. So instead of storing 100 land pixels one by one, I try to store 2 data: 100 and 'landpixel'. With this approach I will be able to save the 100 byte data in only 2 bytes.

This is the top of my 160x200 ASCII map:

And  in its encoded form row by row:

We store 3 data for every chunk of land/water/etc: Xcoord in the row, how many iterations, and the character itself.

As the first row says: "0:65#|65:94 ", we must draw 65 pieces of # starting at coord 0, then 94 pieces of space from coord 65.

With this method the 160x200=32 000 pixels data can be reduced to 6471 bytes. (Compressed size: 20.2% of the original)

Of course I should omit the coords value, because it is a constant data stream. But I wanted from the beginning to exclude the water tiles from my compression, because it covers the most of the map. So we will store only the land/reef/city pixels. And any other pixel that aren't stored will be water automatically.

With this method, new compressed data looks like this:

Now the coordinates got meanings, and our rows was shrinked to near half in size.

The total is 3507 bytes now. (10.9% of original size)

Meanwhile I was thinking about more compression. We can use 4 different pixels (land/water/reef/city) so it's possible to store them in 2 bits instead of 1 byte (8bits)... If I maximize the number of consecutive pixels in 64 (6 bits), then I could store the number of pixels and the pixel type in 1 byte. What if there are for eg 110 land pixels in one row? I can store it 2 chunks: 64+46

As I saw, there aren't so much land pixel lines that are longer than 64. So I can reduce the size with another ¬30%, reaching the size of about 7-8% of the original -> ~ 2500 bytes

But at this moment I realized, I overcomplicated this whole approach. Why? I would like to draw a similar map to this:

As we can see, the big tiles are "dithered" with their neighbors. This means during drawing the zoomed map I need to check all of the adjacent pixels from the big map to paint the needed dithered tiles.

But to access any pixel, by default we need to heavily calculate its value from the compressed data. Obviously this take time. And if I need to access another 4 neighbor pixel, it will take 400% more time to draw 1 tile.

I would like to draw a flawlessly scrolling big map, so this method is not feasible. We are low on resources, so every CPU cycle counts.

Let's go back to the good old solution

Tiles and tilemaps. Let's see our map with tiles:

Let's split up this for 40x25 tiles (=1000 pieces). As we can see, most of them are similar.

To be precise, we have 617 clear water tiles, 100 full solid land tiles, and 283 miscellaneous.

With some coding magic, it's possible to check every small tile to search for recurrence. And yes, there are repeating ones, we have exactly 253 different tiles.

As we stated previously, each pixel can be stored as 2 bits, so 1 tile will occupy 2bit*4*8row->8byte. We have 253 of them, so it's 2024 bytes total. We must add our 40x25=1000 byte index tilemap. Finally it's 3024 bytes

9,45% of the original size :)

It seems the old fashioned solutions are still the best, there is no need to reinvent the wheel with fancy compressors :D

Let's see it in action!

The 40x25 tilemap can be directly put to the C64 text mode screenram. Each character represents a tile. In this case the A means a full land tile, and @ is a clean water tile.

Fortunately our generated tile data (8 byte for each tile, with 4 "colors") exactly matches the C64 custom character set format.

All we need to do is to load into memory, and tell the VIC to use this as charset data, and voila:

There are glitches here and there, because now we use only 1 bit / color:

Of course we can switch to multicolor mode and use 2bits/color, to see our final map on screen:

Ok, and why is this better than the first approach?

If I choose any random point on map, I can get it's tile coordinates in the 40x25 matrix with x/4 and y/8. From there I can get the containing character's index. Index*8 will point to the memory address, where the tile's bitmap data lays. Division and multiplication with 2/4/8/etc can be done with bitshifting which is a really fast operation.

And last but not least, I have a displayable fullscreen worldmap :D

P.s: I think the original game used the same solution for storing the map. In retrospect, it clearly seems the most logical storing method.