Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
2  
Didn't read the OP ( too tired and gonna go to sleep right after this comment :) ), but you could use binary format instead of plain text. That could help you reduce the size of the file at least a bit. –  Jaakko Lipsanen Dec 26 '12 at 10:21
    
I wouldn't worry about 180MB disc space too much, thats reasonable for a big map. However, I would worry about runtime memory, given that for instance each tile uses 32 byte (only 4 pointer on a 64 bit system), 8000 x 8000 x 32 = 64.000.000 x 32 = 2.048.000.000, it's around 2GB for 32 byte tiles. So how big is a tile gonna be? –  Maik Semder Dec 26 '12 at 10:32
    
@MaikSemder Runtime memory won't be a problem, as I will only load the tiles that are actually visible. The entire map will be stored in an integer array (as IDs) from which I get the information I need, so each tile will only need 2 bytes. –  LegionaryCohort Dec 26 '12 at 10:40
    
Fair enough, so ignore the 180 MB, thats ok, make it even bigger, if it boosts the loading time (assuming it's not mobile nor online content). Focus on making the fun part, except there are other reasons for size limitations that you have in mind. –  Maik Semder Dec 26 '12 at 10:44
    
show 1 more comment

4 Answers

up vote 4 down vote accepted

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.

share|improve this answer
    
I had that idea as well, but editing a 8000x8000 image is a real pain. The map-editor I'm writing will have some functions that makes editing the map a lot easier, so I'll have to write the editor either way. Using a text file makes it simpler for me, that's why I chose it over images. Could using an image file compress the size below 100 Mb? If so, which file-type should I use? –  LegionaryCohort Dec 26 '12 at 11:19
1  
You could just use a PNG image (make sure you pick a lossless format, so JPEG won't work) for storage. The editor could still be visual and WYSIWYG. –  Mario Dec 26 '12 at 12:32
    
The editor will enable editing of larger parts of the map all in one piece, which is why I have to write it myself. As for the reason for which I have such a huge map: The game will be a global strategy game, so I have to cover a large real-world region, but do so in a certain detail, that's why the map is so large. As for binary encoding, I'll have to look into that more, I don't know how much that would save me (I'd still need more than 1 byte per tile, I have more than 256 tile-types). EDIT: added that information to the question –  LegionaryCohort Dec 26 '12 at 14:42
    
Then the obvious step is to use 2 byte tiles, if you apply a compression on top there is no need to try to squeeze it down to less. Alternately, are you sure you couldn't do with 256 or fewer tile types and store some information in another way? How come you have so many in the first place? –  eBusiness Dec 26 '12 at 15:49
1  
You don't have to store these in the file if done right. You could just store something like "land, water, woods or hills?" and then calculate boundaries/edges after loading the map. This way editing should be far easier as well. For example, just draw land and water. Then for every water tile next to land draw edges/coasts as well. –  Mario Dec 26 '12 at 17:02
show 2 more comments

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.

share|improve this answer
    
Basically I'm trying to achieve RLE-compression, but instead of only saving lines I also use the rectangles as explained. That should get me a good compression alltogether, even with a large number of tile-types. In other words: I'm trying to optimize RLE for my case. What I'm actually looking for is either an algorithm that will calculate the whole thing for me or a more efficient way of saving the huge map that I have. –  LegionaryCohort Dec 26 '12 at 14:50
    
So essentially a 2D RLE. How about first ignoring overlappings, looking for all rectangles you can fit in there, then looking for redundancies? –  Mario Dec 26 '12 at 15:32
    
That's pretty much what a friend of mine also suggested, but that takes a lot of time. You'd have to check every possible rectangle (so a total of almost 8000² rectangles), and then do the check for redundancies, then calculate all undefined fields, check for possible lines and store the rest specifically. I was hoping that there is some way to optimize that approach or something, at least make it less taxing... –  LegionaryCohort Dec 26 '12 at 15:38
    
You could split your grid into cells, each compressed on its own. But to be honest: Don't reinvent the wheel. Just using some existing algorithm (e.g. through zlib) or some existing image format (like PNG) might be the most elegant solution. –  Mario Dec 26 '12 at 16:06
add comment

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")

share|improve this answer
    
My question was more or less answered, meaning that I know have a solution for my problem, but thanks for the additional info ;) I'm using java by the way, I just didn't say that in the question because it didn't have any real relevance to my issue... –  LegionaryCohort Dec 27 '12 at 15:41
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.