Effecient way to use z-index for 2d games

Newbie & Debugging Questions
#1

I want to add rendering priorities with z-index for my entities in my 2D game.

For example, I have two entities: A with z-index 4, and B with z-index 5.
If they where on the same position, B would be rendered in front of A because of its higher z-index value.

Here is how my game works: I have an array list with entities. I iterate over the list in the rendering method to access their images.

for(GameObject go : stage.entities)
	drawObject(go);

This means the last entity added to the game will have the highest rendering priority(this is unwanted).

So I was thinking of giving the entity class a new variables called z-index and sort the list according to it, which would give the results I want.
The problem is that the list would have to be resorted every time a new entity is added.

Some ideas?

#2

Make a ‘layer’ or ‘z’ int in your gameobject class. Right before rendering, sort your gameobjects list so that gameobjects with highest z value are first in the list, and gameobjects with lowest z value are at the end of the list.

#3

That is exactly what I wrote. Maybe I was unclear?

The problem with that is, that the sorting may affect the performance in a negative way.

#4

Never worry with perforamance before there is a problems. Modern cpu’s can sort billions entries in second. Its common to sort all render objects as optimization(for less state changes)

Edit: You can also add item to middle of list so you don’t need to sort but just move rest of the list one step back.

#5

Anything you write into your code effects performance in a bad way… But it is so small usually you don’t even notice.

#6

Sorting is at most a few if statements and a loop, that won’t affect anything. Consider all the games you have probably seen or played and their complexity. If something as trivial as sorting took up a bunch of CPU cycles then we wouldn’t have these amazing games.

#7

If you set stage.entities right off the bat you can just sort them, it won’t affect your performance significantly.

If you are adding and removing GameObjects in stage.entities often, look into using a linked list instead so you can efficiently insert GameObjects in the middle of your List. This eliminates having the ArrayList have to make a new array and move all array elements from one array to another which can be very slow mattering on the number of elements.

#8

Alright. I guess I had the wrong idea about the sorting.

I assume Collections.sort use quicksort algorithm?

#9

It might be more trouble than it is worth but if you have a relatively finite number of z-index values you can have a List for each layer. The layers can then be held in an array which you iterate over. Something like:


// Loop through each layer
for (int i=0; i< layers.length; i++) {

   // For each layer render everything on that layer.
   for (Renderable renderable : layers[i]) {
      renderable.render();
   }
}

if you want your z-index to take arbitrary values or if the z-index is changing frequently it may not be the best approach.

#10

Collections.sort uses modified quicksort, and the latest implemention in JDK7 uses some fancy newfangled “timsort”. It’s fast enough.

Cas :slight_smile:

#11

Indeed, Timsort is a hybrid sorting algorithm, combining all the best traits (that’s the goal anyway) of several algorithms so it can be more effective on more kinds of data.
Quicksort is fast, but on mostly-sorted data it can run in O(n2) time, whereas Timsort’s worst-case is listed as O(n log n), which is much better for large datasets, and the sub-algorithms keep it very quick on small sets.

Here you can see it visualized: http://www.youtube.com/watch?v=NVIjHj-lrT4

I do like my sorting algorithms :wink:

#12

Roughly how many items are being sorted?

For most situations, I vote with princec’s recommendation. But if items are being handled concurrently, you can consider keeping them in a ConcurrentSkipListSet. To do so, you’ll have to make a Comparator that uses the Z data.

[quote]This implementation provides expected average log(n) time cost for the contains, add, and remove operations and their variants.
[/quote]
http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentSkipListSet.html

I’m using this to store “AudioEvent” objects (custom code I’m writing for my audio library) which can be generated from MIDI data or via game state events. So the list has to allow concurrent access since the audio processing is happening in its own thread and I don’t want to create any blocks via synchronization.