Quick sorting when order rarely changes

Question

I am working on a scrolling 2D game (I think Red Alert or Zelda), but I am bullied with a drawing.

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

In order for things to be displayed opposite each other correctly, they need to be drawn in a certain order (first, removed objects and work in the direction of the "camera").

Now I sort the list of all objects (both types) every time the game is updated (100 times per second), and this seems like a huge waste of processor time. The order of objects rarely changes, and when they do, they usually only move one item up or down in the list.

Another problem is that you need to consider only those objects that are actually on the screen. Since maps can become quite large with 1000 objects, I don’t want to sort them all 100 times per second.

How do you suggest me to solve this?

Answer 1

Bubble Sort the best case is when items are already sorted. In this case, you get O (n) comparisons. According to Wikipedia:

In computer graphics, it is popular due to the ability to detect a very small error (for example, a swap of only two elements) in almost sorted arrays and fix it only with linear complexity (2n).

But it was considered a “bad” algorithm for a number of reasons mentioned in a related article. You can see 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 in which the sorted items are stored, and which is notified when the position of the position changes. If the objects do not move significantly compared to how often they are redrawn, this will save a lot of processing time, since you only need to re-sort the elements whose position has changed, you can avoid re-sorting by all until at least one moves element.

Answer 2

Keep track of which objects are on the screen in the vector, and add new visible objects to the end. Use sorting or sorting bubbles to sort. This value is inefficient for random data, but ~ O (n) for almost sorted data.

Answer 3

Consistent with sorting bubbles and inserts.

I have other ideas without sorting: if you rarely change order, you can track the history of changes and restore order if sorting is necessary. Moreover, if the items are not added or deleted, simply restore the snapshot of the original ordered list, it will be very easy and fast. If I clearly understood your question.

Answer 4

Consider using a PriorityQueue, or perhaps a doubly linked list, so that you can move items in it directly when necessary, rather than using coercive coercion based on the Z order. You should also carefully examine the clip areas.

Answer 5

Sorting 100 objects will take a very long time. But if performance really matters, and you know that the list is similar to being almost sorted, with a small number of items out of order, merge or type sorting algorithms are likely to give you good performance. It has O (N) performance for a list that is already sorted, or that has only a few items out of order.

However, do not reject the general-purpose sorting algorithm provided by the Java library until you have measured its actual performance. Since this is a common goal, it should be implemented in such a way as to provide reasonable performance for a wide range of cases, including cases when the list is almost sorted.

In fact, the standard Java sort method used merge sort to Java 6 and was changed to TimSort from Java 7.