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

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

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.