Is it summarizing too much to say that you're using a sparse matrix setup for the map?

It sounds to me that the "base terrain" (or whatever) would still be a simply 2-dimensional array, and then you're using a sparse matrix to hold the rest of the information.

That about right?

------------------
DavidRM
Samu Games

and it sounds very similar to Dino's method.

http://www.xyphus.com/users/dino/technical/mapfile.html

This sounds sort of similiar the method I am trying..

I wanted all my objects to be tile independant so I have decided to try storing them in their xyz coords. They will be in a linked list that is depth sorted.

The ground-plane is made up of rectangles that are blitted left to right top to bottom, no fancy diamond shaped stuff; the artwork takes care of that.

I thought I would do this since it speeds up the drawing of the ground plane, and lets me have more time to zsort the objects.

I then iterate through the object list, clipping out the non-viewable objects, sort the list, and draw from back to front..

and I think this should work!

I don't think this is a too good approach (when you this approach for all Z values) to the problem, because you waste memory when the map doesn't have many blank tiles. For example the ground layer would become very large in linked lists.
This approach, is also a bit slow, because finding a value in a large list is not fast. When you use these lists with larger X, Y values and you search for a region these lists slow you down.
Example :

RECT DisplayRect;

for ( int z = 0; z < maxZ; ++z )
{
ptr = [Z(z)] // search for Z Values -> fast
Search( ptr, DisplayRect.top, SearchResultY )
for ( y = SearchResultY; y < DisplayRect.right; .. )
{
Search( y, DisplayRect.left, SearchResultX );
for ( x = SearchResultX; x < DisplayRect.right )
{
// Draw etc.
}
}
}

When now the Width and Heigth of the Map are large, the time critical parts ( Search(..) ) become very slow (using indexing could be a slight relief).
For small maps or maps with many blank fields this technique could become fast and efficent.

I suggest (as an OOP addict) using for each height different Map implementations.
e.g.

class CMapBase
{
virtual void Draw( CRect& area, LPDDSURFACE ) = 0;
// etc.
};

Then
class CGroundMap : pubic CMapBase
{
virtual void Draw( CRect& area, LPDDSURFACE );
private:
matrix m_Map;
};

If you keep this implementation clear, straightforward and easy to (use/edit) you can get very good results.
An implementation for the heighest Z value can be somewhat to reduce calculating costs, by using your method, because only few Tiles will be so high up, so that a matrix would be too large.

Hope made myself clear ?

Aidan

PS : Email CKoschack@T-Online.de if you have suggestions, comments

I use a 2D array for the base map (square tiles, but I figure you know that by now ), but keep everything else in a large array.

For rendering, I create a tree (sorted in screen depth, for back-to-front rendering) of the visible items in the array - no malloc here, I simply create the tree within the array, giving me the best of both worlds (with a certain waste of memory, yes!). When things change, I re-sort the active visible items in the array (and only those).

I was initially worried that this would suck from a performance perspective, but as it turns out, it doesn't. Even with several hundred active items, sorting and recursing is less than 1% of the time spend in rendering.

This approach has at least one major benefit: There are really no firmly defined "layers", each item is free to move in (x,y,z) space as I see fit. Also, memory is directly proportional to "map density".

/Niels

I am too using a method such as that described above (and as T-man said). My method does the following:
You have a base array (2D). Each element in the array is the head node to a linked list. Each linked list is a list of objects (sorted by Z order) over a given 2D point. When an object moves, resorting is done only over that 2D space. (NOTE: An object can be anything from a basic non-interactive tile to an interactive entity).

Now there is another list that needs to be mentioned here. In my design, I had a problem when drawing the images. The method above is great for storing it in memory, but when drawing the objects, it failed big time. Here's the solution I came up with. I have a linked list of objects that would be drawn sorted by their pixel position. These objects are only the currently visible ones. Each node in the linked list points to an element of the map in memory and has a link to the next and previous node in the list. This allows me to quickly move the object up and down the drawing list whenever an object moves.

I will be writing up an article on this method and post it up on my page for the standard critism such as:
"That will never work you stupid stupid man!"
"Go code some business application you loser!"
"You couldn't tell a linked list from an array!"
and so forth

I'll let you know when it's up.

------------------
Dino M. Gambone
http://www.xyphus.com/users/dino

Good judgement is gained through experience. Experience, however, is gained through bad judgement.

Hiya all. I was just brainstorming for ideas on how to store and render the map for a tile-based engine. I've read a few docs and written parts of two or three engines myself. Anyway, the point is this. I've come up with an approach that I've never seen done before, and that appears to be an improvement over some techniques I've read about. I'd like to get the opinion of this group of programmers on this implementation, any problems or improvements that you guys can point out and, if possible, material that discusses this particular technique (which I haven't found so far.)

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 - * -

[Z 0]
|
[Y 0]->[X 0]->[X 2]
|
[Y 1]
|
[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 =)

--Feyr

[This message has been edited by Feyr (edited October 20, 1999).]

I finally finished writting the article on the method described above. Here's the link to the site:
http://www.xyphus.com/users/dino/technical.html

Happy reading!

------------------
Dino M. Gambone
http://www.xyphus.com/users/dino

Good judgement is gained through experience. Experience, however, is gained through bad judgement.