Someone asked me about storing variable-sized tiles in a file. The problem is that if you are keeping only part of your map in memory, you have to be able to easily figure out where in the file the tiles you want are. Tiles can be a variable size if you have a linked list of objects on them, instead of limiting a tile to have only one object.
Here is (most of) my reply:
This is a good question. I have not written a tile map game before but I have often thought about how I would do it, and I had decided the best thing would be to organize tiles into NxN “blocks” and then keep a linked list per block of all the objects in that area.
Storing this format in a file, however, becomes complicated, because the blocks have variable size -- if you have more objects, the block is larger.
What I came up with was that there would be TWO files with map data. (Plus one file with indexing data, which I’ll describe later.) One file would contain the fixed array and one file would contain the linked lists. To load a block of tiles, I can easily figure out where in the fixed-array file to go, and I can load the block from there. THEN that block would contain the location in the other file, of where the linked list goes. The way the linked list file would be stored would be similar to how memory allocation (malloc library) works in C/C++. You’d have to keep track of which parts of the file have data and which do not, and when you want to save your linked list, you would find a place in the file that has enough space for the list.
I am not sure if that made sense, so here are some more details:
A block would be a structure:
Block: int object_file_pos; // where in the linked-list file to go int num_objects; // how many to read from that file Tile tiles[64][64]; // all the tiles in this block
The first file (TILE) would be a file of Blocks.
The second file (OBJ) would be a file of Objects that go in linked lists.
The third file (INDEX) would keep track of what’s in the second file. (It’s a bit vector of all empty areas in the OBJ file.)
LOADING:
To load a block, you’d first load the appropriate block from the TILE file. Since all the blocks are the same size, you can figure out where to read.
Now we have a block, which tells us where in the OBJ file to read. We can read num_objects objects from the OBJ file.
SAVING:
To save a block is easy because we know where it goes in the TILE file, but we don’t want to save it yet because object_file_pos and num_objects are going to change.
However, saving the objects may be harder. First we “deallocate” the objects from the OBJ file. Let’s say for example that the bit vector telling us what areas are free looks like this:
1 2 0 0 0 <- position in OBJ file - - - 111010011110000001110 <- 1 means there's something there
If object_file_pos is 7 and num_objects is 4, then to “deallocate” the objects, we set those bits to 0:
1 2 0 0 0 - - - 111010000000000001110 ~~~~
Now we need to “allocate” a space in the OBJ file for the new objects. First we count how many things are in the linked list and put that into num_objects. Then we look in the bit vector to find a place where num_objects objects can fit. For example, let’s say that there are now 6 objects. We have to find a place where there are six 0’s in a row. The first place this happens is at position 5, so let’s “allocate” 6 objects at position 5 by changing those 0’s into 1’s:
1 2 0 5 0 0 - - - - 111011111110000001110 ~~~~~~
Now we can go through the list and save the objects at positions 5, 6, 7, 8, 9, 10 in the OBJ file. When the player saves or quits the game, you can save the bit vector into the INDEX file.
An alternative would be to store objects anywhere there’s space in the OBJ file, without putting them all close to each other. Then you’d be able to fill the ‘0’ at position 3, for example. This approach lets you save space (because the file doesn’t become fragmented) but loading tiles will be slower because the objects won’t be together.