I'm all for the header thing, and I wouldn't bore me that much for a map file format.

All the informartion need to be written in that file, so the order/encapsulation does not matter, if you are able to read them back.

Sounds like you actually want two formats: a hierarchical container for disparate objects, and the actual tilemaps. For the former, I suggest... a directory. With files. You can zip it up if you like. The latter, I'd recommend using some extensible text format (easier in most cases) and letting the compression algorithm deal with making it smaller.

I have to say, I like Peter's suggestion of a directory with files in it. I used to be a big fan of compact obfuscated user-defined file formats, these days I prefer text files. Directories are good too if you want hierarchical things. And indeed, if you insist on having it all in one file, you can just zip it up.

It's your format though, so go with what you think works best. One tip: if you give each chunk a header of its own, be sure to include the size of the chunk (mabye the size of the chunk and the size of the header, if the latter can vary) so that if you later decide to add stuff to the format, your older programs can simply skip data they don't need or understand. That's saved me quite a bit of headache on a number of occasions in the past.

The cross-reference table is just a standard indirection table, with all the benefits of referring to things indirectly, i.e. you can adjust them and move them about without having to walk up a tree adjusting at least one and at most every other object that, eventually, refers to it. By relating object ids to actual file positions, it makes quick access easy. Always being a well-defined place makes the cross-reference table easy to find. Being at the end of the file¹ means that PDF creation software doesn't need to keep much of the file at all in memory.

Splitting individual chunks into an ASCII part and a binary part is a pragmatic compromise that gives you one part that's easy to add or remove optional and mandatory fields from and one part that's really compact for more rigidly formed data.

I'll bet you end up needing a mechanism that allows one chunk to refer to arbitrarily many others. I guess the main simplicity you'll gain over PDF-style formatting is that you intend to load the entirety of every map file into memory at once, and then write it all at once. Which means you can make things implicit from positioning, e.g. have a map chunk that says "this map is composed of four layers" and then instead of saying "those layers are described by chunks a, b, c and d" you can just assume it means the next four chunks in the file.

Peter Wang's RISC OS/OS X—type directories are really smart; you could even flag them as bundles in the Mac realm so that they look and act like a single file in the Finder. It'd mean you could devolve all map and image data to common PNG files, for example. Then someone like me could reduce my map file size by throwing all of those through a PNG optimiser. And if a better PNG optimiser comes along, or the PNG file format is improved in the interim, your code needs no adjustment.

By separating your frames and control, you can easily edit individual frames, which may be an advantage. But there is no extensibility. There is no effective difference between storing the tile map (array of tile indexes) in a binary or text format. There won't be extensibility either way. The other parts of your format, though, those can be extensible.

Instead of storing a fixed list of fields (like a C struct), try handling things differently.

The tilemap format takes place in three parts. The first part is a null terminated string that contains an INI file. parse it using Allegro's set_config_data In that section, you can specify metadata fields… Maybe the level title, author, etc. Maybe the initial tile set to use. And you can always add more to it later, because it's extensible.

After that section, put another null terminated string that contains a Lua script. This script is effectively the main() function for that map: it loads and plays the music, fills the scene with objects, etc.

Finally include your binary or text—doesn't matter—blob of tile indexes.

The script should be created by the level editor. When the editor saves a level with an object in it, it actually adds a line to the script that creates the object and places it on the map at the target coordinates.

This is a good start, we've got a good text/binary file that is easy to parse and use because it's built on libraries (Allegro's INI routines and Lua). And, with the level editor, it's easy to create. In fact, you can open it up in a hex editor and edit the INI section or Lua section right there, and it will work, just fine. But we are still being too hard on ourselves. We can make this even easier to deal with.

(The next part of this post moves towards what Peter Wang suggested.)

Instead of having null terminated configuration, script, and tile map sections, let's split it into three files: level.ini, level.lua, and level.map. All of these are text files, and they live in a directory created just for them. The level editor's code is exactly the same, it's just the code to save the levels that's changed. The engine can load those files and use them identically as well.

What advantage does that give? Now we can edit any of the files in our individual editors, and it will have syntax highlighting and whatever other features the editors provide. We should never need to edit the files this way, because the level editor does it for us. Still, when we are debugging, it helps to have our normal repertoire available to use.

What disadvantage does this give us? Well, we've got a bunch of files laying around. It's ugly, and easy for files to accidentally move around, etc.

How do we rectify this? We zip the entire level directory. The zip file contains, in its root, level.ini, level.lua, and level.map. Now we only have one file again. We can rename it to something less obvious than ".zip" if we like. Plus, we still have the ability to use all of our tools to debug. Oh, and use the Allegro Zipfile Reader. You still have the extensibility of the separate files, plus the convenience of a single map file. And, when eveyrthing works properly, you don't even need to remember that the file is really a zip archive with a bunch of other files in it.

There's another layer of extensibility here. Take your level format and convert it into an archive format. The level now becomes level1 in the zip file, and every other entity gets its own directory. Use a VFS system to access them: LoadMap("path/to/archive.dat#level1"), just like Allegro's datafiles, but built on a standard format.

That's why text files are good.
Yes, you can always write something that reads a binary file too, but then you'll always need to have a reference specification. If you ever lose that and need to work on your old data, you're screwed. A text file at least you might be able to decode with a simple text editor.