Fast sorting where order seldom changes

Question

I'm working on a 2D game with a scrolling view (think Red Alert or Zelda) but I'm stuggling with the drawing.

Basically there are two types of objects that are drawn on the map. Some have fixed positions (like trees and buildings) and others move around (players, enemies, flying arrows).

For things to appear in front of each other in a correct way they need to be drawn in a specific order (distant objects first and work towards the "camera").

Right now I'm sorting the list of all objects (both kinds) every time the game updates (100 times per second) and it feels a like a huge waste of CPU time. The order of the objects very seldom changes, and when they do they usually only move one position up or down in the list.

Another issue is that only the objects that are actually on screen needs to be be considered. As the maps could become quite large with 1000s of objects I don't want to sort them all 100 times per second.

How would you suggest I solve this?

Answer 1

Bubble Sort's best case is when the elements are already sorted. You'll get O(n) comparisons in that case. According to Wikipedia:

In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n).

But it's considered to be a "bad" algorithm for a variety of reasons mentioned in the linked article. You may want to profile the difference between it and Insertion Sort (also O(n) for sorted lists) to see which is faster in practice.

Another option is to use a data structure that keeps the sorted items in it, and which gets notified when an item's position changes. If objects don't move around much compared to how often they get re-drawn, that would save a lot of processing time since you'd only have to re-sort the elements whose position has changed, you could avoid re-sorting at all until at least one element has moved.

Answer 2

Keep track of which objects are on screen in a vector and add newly visible objects at the end of it. Use bubble sort or insertion sort for sorting. This is increadably inefficient for random data, but ~O(n) for almost sorted data.

Answer 3

Agreed with bubble and insertion sorts.

I have other ideas without sort: if seldom change order, you could only track the change history and restore the order when sort needed. Moreover, if elements are not added or removed, just restore the snapshot of original ordered list, it will be very easy and fast. If I understood your question clearly.

Answer 4

Sorting 100 objects will not take very long. But if performance really does matter, and you know that the list is likeky to be almost sorted, with few items out of order, the merge sort or Tim sort algorithms are likely to give you good performance. It has O(N) performance for a list that is already sorted, or which has only a few elements out of order.

That said, do not dismiss the general purpose sorting algorithm provided by the Java library, until you have measured its actual performance. As it is general purpose, it should be implemented in a manner that gives reasonable performance for a wide range of cases, including cases when the list is almost sorted already.

In fact, the standard Java sorting method used merge sort upto Java 6, and changed to TimSort with Java 7.

Answer 5

Have a think about using a PriorityQueue, or possibly a doubly-linked list so you could reposition items in it directly when needed rather than brute-forcing based on Z order. You should also thoroughly investigate clip regions.