In tune with the other active discussion about square tiles vs. iso tiles I''ve encountered a performance issue that I am trying to resolve. If I''m not using iso tiles (even if I am, I suppose), I realized that my map, a simple map[200][200] system, was getting really big. I was thinking it would be better to use a linked list of objects with x,y positions and to draw from that, clipping out those objects not visible. I did some tests and found the calculations required to do the x,y,z world space to x,y screen space every frame were a bit longer than I liked. Not to mention that the list most likely needs to be sorted, or at least a lot of effort would be needed when an object moves around to make sure they are drawn in the right order, and not in front of something they just moved behind. Has anyone experimented with this? I know some of you have - what kind of pitfalls / options / ideas do you all have for this..

We used an array of avl trees of avl trees to hold our object data. The array held the which height level an object was act. The first level of avl trees was sorted by y value and the second level was sorted by x value.
Then we used a descending prune to clip objects. i.e. we knew which levels were going to be drawn, so we could prune other levels, once we knew which level was drawn, we knew which y values were visible, etc.

I tend to find that an array is much more efficient than lists for map data. The reason being, Lists are primarily good for efficiently inserting new data and removing old data in random locations. A map, generally, doesn''t have many objects that are deleted and created dynamically. The addressing speed and ease found with using array-based maps makes them a very good choice. Also, you eliminate a lot of space overhead by using arrays instead of lists or trees. In a doubly linked list of integers of size n, you have to allocate a minimum of 3*2*n bytes of data.

Since, in the usual case, you will only allocate each map array once, and just access it until you delete it, a dynamic ADT is mostly overhead. If your maps are really getting too big, you might want to break them up into smaller chunks, and page each portion of the map in as needed

I see the value in the statement above about map arrays except that I''m working on a simulation, so there may well be sparse areas of the map with really nothing on it. And the user can add and remove objects to the game field often and quickly. Since I have a background thread that works through the map and ''simulates'', I need to have access to all the map data all at once. Could "SiCrane" please expand on what avl trees are, why they are sorted in differnet orders, and what mechanism ''pruning'' was used?

This is sort of what our object storage system used to look like (it''s changed, but I''m no longer in charge, so I have no clue what it''s doing now):

class RowObjectHolder {
AVLTree Objects;
int RowNumber;
}

LevelObjectHolder {
AVLTree Rows;
}

template class ObjectHolder {
LevelObjectHolder level[V];
}

When we add an object we determine it''s level and send it to the proper LevelObjectHolder. The LevelObjectHolder determines which row it sits in and sends it to the correct RowObjectHolder, which is determined by it''s row. The RowObjectHolder determines which column it sits in and adds it to the AVL tree sorted by column.

An AVL tree is a self-balancing form of a binary tree. It''s good for holding an order set of dynamically changing objects. Because it''s just a big binary tree, it''s easy to create an iterator off of it. It works by moving nodes you access a little closer to the top everytime you use them. A good textbook on data structures can probably tell you more.

Given a level, I know which rows in that level will be displayed. Given a row, I know which columns in that row will be displayed. Therefore I can easily remove from drawing non displayed rows and columns.