How to sort display group elements based on Y position (simple code/pointers) (z-sorting)

Audio and Graphics
#1

I decided to share my solution for z-sorting elements in a display group, based on their Y position. My task is to sort the elements with higher Y (lower on the screen) to be in front of the ones with lower Y (that are higher on the screen). (Generating a lot of critters, that walk from left to right with different speeds, and their Y position is random, so it is important to sort them correctly, otherwise they look strange when overlapping)

Resources:
This API reference
And this tutorial on bubble sort.

In a nutshell, you rearrange the indices of the elements in the group you want to sort using the above mentioned bubble sort method, comparing their .y value, using the fact that the higher the index of an element in a display group, the more towards the front it gets.

Here is my simple code, just pass the display group you want and it should sort it’s elements based on their Y value:

sortZ = function(group)
local changes = 0
local function stepAgain()
	changes = 0
	for i=1, group.numChildren do
		if group[i+1] then
			local ind1 = group[i]
			local ind2 = group[i+1]
			if ind1.y > ind2.y then
				changes = changes + 1
				group:insert(i, ind2)
				--print("rearranging positions")
			end
		else
			break
		end
	end
end
stepAgain()
if changes > 0 then
	stepAgain()
else
	--print("rearranging done")
end
end

This function should be faster than sorting tables etc. I am using it with an “enterFrame” listener, with quite a lot of objects being sorted every frame, and as far as I can tell it doesn’t seriously impact performance, but your mileage may vary.

P.S. There are probably more optimized and faster ways of sorting a group than bubble sort, but it is simple and pretty easy to understand.

Cheers.

#2

Bubblesort is slow compared to quicksort. Table.sort uses quicksort implemented in C. This will always be faster than any lua self-rolled sort.

http://www.lua.org/source/5.3/ltablib.c.html#auxsort

#3

Thanks for the reply! What I meant was that if you sort a table, for example based on the Y position of its elements, you get a sorted table, but in my case you still have to rearrange the elements inside the display group based on the now sorted table, correct? Now I am proposing directly sorting the display group with the code above (or something similar and faster?). Am I correct to suppose that you cannot rearrange a display group with table.sort directly?

#4

No you can’t sort a displayGroup directly but you can do this…

local function depthSort(group)
  --depth sort this
  local objects = {}
  for i = 1, group.numChildren do 
    objects[#objects+1] = group[i]
  end
  table.sort( objects, function(a,b) return a.z < b.z end )
  for i = 1, #objects do 
    group:insert( objects[i] ) 
  end
end

depthSort(myDisplayGroup)

Note I derive a z value for my images as my games are isometric so sorting on just y is not good enough.

1 Like
#5

Cool! Thanks:)