I have a big problem with my Game Engine. I designed my Unit engine with Link-List before. Then I shown all units one by one which follow the Unit Link-List. But if there was a unit "A" which in upper location in the map than unit "B", but in the unit Link-List, unit B is in front of unit A. Then something happened following.

(Unit Link-List)
  head-->B-->A--> ... -->tail

(bad case)
-------
| A   |       EX: A,B are buildings or tanks.
|     |---    ==> if I don''t adjust the Unit List-Link, 
-------  |    ==> it will show B first, than show A.
   | B   |
   -------

(It''s should be this)
-------
| A   |
|  -------
---| B   |    
   |     |   
   -------

if I design my engine with AVL-Tree, is it true I can solve this problem and do not make the game speed slow down ?? Thanks a lot. and sorry for my poor english

I don''t know about AVL trees, but generally, what you want to do is depth sorting. You could just give each unit a z value (describing how high it is on the map) and sort the list according to these values before drawing.

Just like

    int compare_units_z(void *unit1, void *unit2) {  return unit1->z - unit2->z;}void Draw(void) {  t_unit **units;  t_unit  *unit;  int      cur_unit;  units = malloc(sizeof(t_unit *) * num_units);  unit = list->top;  cur_unit = 0;  while(unit) {    units[cur_unit] = unit;    cur_unit++;    unit = unit->next;  }  qsort(units, num_units, sizeof(units[0]), compare_units_z);  for(cur_unit = 0; cur_unit < num_units; cur_unit++) {    // Draw Units[cur_unit]  }  free(elements);  return;}    

Anyway, this is not the most optimized solution (a linked list can better be sorted without dissolving into a pointer-array) and it will involve some speed loss.

Well, good luck,
I hope there''s anyone knowing about AVL trees here
-Markus-

Trees make sorting faster Especially if you got a lot of nodes.
I can''t remember a good link right now, but you might want to check for "red-black trees". I''ve been told these are the fastest and easiest...

Just using an AVL tree will not clip your objects properly

It would create an automatically balencing tree and result in the fastest searches, but slower adds, more difficult iteration and mind-boggling complicated deletes.

I guess it would work if made the avl balence on the object position, but you would have to remove and re-add everything everytime it moved.

AVL trees are binary trees which guarentee O(log n) depth. Inserts and deletes can be slow, and should probably not be done in a real time game. And, if you need a static tree, then obviously an AVL tree is overkill.


Mike

I got another question:

What is STL ( Standard Templete Library ) ??
what kind of data stucture in STL??

A template is like a #defined class.
For example you could either write a linked list class:

class CLinkList {
private:
CLinkList *m_pCPrev;
CLinkList *m_pCNext;
void *m_pData;
...
};

which only stored variables of type void *. This means a bit of confusion and a lot of type casts.
So, as a workaround, you could derive a class for each type from the CLinkList class:

class CLLObjects : CLinkList {
...
}

Yet you would still have to rewrite each Add(), Remove(), Get() etc. function in the class. The solution here is a template:

template <class TYPE> class CLINKLIST {
private:
CLINKLIST<TYPE> *m_pCPrev;
CLINKLIST<TYPE> *m_pCNext;
TYPE *m_pData;
...
public:
void Add(TYPE *m_pData);
};

And to use it, just do

class CMyClass;
...
CLINKLIST <int> m_pIntList;
CLINKLIST <CMyClass> m_pMyClassList;
...
m_pMyClassList.Add(new CMyClass(123));

So, the STL is, like the name says, just a library of standard templates, like Queues, Hash lists, Strings, Trees and other data structures.
If you want a quick, self-optimizing tree, which keeps a lot of objects and moves the most recently used objects to the top, I''d recommend you a Splay-Tree,
www.LunaticSystems.de/splaytree.zip

-Markus-

The Standard Template Library is a collection of objects written a number of people, most of whom work at SGI (i think). They implement a spectrum of commonly used data structures.

goto www.sgi.com and search for STL and you can download thier library and header files. I haven''t used the STL much, but always hear good things about it.