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

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?

• Generally speaking, for any "which is more efficient" type questions, the only real answer is one in which you profile real data (e.g. a shipping level) on real hardware (e.g. your minimum spec machine) to see which one is more efficient in whichever axis you are limited on (CPU time, GPU time, memory usage, etc.). Hopefully your game code is compartmentalized in such a way that refactoring to test different approaches is easy. – Tetrad Feb 4 '13 at 17:12
• -1 for a "what is most efficient" question which hasn't tested whether the thing being asked about is actually the cause of performance problems. – Trevor Powell Feb 4 '13 at 22:03

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).

• Thank you for your statistic. I will try implementing this way, and will comment later after I get the result :) – Luke Vo Feb 4 '13 at 15:28
• Upvoted for the Insertion Sort special case mention. – Mickael Bergeron Néron Aug 26 '18 at 9:07

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

• Thank you for your answer, but you only mention about manage the layers, and general way to draw the objects. However, I need an answer about specific algorithm/statistic to achieve it. – Luke Vo Feb 4 '13 at 15:35
• He just gave it to you. Keep separate lists of objects at different visible depths. There's nothing more to explain here. There is no specific algorithm at this point, just code. – Sean Middleditch Feb 4 '13 at 23:21

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.

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.

• -1: Radix sort is way way better for sorting depth and render queue keys (which is better than sorting just depth, as multiple objects at the same depth may use different render states that also need to be sorted together). – Sean Middleditch Feb 4 '13 at 23:17
• There is no "better" for this number of elements. In other words, it does not matter which sorting algorithm you use. – CaptainCodeman Feb 5 '13 at 0:46
• sure it matters. 1ms is huge for real-time rendering. Radix is easier to implement, and faster here. Even if quicksort is "fast enough" for the asker's case, it certainly isn't in general. Using a faster, easiser algorithm also allows more scalability down the road. Pick the right algorithm for the job. – Sean Middleditch Feb 5 '13 at 1:26
• The right algorithm for the job is the simplest algorithm that works. If you spend an hour optimizing something that doesn't need optimizing, you have simply wasted your time. My 1ms example was an extreme example just to give perspective, and doesn't apply here. – CaptainCodeman Feb 5 '13 at 23:31
• quicksort doesn't work in many cases for real-time rendering. recommending it as a general solution to the problem is still bad advice. it's adequate sometimes, but not all times. i'll undownvote if that clarification is made in the answer. easy and quick is good, but as game devs, we have to think about and care about these things. :) – Sean Middleditch Feb 6 '13 at 1:49

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?

• Immobile objects still need to be considered while sorting, because you need to know if an object which moves near them needs to be drawn before or after them. – Philipp Feb 4 '13 at 15:28
• @Philipp Thank you for your comment, I also intend to say so. While sorting, immobile objects are still in the list, so it's not important about it can move or not. – Luke Vo Feb 4 '13 at 15:33

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.

• At least according to this comparison Insertion sort seems to perform a lot faster. The discussion section also says that "insertion sort has lower overhead". – David Gouveia Feb 4 '13 at 22:04
• -1: As I said on CaptainCodeman's answer, anything other than radix sort is bad advice. – Sean Middleditch Feb 4 '13 at 23:18