   How to create a 2D sorted rendering list?
  I'm created a RPG-like game, and now I'm at the point where I'm coding the rendering "algorithms" (if you could call it that). My game will implement a view where it is at a slightly skewed angle, much like the RPGs of the olden days (Crono Trigger, Final Fantasy 3, etc).I've tried implementing this a couple of ways:vector m_tileList;I tried this first because I'm a huge fan of vectors, but then I couldn't find a fast way to sort this (qsort doesn't like vectors ) Then I triedtypTile* m_tileList;And reallocated every time I added a new tile to the list, and then finally, I sorted the whole thing right before I rendered it.That didn't work, because there were a million memory leaks, (damn MFC), or SOMETHING, and I've looked at the code over and over again, I can't see any place where i didn't delete when i needed to, etc. So besides me having memory leaks for the dynamic array implementation, does anybody have any tips/ideas on how to implement a sorted rendering list?And the program was running VERY slowly.THanks very much,Ciph[edited by - Cipher3D on February 7, 2004 11:41:49 AM]
  Umm, possibly std::sort? I believe it uses the quicksort algorithm.You could either update it when an object moves, or just before rendering (find out which would be more optimal for the map you are on). Also, you could split the world up into spaces, and just sort those that would be on-screen anyways. ;  I don''t think I made myself clear enough, sorry,I was sorting by Y values ;  Insertion times in a sorted container:O(n) for vectors, listsO(log n) for treesRendering times:O(n) for vectors, lists, treesRemoval times:O(n) for vectorsO(1) for trees, listsConclusion : use a tree.   Victor Nicollet, INT13 game programmer 