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?

Answer

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