Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Cipher3D

How to create a 2D sorted rendering list?

This topic is 5398 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 tried typTile* 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]

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
Insertion times in a sorted container:
O(n) for vectors, lists
O(log n) for trees

Rendering times:
O(n) for vectors, lists, trees

Removal times:
O(n) for vectors
O(1) for trees, lists

Conclusion : use a tree.

Victor Nicollet, INT13 game programmer

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!