What is a good flat file format for storing a 2D tile map that can grow infinitely in any direction?

Question

I am creating a simple map engine that will automatically expand in any direction with procedurally-generated content as needed.

What is a good way to store map data, anchored at a 0,0 origin so that a rectangular subset of map data can be loaded quickly and efficiently from any point on the map?

I have an idea that maybe I should chunkify the map into distinct sectors and then use some sort of header format to identify where in the file a specific sector is stored. Is this a good technique or are there better, more efficient techniques that I can look at?

Answer 1

I would advise against using a single flat file for theoretically infinite amounts of data.

If you have a theoretically infinite amount of data then you need random access, which means multiple files or a database - or an indexed flat-file format, which involves re-solving the indexing problems already solved by file systems or a database.

If you spread your chunks across multiple files, getting the chunk at (-110, 5000) is just a matter of saying "%APPDATA%/game/map/-110/5000.dat" (or some other filename if you want to begin compressing them). Databases just need a query. If a chunk doesn't have any data, you can just not store anything. A single flat file doesn't offer the speed and convenience of random access right off the bat.

In a single file of arbitrary size, for fast random access you must have a guarantee for the position of any chunk of data, which means using an index (since a raw binary search through your data chunks hurts performance, and creating a grid in your file with "blank" spots gives you Byte56's problem). Once you develop an indexing system, give it efficiency and write yourself an API, you've recreated something like the file system or a database. Unless you actually gain something out of doing that it probably isn't worth the investment. For instance, Steam benefits massively from their GCF/NCF file formats.

If you want some security on your saves, it's still possible to do that. For instance, you can encrypt each individual chunk. In order to prevent them getting deleted, you could have a central hash based on existing saved data. If the saved data doesn't match up to the hash (and your program didn't cause the change), a chunk's been deleted.

Answer 2

The solution used most often seems to be to split into lots of files, however your question does imply a single file only. The only sensible option for this (in my opinion) is to emulate a very simple file system inside that single file. It's not actually terriby hard to do, but you really should consider using multiple files if you can.

If you have to stick to one file, then you might find inspiration for your implementation from the ext2 fs. http://en.wikipedia.org/wiki/Ext2 I know it helped me make some good decisions when I had to implement a simple FS for a game.

But really, for any growing map, it's usually better just to use a file for each "accessed" chunk.

Answer 3

I implemented a chunking system for my game when I was fiddling with infinite worlds (not sure if I'll keep them or not). For use with a single file, at first I used the chunk's world position to calculate a byte offset into the file. This assumes a static chunk size, or at least a static maximum. However, if the user were to head off in one direction for a while, this file would become pretty sparse for it's size, since there were large areas of land that hadn't been generated yet so there was blank spaces in the file.

I also tried a two file system. One file holds a map of "chunk position" to "chunk file offset" pairs. The second holds all the chunks. When a new chunk is generated, it simply goes on the end of the chunk file, and it's offset is stored in the position->offset file. This one was an issue when you had a LOT of chunks and finding the offset in the position->offset file took a bit of time. If you find it feasible, you can load the position->offset data into a hash-map on load, to have quick access.

I'm using the second one option for now, but may switch to something else if I find that the performance is lacking. Maybe with this information you'll be able to create something that works for you. Good luck!