Storing huge 2D tiled map in a txt file

Question

I'm working on a global startegy game that uses a 2D tiled map. The map is to be 8000x8000 tiles large (this size is fixed, the map stays the way it is throughout the game), since I'm covering a large real-world area, but have to do so in detail. I want to store this map in a txt file. To do so I want to use simple IDs for the tiles, but that still leaves me with 2 bytes per tile and a total of about 185 Mb for my txt file, which is far too large. So I went ahead and thought of ways to reduce the size of the file that contains the map. This is what I came up with: Instead of stupidly defining an ID per field, I define regions, lines and specific fields:

region: a rectangle of any size (requires 23 bytes, regardless of its size)

line: a straight line of any length in any simple compass-direction (north, west, east, south) (requires 20 bytes, regardless of its length)

specific field: a specific single field (requires 13 bytes, due to the coordinates that have to be given)

using these three simple "objects" I managed to reduce the size of the file significantly. I may want to add that fields that have already been defined can be overwritten. Take the following rectangle for example:

1 1 1 1 2

1 1 1 1 2

2 2 2 2 2

This could be defined as a 5x3 rectangle of 2s with a 4x2 rectangle of 1s overwriting part of it (total of 46 bytes, as opposed to 195 bytes when defining every field specifically)

The problem I have now is the following: I'm trying to write a map-editor to simplify the process of making such a map. Obviously this editor should automatically generate the map-file, using the previously described objects to reduce the size. The question is, how do I go about writing such an algorithm, meaning one that finds optimal or near-optimal combinations of regions, lines and specific fields, possibly without taking 3 hours to do so? The algorithm that qucikly came to mind was your typical straightforward approach of going through all possible rectangles, picking out those that work best, then going through the undefined fields and defining lines and then specifying the rest specifically, but as you can probably tell, this approach takes a lot of time, so I'd rather avoid it. I had the idea of splitting the large map into smaller parts, but in the process the algorithm loses some of its precision, as this would eliminate rectangles and lines that cross over two or more of these smaller parts.

So, does anyone perhaps have an idea how to optimize the algorithm, or maybe even a better approach? I'd be very grateful for some help here, since I can't quite go on writing the game without the map in place...

I realise this is a lot of text and perhaps an even bigger problem, but anyways

Thanks in advance,

LegionaryCohort

Answer 1

Don't make a text file, make an image file. Now whatever pixel editor you prefer is a working tool for editing the map, and you can compress it as a png in 4, 8 or 24 bit resolution depending on how many distinct tile types you need.

Edit, this will fit poorly in the comment section:
Yes, editing a 8000 x 8000 image is a pain, and I have no doubt that some pixel editors will not be able to handle such images in a satisfactory manner, but there must be some software that can do it. I see that even if the image editor works as it should it will not be easy for a human to handle such an image, but will a custom editor change that? The real question, why would you want such a big map in the first place? I don't recall any tile based game that has used a map that is even close to that size.

You certainly shouldn't use a text file for that much data, even the most rudimentary binary encoding will get you a file format of 1 byte per tile. You could shrink that further by applying a basic compression algorithm, anything your language of choice has library for will do. Png is just a pre-baked format that does these two things for you, but it is not particularly hard to roll something similar of your own doing.

Answer 2

If you feel uneasy utilizing an image (really easy to be done and depending on the format you've got up to 32 bits per pixel/entry), you could still use a text file or your own binary format utilizing RLE (run-length encoding).

What this essentially means is you're storing consecutive fields with the same value as a length with a value. Assuming you're happy with having 128 different IDs, you'd be able to use the most significant bit as an indicator:

• If the MSB isn't set, the value is a single ID.
• If the MSB is set, the value (ignoring the MSB) defines the length of the following ID.
• If the MSB of consecutive bytes is set, their values are added as lengths.

For example:

• 1 occurrence of the value 5: 0000 0101
• 2 occurrences of the value 5: 1000 0010, 0000 0101 (or: 0000 0101, 0000 0101)
• 3 occurrences of the value 5: 1000 0011, 0000 0101
• 5 occurrences of the value 5: 1000 0101, 0000 0101
• 128 occurrences of the value 5: 1111 1111, 1000 0001, 000 0101
• 1 occurrence of the value 5 (shouldn't happen due to being counter productive): 1000 0001, 000 0101

Just to note: The same can be done with larger numbers, e.g. 32 bit integers. It's just easier to explain with shorter bit sequences. Also keep in mind that RLE compression will perform rather bad (i.e. almost no to no savings) if there are lots of different values.

Answer 3

You haven't said what platform / language / libraries you're using, but there is an implementation of the DEFLATE algorithm for just about every language there is. This is the compression algorithm used by PNG, Gzip and many other formats (I've used it many times for large XML files).

I would recommend that you split your huge map into sections, so that you don't have to decompress the entire thing all at once, and compress the sections using deflate.

Most of the time deflate does just as well, if not better, than any custom compression that you can come up with on your own.

(Bear in mind, that the development platform you are using may have a class / method called compress, gzip, zip, zlib or something else rather than just "deflate")

Answer 4

Once I made an image format that was smaller in size. Here's an example file:

255 255 255

0*100 ^100

This would produce a white 100x100 image.I know this is a very simple example and others would take much more but you can use the same technique for your map files and it's very easy to decode it.