# Compressing 2D level data

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 >[][]

• Can you provide a bit of detail as far as the way you're currently storing your data? 1D arrays? 2D arrays? Individual objects per tile? Very simple tiles come out to 128x128 * (4 layers) * (4 maps) * (8 bytes per tile) = 2 MB, which should definitely not be a memory hassle on any modern platform; there may be much simpler optimizations to try first. – John Calsbeek Jul 25 '12 at 3:07
• @John what I'm currently using is a 2D array - edited the original post with more info on that. Maybe you (or anyone else) can suggest something better? I would really appreciate. – Lucius Jul 25 '12 at 12:04
• What are you storing in your 2D array? Integers identifying the tile? Tile objects that you've individually new'd? Tile objects that are shared between identical tiles? – John Calsbeek Jul 25 '12 at 14:46
• @John The 2D array stores HashMaps that stores integers that are the ids of tiles. But I've run some tests in the last hour and it seems that even though a 2D array of HashMaps uses less memory than a 3D array of integers at first, once I populate it, the 3D array seems much better. So most likely I was just being dumb, using tons of HashMaps. I'll try to adapt the code to use a 3D array of integers (something like int[columns][rows][layers]) and see if it's any better. – Lucius Jul 25 '12 at 15:47
• If you're really memory-constrained, then don't even use a 3D array. Use a 1D array (or one 1D array per layer), and do the indexing math yourself. (i.e. index = y*WIDTH + x) Java has the quirk that a 2D array is an array of 1D arrays, and has more memory overhead because of that. – John Calsbeek Jul 26 '12 at 4:58

## 3 Answers

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.

• As I said in my reply to John's comment, I changed that Map to a 3D array which pretty much solved my problem. It can still be improved quite a lot, but due to time constraints, I must move forward and try to finish this. In a future project, though, I'll pay more attention to this kind of stuff. Thanks for the answer anyway. – Lucius Sep 26 '12 at 17:38

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.

• I'm doing something like that now, but instead of having the ids in the array, I just make the position point back to a specific tile (which is pretty much the same, I believe). – Lucius Jul 26 '12 at 18:05

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.

• First of all, thanks for your answer. Unfortunately, due to time constraints, I can't spend more time on this - luckily, as I said in my reply to John, I managed to make it less memory consuming by simply using a 3D array and not creating hundreds of identical objects. That being said, the idea of only keeping one map loaded in memory - as simple as it may be - is actually quite good, though it would require some loading screens when going to another map, but that isn't that bad. I'll see about using that, and in a future project I'll be sure to remember all the tips you gave me here. – Lucius Sep 26 '12 at 17:53
• Well, the point of this site is not just to help you with your specific problem, but to help others with similar problems in the future, so it's not all a waste.. =) – Jari Komppa Sep 26 '12 at 18:25