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