This is a rather perplexing dilemma that I've had while developing a tile-based RTS (Real Time Strategy) game. But, first off, all I'm really interested in here is theory and possible code snippets, I don't need (or want) a complete engine or anything like that.
In the game I need to be able to store the objects that are scattered about the game world (trees, rocks, buildings, units, etc.). At first glance, this is a simple problem: just create a linked list of objects in the world, when a new object is created, simply add it to the end of the list. This has one huge problem though: drawing efficiency. Somehow drawing must occur from upper-left to lower-right to avoid overlap. So, what I have implemented right now is a sorted linked list (sorted by Y, X). Then, I have an array that is the size of the map (in a 192x192 map, the array is declared as: Object_List object_list;). The basic design of the Object_List structure is:
A simple linked list. Now, the complicated part; if you look at that structure and the array, it looks like you get hundreds of little linked lists. However, the way I have it implemented, each of those small lists are connected to each other. So, object_array.next points to object_array and so forth. The reason for splitting up the list like this is that I needed to allow multiple objects per tile on the map, and this seemed to work.
So, here is where I need help. This system falls apart as soon as you add height. I could declare Object_Array object_array[h][x][y]; -- but then you have a whole slew of wasted memory. Because there is only one height for each tile, that array would waste (h-1)*x*y*sizeof(Object_Array) bytes of memory -- which is completely unacceptable.
So, are there any ideas on better, more efficient implementations that will work with height but still be able to be drawn on the screen properly?
I appreciate the help,