next »

[raigan]

3. For each entity
   a. Insert entity into list at right Z order.

I feel like there is a lot hidden in the phrase "at right Z order": how do you know where to insert each entity?! Either your "for each" is traversing them back-to-front, or you're using some sort of sorted list... right? Either way you can't avoid sorting if you want an ordered list.

But possibly I'm missing something.

[Theotherguy]

3. For each entity
   a. Insert entity into list at right Z order.

I feel like there is a lot hidden in the phrase "at right Z order": how do you know where to insert each entity?! Either your "for each" is traversing them back-to-front, or you're using some sort of sorted list... right? Either way you can't avoid sorting if you want an ordered list.

But possibly I'm missing something.

You are missing something. The list is sorted the entire time. The key is that we are maintaining the sortedness with each insertion, rather than inserting all the elements and then sorting afterward. The only thing needed to do to insert an item in the list in the right order is a simple comparison with each element until we find the right location to insert it, and then we stick it there. If you are using a simple doubly-linked list structure, insertion is a constant time operation. The most number of comparisons we will ever have to do is N comparisons in the worst case, so it is clear that the process is O(N).

This can be proved quite easily with induction.

EDIT:

I'm an idiot. This is O(N^2), as bad as bubble sort.

EDIT 2:

In fact, this is insertion sort.

[bart_the_13th]

This abandoned games relies on z sorting, even it's collision take z into account
http://filebin.gamedevid.org/view/100bv/

I only zsort everything when a grass reach the nearest znear value, then move that grass to the farthest z value (zfar). The 'zsort' itelf is just the internal AS3 sort. I think the result is considerably smooth