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.
Amit