I have a RTS game with about a load average of 10 to 20 thousand on-map objects at a time. Now I need a quick z sort routine- but for thousands of objects every frame?! What is the best method for this? (my objects are stored in a dynamic array). I think I will start by narrowing the sort list (making a dynamic array of only on-screen objects- don''t see why I need to sort objects off screen) then using a quick sort method? Any ideas/comments appreciated. ill-lusion.com
ziggy@ill-lusion.com

quote:

---

Original post by Ziggy5000

I have a RTS game with about a load average of 10 to 20 thousand on-map objects at a time. Now I need a quick z sort routine- but for thousands of objects every frame?! What is the best method for this? (my objects are stored in a dynamic array).

I think I will start by narrowing the sort list (making a dynamic array of only on-screen objects- don''t see why I need
to sort objects off screen) then using a quick sort method?

---

It depends on how data is stored and organized. Quicksort is often a decent choice, but not always the best choice. If your items to be sorted come in sequentially, it may make better sense to use insertion sort (and use binary search to find the insertion location).




---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!
---- --- -- -
New York. New York. New York. Texas. Texas. New York. New York. Canada.
---- --- -- -

Are you using OpenGL or some other API? Try using the Zbuffer. Use the Y value of your player in the z pos.

If possible, only sort onscreen objects too. Hopefully you won''t have 10-20 thousand onscreen at once

Give the radix sort a look. It''s also known as the Postman''s sort or hash sort. Let''s take a quick example. Say your distances from the near clipping plane to the far are given values from 0 to 100. You start by creating one array of 10 lists, then take everything 00-09 into element [0], 10-19 into [1], and so on (object n goes into list n/10). You can choose whichever radix you want of course, and you may also subdivide each list to do another radix sort, or a quicksort from there.

David

From what I remember, the merge sort was the best sort to use when you had tens of thousands of elements to sort. Once you get down to about 1000, use the quick sort, and at about 16 you switch to the insertion sort.

Actually, if you''re sorting on load, the insertion sort is the fastest (hence the name).
If the list in nearly sorted, the insertion sort is again the fastest to use (faster than quick sort), so you could do an insertion sort whenever something moves.