The method for storing a tile map that I've most often seen written about is to create a 3 dimensional array or linked list of tiles, with the X, Y and Z indices of each tile serving to place it on the X, Y and Z axes. When the rendering function is called, each tile is drawn starting with the top left of the screen at the bottom layer, going through to the bottom right of the screen at the top layer, with every tile being in between being drawn (or possibly skipped, if it the programmer tests for blank tiles.) There are a couple problems with this setup, however. The first is storage: it seems wasteful to me to use memory on a tile that is nothing but a placeholder. The second is time: if the tile is blank, and is drawn, then time is wasted testing each pixel for transparency (the time is less if the images are RLE, of course.) And if the tile is blank and the renderer skips to the next tile, then every tile that is placed or skipped is accompanied by a corresponding test to see if the tile is empty. Those tests don't matter much individually, but with high resolutions or many layers they are likely to slow the render down. Below are a few modifications to the storage scheme and rendering function that I think will help ease these problems.
A linked list (the map) of linked lists (the rows) of tiles (the individual tiles) is created. Each row list contains the index of the list (from 0 through MapHeight-1), and the rows are initially empty. As the map data is read from the disk, new nodes are added to whatever row they belong to. Each node contains its X index (from 0 through MapWidth-1)...but empty tiles are skipped. For instance, take a look at this 3x3x1 map, and the accompanying representation of the linked list that would be built from it (it looks better in proportional font =/ ):
- = blank tile
* = non-blank tile
0 1 2
0 * - *
1 - - -
2 - * -
[Y 0]->[X 0]->[X 2]
[Y 2]->[X 1]
In each node labeled X # the tile image would be stored. When the render loop begins, it would search through the Z0 linked list for the lowest number that is greater than the Y coordinate of the screen (we'll assume the screen is at location 0,0 with a size of 3x3 tiles.) It would come to the Y0 list, and search for the lowest number that is greater than the X coordinate of the screen, which would be X0. It would then walk down the list, drawing each tile as it comes to it, until it reaches the end of the list or the end of the screen (both of which are X2 in this case.) It would then continue with the list Y1 (where it would reach the end of the list as soon as it started, and so would continue to Y2.) Hopefully this explanation has been clear enough for you to see that in this instance there are many less blits required (3) than would be performed if the tiles were stored in an array or solidly filled linked list (9).
Okay, like I've mentioned, I would appreciate any comments, improvements or criticisms of this map storage technique. Here are a few possible problems:
First, calculating the X offset for each tile is less straightforward than in a solid array. The X index would have to be multiplied by the tile width each time a new tile is drawn instead of simply adding the tile width to the X offset. I don't know whether replacing a test to see if the tile should be skipped with a multiplication would save or lose time.
Second, for very dense layers, the map data plus pointers is likely to exceed the memory required for a solid array of map data.
Thanks for your time =)
[This message has been edited by Feyr (edited October 20, 1999).]