Compressing 2D level data

Question

So, I'm developing a 2D, tile based game and a map maker thingy - all in Java.

The problem is that recently I've been having some memory issues when about 4 maps are loaded. Each one of these maps are composed of 128x128 tiles and have 4 layers (for details and stuff).

I already spent a good amount of time searching for solutions and the best thing I found was run-length enconding (RLE). It seems easy enough to use with static data, but is there a way to use it with data that is constantly changing, without a big drop in performance?

In my maps, supposing I'm compressing the columns, I would have 128 rows, each with some amount of data (hopefully less than it would be without RLE). Whenever I change a tile, that whole row would have to be checked and I'm affraid that would slow down too much the production (and I'm in a somewhat tight schedule).

Well, worst case scenario I work on each map individually, and save them using RLE, but it would be really nice if I could avoind that.

EDIT: What I'm currently using to store the data for the tiles is a 2D array of HashMaps that use the layer as key and store the id of the tile in that position - like this: private HashMap< Integer, Integer >[][]

Answer 1

Its unlikely that the map itself is taking too much RAM, even on low-end Java phone targets.

Voxel-based editors are editing RLE models - which is analogous to your use-case - every time the user clicks; we were doing that last century and it wasn't a performance problem then; so no worry now.

One small detail; why use a Map<Integer,Interger> ?

Why not just have an array of columns e.g. Tile[][] map where the first dimension is (y*width)+x? This isn't performance-related particularly, in that map-access should be a fraction of the cost of rendering anything, but using a single-dimension array for a x*y map is fairly standard.

Answer 2

I usually write some kinda of imageCache class which merely holds the tiles graphics. Let's say I have 20 different coloured tiles representing different terrains. My world(s) then are simple 2D dimensional arrays of ints, where each int is just an index back to what colour/type of tile needs to go in that position when I need to draw the map/world.

Answer 3

Depending on your compression target, you have plenty of choices that are always a tradeoff of space vs implementation complexity (and processing time).

I have to make plenty of assumptions here, but the general principles should apply.

The raw data is 128x128x4x4 bytes (1 byte per tile).

128x128x4x4 = 256k

Accessing this goes something like..

tile = map[mappos]

The easiest solution is to tile the tiles. The compression ratio depends on the source data, but let's assume that there are a bunch of identical "pilars" - same configuration of tiles in the z direction. Stuff like actual pilars, railings, etc. Save unique Z slices and then genrate maps that refer to these by index.

Assuming there's only 256 unique "pilars", we get down to:

128x128x4 + 256x4 = 65k

Indexing this data is still pretty trivial. The compression ratio is naturally worse if there are more uniques (as you have to pump up the indexes to 16 bit ints and store more pilars).

tile = pilar[map[flat_mappos]][z]

You could go a level deeper and start storing unique 2x2 pilar sets (adding yet another indirection); let's say there's 256 of these as well. The result is

64x64x4 + 256x2x2 + 256x4 = 18k

Accessing this gets a bit hairy though (still relatively fast)

tile = pilar[quadmap[map[quaded_flat_mappos]][quadpos]][z]

Another way to slice would be to take horizontal or spans, but it's less likely that you end up with a small number of uniques. But if you do, the result is much better even with one iteration:

128x4x4 + 256x128 = 34k

If you need even more compression, you COULD go and use RLE compression, but that will make the data less efficient to access. The compression described above gives you random access.

If you only ever access the data sequentially, RLE is a good match. A trade-off is to only RLE one scanline at a time, but the compression ratio gets worse; you'll have to benchmark and see whether the compression ratio is good enough AND whether you can keep framerate high enough. Again, you can slice your data in various ways, and some are better than others, depending on your exact use case.

Finally, for even further compression, you could use ZLIB or some other general-purpose compressor. You could, for example, only keep the currently active level in memory in an uncompressed form. And here "uncompressed" may still mean any of the methods mentioned above.