Lightweight dynamic depth sorting

[peter.allen.christen]

I looked around, and the only solutions I found for sorting children of displayGroups involved copying everything out, sorting, then replacing. Also, they seemed to sort by the Y coordinate, which doesn’t work for me.

So I wrote a function that sorts the children of a displayGroup without copying in and out, that takes advantage of the general stability of the collection from frame to frame, and that sorts by Z.

[lua]displayGroup.sortZ = function(self)

  local lowerBound, upperBound = 1, self.numChildren

  local sortedMaxZ, index = self[lowerBound].z or 0, lowerBound + 1

  while index <= upperBound do

    local testItem = self[index]

    local testZ = testItem.z or 0

    if testZ < sortedMaxZ then

      local lteIndex = index - 2

      while lteIndex > 0 do

        local lteZ = self[lteIndex].z or 0

        if testZ >= lteZ then break end

        lteIndex = lteIndex - 1

      end

      --printf(“Moving %i to %i”, index, lteIndex+1)

      self:insert(lteIndex + 1, testItem)

      index = index + 1

    elseif testZ > sortedMaxZ then

      local gteIndex = index + 1

      while gteIndex <= upperBound do

        local gteZ = self[gteIndex].z or 0

        if testZ <= gteZ then break end

        gteIndex = gteIndex + 1

      end

      if gteIndex - 1 == index then

        --printf("%i is already in place", index)

        sortedMaxZ = testZ

        index = index + 1

      else

        --printf(“Moving %i to %i”, index, gteIndex)

        self:insert(gteIndex, testItem)

      end

    else

      --printf("%i is already in place", index)

      sortedMaxZ = testZ

      index = index + 1

    end

  end

end[/lua]

I’ve tested it quite a bit, so I’m fairly sure it’s bug free. If a child does not have a Z field, it is presumed to be 0. The implementation is basically a bubble sort, since it is easy to write, easy to understand, and performs well when the collection is already mostly sorted. Also, this sort is stable, whereas anything run through table.sort is not guaranteed to be so.

I have this function run every frame after all input and timing events have completed. It’s quite nice to set the Z field of any child and have its render order handled automatically. What’s really handy, though, is that now I can tween depth.

In the Windows simulator, the CPU hit for the below example was not noticeably different than with the sorting turned off (both clocked in around 0.3% CPU usage). Here is an example of it handling faux 3D card animations:

[torbenratzlaff]

Very nice, thanks alot for sharing.

I came up with a similar solution (but using table.sort) some time ago, where I had an additional approach, in which only dynamic/mooving objects are updated (reinserted in the group), as the z-order for static objects stays the same. This speeded up the process even more, if you got only a few mooving objects. (like when a player mooves through a forest)

[peter.allen.christen]

@torbenratzlaff

I came up with a similar solution (but using table.sort) some time ago, where I had an additional approach, in which only dynamic/mooving objects are updated (reinserted in the group), as the z-order for static objects stays the same. This speeded up the process even more, if you got only a few mooving objects. (like when a player mooves through a forest)

That’s a great place to be. I could only figure out three ways to accomplish that:

1. Every place I set the Z field, I also set a flag.
2. Do some metatable __index and __newindex magic to interrupt the getting and setting of Z as a field.
3. Do not have Z as a field, but instead access it through :getZ() and :setZ() methods.

I dislike #1 because it requires me to remember to set the field manually. That’s just asking for bugs.

I dislike #2 because I’m trying to stay away from metatable magic. My previous experience is that magic like that spreads like wildfire through the codebase, with readability, interoperability, and maintainability suffering.

I dislike #3 because I can only tween fields, not get/set property pairs. I might be able to modify the tween system to interpret Z changes as method calls, but that gets into the same magic that I dislike from #2.

I initially disliked sorting every frame because it seemed wasteful, but then I ran it. With 50-60 items, it seemed to have no CPU impact. So it scales better than I anticipated. Good enough for now, at least.

Thanks for commenting!

[torbenratzlaff]

Let me elaborate that further. In my model I sorted based on a z value just like you did.

In the second step I loop backwards through the sorted table and check for each object, if it has the .dynamic flag.

If it does, it is inserted into the right position according to it’s index. There are some small errors here, as the shifting might change the objects position afterwards, but as this function is called each frame, you don’t notice that, as it is corrected on the next frame.

I think the right approach might differ from ituation to situation, as if you have like an RPG with many objects and tiles, I think my solution is faster, but if you got primarly mooving objects (like in your cards example) yours should work better.

[torbenratzlaff]

Very nice, thanks alot for sharing.

I came up with a similar solution (but using table.sort) some time ago, where I had an additional approach, in which only dynamic/mooving objects are updated (reinserted in the group), as the z-order for static objects stays the same. This speeded up the process even more, if you got only a few mooving objects. (like when a player mooves through a forest)

[peter.allen.christen]

@torbenratzlaff

I came up with a similar solution (but using table.sort) some time ago, where I had an additional approach, in which only dynamic/mooving objects are updated (reinserted in the group), as the z-order for static objects stays the same. This speeded up the process even more, if you got only a few mooving objects. (like when a player mooves through a forest)

That’s a great place to be. I could only figure out three ways to accomplish that:

1. Every place I set the Z field, I also set a flag.
2. Do some metatable __index and __newindex magic to interrupt the getting and setting of Z as a field.
3. Do not have Z as a field, but instead access it through :getZ() and :setZ() methods.

I dislike #1 because it requires me to remember to set the field manually. That’s just asking for bugs.

I dislike #2 because I’m trying to stay away from metatable magic. My previous experience is that magic like that spreads like wildfire through the codebase, with readability, interoperability, and maintainability suffering.

I dislike #3 because I can only tween fields, not get/set property pairs. I might be able to modify the tween system to interpret Z changes as method calls, but that gets into the same magic that I dislike from #2.

I initially disliked sorting every frame because it seemed wasteful, but then I ran it. With 50-60 items, it seemed to have no CPU impact. So it scales better than I anticipated. Good enough for now, at least.

Thanks for commenting!

[torbenratzlaff]

Let me elaborate that further. In my model I sorted based on a z value just like you did.

In the second step I loop backwards through the sorted table and check for each object, if it has the .dynamic flag.

If it does, it is inserted into the right position according to it’s index. There are some small errors here, as the shifting might change the objects position afterwards, but as this function is called each frame, you don’t notice that, as it is corrected on the next frame.

I think the right approach might differ from ituation to situation, as if you have like an RPG with many objects and tiles, I think my solution is faster, but if you got primarly mooving objects (like in your cards example) yours should work better.