Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 1 down vote favorite

I need to render a "tile" game, which are like these:

enter image description here

or

enter image description here

or

enter image description here

I don't know how to render them in correct order. I intend to perform a sorting operator before every rendering (depending on their Y position). However, I find it may be expensive, and very few objects change their Y positions.

Is sorting the best way to achieve this (I mean, the performance)? Is there any other way? What data structure should I use?

Please note: my question is, the way to draw entire game field with good performance, every frame (ignore the HUD and background).

share|improve this question
3  
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 at 17:12
1  
-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 at 22:03

6 Answers

up vote 6 down vote accepted

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

share|improve this answer
Thank you for your statistic. I will try implementing this way, and will comment later after I get the result :) – W.N. Feb 4 at 15:28
up vote 2 down vote

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.

share|improve this answer
up vote 0 down vote

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.

share|improve this answer
-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 at 23:17
2  
There is no "better" for this number of elements. In other words, it does not matter which sorting algorithm you use. – CaptainCodeman Feb 5 at 0:46
1  
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 at 1:26
1  
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 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 at 1:49
up vote 0 down vote

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.

share|improve this answer
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 at 22:04
-1: As I said on CaptainCodeman's answer, anything other than radix sort is bad advice. – Sean Middleditch Feb 4 at 23:18
up vote 0 down vote

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?

share|improve this answer
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 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. – W.N. Feb 4 at 15:33
up vote 4 down vote

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

share|improve this answer
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. – W.N. Feb 4 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 at 23:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.