Tile maps: Storing, Drawing, Saving and Loading by Nathan Smith

This article talks mostly about drawing tile maps but I will talk a little 
about loading and saving too.

Some of the examples are taken from a RPG game I am working on with some 
friends. It uses the allegro library for drawing, but some of this stuff 
should apply to tile maps in general.

Contents:

Level 1: Data Structures
Level 2: Drawing tile maps
2.1 Total redraw
2.2 Hardware scrolling
2.3 Buffered scrolling
2.4 Partial redraw
Level 3: Saving and Loading tile maps
Level 4: Conclusion

---------------------------------------------------------------

Level 1: Data Structures

To store your maps in memory you need a nice data structure. Bad ones will 
be harder to change or expand upon later.

A tile map is basically a bitmap with tiles as its most basic unit instead 
of pixels therefore I like to use a tile map data structure originally 
based loosy on the allegro bitmap data structure, because I hate how most 
tile map article have the width and height of their maps set in stone.

here is a basic single layer map:

struct tile_map
{
    struct tile *data; // an array of tiles sized w*h
    int w,h; // width and height
    int tile_spacing_w,tile_spacing_h; 
    // this is how far apart each tile is drawn. (when we started our
    // game we used 16x16 most of time but later we decided to
    // change over to 32x32, having these variable made it very easy to
    // adjust the maps we had already done.)
};

The tile struct should hold information on how to draw each tile, but what 
you put in the tile struct really depends on the features you want in your 
tile map system.

In our game we have:

struct tile
 {
    BITMAP *pict;     // pointer to the bitmap of the tile
    int flags;             // bit flags controlling special tile effects
    int trans;             // how translucent is this tile
...
 also has some animation information and other drawing stuff
...
 };

However while a map with the above two data structures is okay.. it is not 
very flexible and you will end up with quite boring maps.

so the next step is to have multiple layers. A good tile map is like an 
onion it has layer over layer over layer... this gives the map depth and 
allows you to create better maps.

for example: the bottom layer could hold the basic floor tiles, and next 
walls/cliffs, then have a layer for a pond of translucent water that lets 
you see the rocks and mud bellow it and finally create a layer on top for 
trees and rocks.

How many total layers should a map have? I don't believe there should be a 
set number. Different map require a different number of layers. So here is 
the changed data structure:

struct map
 {
    struct layer *data;
    int total_layers;
 };
 struct layer
  {
    int x,y; // where to start drawing this layer (this should be relative to the map's x and y)
    struct tile *data;
    int w,h; // in our game different layers can have different sizes and different tile spacing.
    int tile_spacing_w,tile_spacing_h;
 };
 struct tile
 {
    BITMAP *pict;
    int flags;
    int trans;
 };

In our game we used classes instead of structs but only difference is our 
drawing code and load/save functions where inside the classes instead of 
outside if we had used structs.

---------------------------------------------------------------

Level 2: Drawing tile maps

Now the main thing that everyone wants when drawing a tile map is to be 
able to scroll it pixel by pixel.
I have seen four different methods of doing this:

2.1 Total redraw - each frame draw the whole map and add a x and y to each 
tile's location then change the x and y to scroll the map.
2.2 Hardware scrolling - draw sections of the map to video memory and use 
hardware to scroll the screen around... redrawing only when the player 
reaches a border..
2.3 Buffered scrolling - draw the map to a buffer larger than the screen as 
the player moves around copy from the buffer to the screen.. redrawing only 
the edges of the buffer.
2.4 Partial redraw - each frame draw the only section of the map the player 
is over.

2.1 Total redraw
This is the easiest to do and understand.. also the slowest (even more so 
if you have animation and other special effects like translucency)

 for(l=0;l< total layers in map; l++)
  for(j=0;j<current layer.h;j++)
   for(i=0;i<current layer.w; i++)
    {
     draw the tile at (scroll_x +layer.x+layer.tile_spacing_w*i), (scroll_y +layer.y+layer.tile_spacing_h*j)
    }

and this will work

One other thing because the map must be redraw each frame you will need to 
use either page flipping or a double buffer system, because dirty 
rectangles just will not work for your game sprites.

2.2 Hardware scrolling
This is most likely the fastest... but I don't like it. Being hardware 
dependent, it works on some machines and not others. It also can't really 
handle tile map animation very well.

in the dos it requires that you that use either Mode X in dos or some 
machines can do it with vesa too but vesa scrolling is not a good as it 
requires you to scroll 4 pixels at a time when scrolling horizontally..

with allegro in dos you can do this:

set_gfx_mode(GFX_MODEX,320,200,640,400); // we request a virtual screen 
twice that of the screen

draw to the screen using VIRTUAL_W and VIRTUAL_H instead of SCREEN_W and 
SCREEN_H for size checking.

then use scroll_screen(x,y); to move around inside the 640x400 area but! 
you will need to redraw when the player try to walk off the edge of the 
640x480 area.

the one nice thing about this method is it works well with dirty rectangles 
for your sprites.

2.3 Buffered scrolling
This is basically a software version of the above method.

If you do use the above method I would suggest you add this one too for 
machines and/or operating systems that don't support Mode X or vesa.

basically if you're screen size is 320x200 then create a bitmap the size of 
640x480
BITMAP *buffer=create_bitmap(640,480);
then draw your map to the buffer

and then instead of scroll_screen(x,y) do this
blit(buffer,screen,x,y,0,0,SCREEN_W,SCREEN_H);

just like in the hardware method you need to redraw if the player walks off 
the edge of the map

this could be done with dirty rectangles if you drew the sprites on the 
buffer then just did one blit to the screen each frame... but I doubt it 
would gain you much speed, as you are already using a buffer.

2.4 Partial redraw

This is my current favorite.
Like method 2.1 you redraw the screen each frame... but you just redraw the 
part of the map that is visible on the screen.

its not that much faster for simple one layer map, but the speed comes when 
you have complex maps with multi-layers and special tile effects that can 
use a lot of the cpu time.

to do this you need three things for each layer:
the x and y of where to draw the first visible tile on the map.
the x and y of the first visible tile in the tile map
the x and y of the last visible tile in the tile map

take the x,y of the first tile (eg the top left corner of the map)

for example -100,-132
invert it:
-(-100)=100
-(-132)=132
divide by the tile_spacing (32 in this example)
100/32=3;
132/32=4;
3,4 is the first visible tile
now go back and find the remainder of the first variables (%)
(-100)% 32 = -4
(-132)% 32 = -4
so -4,-4 is where to draw to the screen
then to get the last tile
take 3,4 and add 
(SCREEN_W-draw_first_tile_here_x)/tile_spacing_w,(SCREEN_H-draw_first_tile_here_y)/tile_spacing_h 
(but you must round up!!!!!!)
(320-(-4))/32+1=11;
(200-(-4))/32+1=7;
the last tile to draw is 11,7

for(j=first_tile_in_map_to_draw_y, j<last_tile_in_map_to_draw_y;j++)
 for(i=first_tile_in_map_to_draw_x,i<last_tile_in_map_to_draw_x;i++)
  {
    draw the tile at i*tile_spacing_w+draw_first_tile_here_x, *tile_spacing_h+draw_first_tile_here_y
  }

We use this method in our game.

to speed up the inner loops of your tile drawing function try and change 
all * to + if you can

for example before loop create a sx and sy variable
sx=first_tile_in_map_to_draw_y*tile_spacing_w+draw_first_tile_here_x;
sy=first_tile_in_map_to_draw_y*tile_spacing_h+draw_first_tile_here_h;

for(j=first_tile_in_map_to_draw_y, j<last_tile_in_map_to_draw_y;j++,sy+=tile_spacing_h)
 for(i=first_tile_in_map_to_draw_x,temp_sx=sx,i<last_tile_in_map_to_draw_x;i++,temp_sx+=tile_spacing_w) 
 {
    draw the tile at temp_sx, sy
 }

there is on more thing about drawing tiles and that is some engines (like 
ours) don't require all the tiles to be of the same size. to handle bigger 
tiles so they overlap nicely (like big trees for example) you need to make 
a small change to the draw function and that is to draw them at 
temp_sx+offset_x, sy+offset_y where offset_x is equal to 
tile_spacing_w-the_tiles_bitmap->w and the offset_y is equal to the 
tile_spacing_w-the_tiles_bitmap->h.

---------------------------------------------------------------

Level 3: Saving and Loading tile maps

there are so many way of doing this that I couldn't even begin to list them..

however I will show you the method we use

we hold all the bitmaps of the tiles for each map in a tileset we store the 
tile set as a datafile. and the problem was each time with changed a 
tileset the whole map had to be rebuild from scratch, but then we came up 
with this method. As we go to save the map, for the bitmap of each tile we 
find the index of it in the datafile we then save grab the datafile 
propriety 'name' for the name of the tile and we save this as a string. 
then if the datafile order get changed it doesn't matter.

As you can imagine this makes map larger than needed on the disk but 
thankfully file compression takes care of that. if anyone using allegro I 
strongly suggest that you use the packfile rountines.

The easiest way of saving a tilemap is to draw it to the file (using method 1)

PACKFILE *f

f=pack_fopen(filename,"p");

first you should write a id string to the top of the file using pack_fwrite 
so you be able to tell if a file is of your type or not.

the next step is to write the number of layer and any other map variables. 
We used pack_iputl for this but you can also use pack_mputl it doesn't 
really matter as long as you stuck to one of them.

then loop through each layer:
{
f=pack_fopen_chunk(f,FALSE);  // this makes sure information from one layer is separate from
                                                   // another

write the w,h and any other layer variables from in the layer here

then loop through each tile in the map (from 0 to w*h)
{
once again use f=pack_fopen_chunk(f,FALSE);
write the name of the tile's bitmap in the datafile in string form 
by first writing the length of the string
with a pack_iputl then the string it self with a pack_fwrite
also write the flags and any other tile variables to the file.
f=pack_fclose_chunk(f);
}
f=pack_close_chunk(f);
}

Reading the map from the disk is as easy as coping the above function and 
changing all the writes to reads and the puts to gets...

There is however there is one small problem, and that is what happens to 
your old maps when you want to make a change to the format?

I would suggest that you save a version number with each map. That way when 
you change the format you can either not load an old version and return 
with an error (better than crashing), or like us you can keep all the old 
versions of your load_map function and call the right one depending on 
which format the map you are loading in.

---------------------------------------------------------------

Level 4: Conclusion

There is no perfect map structure, format, drawing function, loading or 
saving function.

It all depends on the features of your game engine as to what is best to 
use. Here is the thing, the more general and more flexible a tile map 
system is, the slower it will be. There is no other way about it. You can't 
download a tile map engine and expect it to do all the cool stuff at the 
same speed as one you build yourself.

I hope you found this useful, if I missed anything out or messed anything 
up, or if you need some help with tile maps, or even if you want to thank 
me for saving your life by writing this article please email me at 
white_door@yahoo.com