How do I efficiently sort objects by draw order when rendering a 2D game?

Question

I need to render a "tile" game with objects that overlap, because they are taller than the tile they stand on, like the games in these screenshots:

I don't know how to render them in the correct order. I intend to perform a sorting operation before every rendering, depending on the object's Y position. However, I'm worried it'll be too expensive, especially since very few objects change their Y positions.

Is sorting the most performant way? Is there any other way? What algorithm or data structure should I use?

Answer 1

When you have mobile objects and you want to get their draw order, there are two possible approaches how you can preprocess them before drawing:

1. Add a list of objects to each map tile. Iterate all objects and add them to the object list of the tile they are on. When you draw each tile, you first draw the tile itself, then sort its object list, then draw the objects, then delete the object list.

2. sort all objects by draw order. Then draw them all after drawing the map. Map tiles which obscure objects behind them need to be treated like objects in this case.

Option 1 is best when the objects move so quickly so they are in a different order every frame or when you have a lot of immobile objects, because you can then treat them like tiles.

Option 2 seems slow at first, but in most games you can make it a lot faster by using the right sorting algorithm.

In the majority of games, most of the time the object order will be the same or almost the same between two frames. In that case I would recommend you to use Insertion Sort. Usually it is considered a sub-par algorithm, but in the special case of data which is already nearly sorted it greatly outperforms all general-purpose sorting algorithms like quick-sort or merge-sort. I am using this method in the game I am currently developing. By replacing the standard Javascript sort with an own insertion-sort implementation I was able to reduce the execution time spent on object sorting from 3% to 0.2%, even though the default sort has the advantage of being implemented natively (measured in Firefox using the profiler of the Firebug extension).

Answer 2

i would split it up into logical Layers

i.e.

BackGround
Tiles
Objects //People, trees etc.
Gui

draw each separately and place on top of each other

with the tile i would try to draw in order(topleft to bottom right), or define the the specific layer it should be drawn to (you can probably compute this from world coordinates (or tile index)

i would imagine the solution may vary from engine to engine but this would be how i approached it from an XNA / MonoGame pov

Answer 3

I'd like to add that the stability of the sorting algorithm is also important.

When I first implemented sprite sorting in C# I used the built-in list sort method. This created a problem where overlapping sprites would flicker randomly when sharing the same Y value.

This happened because I used an unstable implementation of Quicksort, and the order in which those sprites were rendered would keep changing from frame to frame. I switched to a stable sorting algorithm and the problem went away.

I think I went with a Merge sort at the time, but Philipp makes a fine point about Insertion sort and its best case scenario, so I would look into that instead.

Answer 4

Just sort them. Use quicksort. (Usually that's the default sort on whichever language you're using.)

Just to give you an idea of the insignificance of thinking about other ways to do it: quick sorting 100,000 items will generally run in around 1 millisecond on modern hardware.

The only thing worth thinking about is that if your objects are huge, it's better to sort a list of pointers to your objects rather than the objects themselves (in order to prevent large copying.) Again, this is only a problem if you have megabytes of data.

Answer 5

I think you probably don't care.

If you have < 100 (moving) objects in view, then sorting them is likely to be so fast that it's not important.

You don't need to sort objects outside the view, if you have thousands of objects in the world, but out of view, you should probably put your optimisation effort on culling instead of depth-sorting.

Objects which are permanently attached to ground tiles, don't need to be sorted (more than once) as they won't move around, right?

Answer 6

I would sort every frame, just as Philipp with his option 2 but using Bubble Sort. The advantage is that this is an in-place algorithm and it has the same advantage as insertion sort on already (almost) sorted lists. Which should save you some memory.