Rendering order of groups children

We’re developing a new side scroll rpg/action game with Corona SDK 2.0

The scene is a parallax scene with 3 layers spreading 2400 points wide.

There is a ground level which has some “depth” to it and on this 2.5D floor we have characters (enemies and  player) moving around, and when they go up it is as if they are actually going further into the screen (z axis).

In this case objects with higher “y” value should have a higher “z-index” and should be rendered after objects with lower “y” values. The problem is that in Corona objects are drawn excusively in the “painter model” and I can only control the rendering order by re-inserting all the objects each frame.

We’ve been working with Spine, and I’ve noticed that in their runtime they have the same issue, and they reinsert all the images each frame to allow changing the draw order of elements within an animation sequence.

I’ve been doing some research on this and I’ve noticed that on a few other SDKs there is an option to either set a z-index or even tell the “group” (or in this case MOAILayer) to render the objects by one of few sorting modes.

I would think others will run into this issue as well once starting to take advantage of all the cool API’s in 2.0 and our current solution is to sort all the children by their y value, and insert this sorted list to the group, and this is done every frame… if you tell me this isn’t something I should worry about performance wise I’ll be glad to stick with my solution but it has some “code smell” to it :slight_smile:

This is on our feature request list, e.g. add a “z” property to control the order.

For now, you have to manage this manually. One suggestion I have is to divide your “z” plane into, say, 5 sections, so one group in front, 3 in between, and 1 in the background. Then, you can limit the sorting done to groups via some invalidation logic. In the best case, you only have to sort 1 or 2 groups, and the rest can be untouched.

If you have lots of objects on screen, you might want to do that anyway even if we had this feature, b/c you would have higher level knowledge about how to organize your scene, whereas Corona would not have that information and so would have to organize/sort via brute-force.

I created a z-index test a while ago where you can insert and remove objects without having to redraw everything.

I haven’t used it in a project yet but the concept seems to work quite well. 

The idea is to have a top level z-index group and to insert invisible placeholder objects for each z-index. The trick is to keep track of the index of these placeholder objects so that’s it’s easy to insert game-objects into the correct index.

Here’s the code if anyone’s interested: (EDIT: Modified to work with Graphics 1 and 2)

-- -- main.lua -- local buildInfo = system.getInfo("build"); local buildVersion = tonumber(buildInfo:sub(buildInfo:find("%.")+1)); math.randomseed(os.time()); local random = math.random; local spawnObject; -- predefined function local z; -- z-index display group local MAX\_LAYERS = 10; local MAX\_OBJECTS =100; -- helper functions to keep track of where current z-index is local makeIndex = function(i, order) order = order or "top"; if (i \< MAX\_LAYERS) then -- push indexes up for j = i + 1, MAX\_LAYERS do z.minIndex[j] = z.minIndex[j] + 1; end end local retVal; if (order == "top") then if (i == MAX\_LAYERS) then retVal = z.numChildren + 1; else retVal = z.minIndex[i + 1] - 1; end else -- assume "bottom" retVal = z.minIndex[i] + 1; end return retVal; end local removeIndex = function(i) if (i \< MAX\_LAYERS) then -- pop indexes down for j = i + 1, MAX\_LAYERS do z.minIndex[j] = z.minIndex[j] - 1; end end end -- create z-index group z = display.newGroup(); z.minIndex = {}; for i = 1, MAX\_LAYERS do local r = display.newRect(z, 0, i\*20, 10, 10); -- z-index placeholder object r.isVisible = false; z.minIndex[i] = i; end local travelTime; -- create objects in random z-index spawnObject = function() local zIndex = random(MAX\_LAYERS); local o = display.newRect(0, 0, 40, 40); local t = display.newText(zIndex, 0, 0, native.systemFont, 10) if (buildVersion \> 2000) then -- Graphics 2.0 o:setFillColor(random(), random(), random()); t:setFillColor(0); else -- Graphics 1.0 o:setFillColor(random(255), random(255), random(255)); t:setTextColor(0); t:setReferencePoint(display.CenterReferencePoint); t.x, t.y = 20, 20; end local g = display.newGroup(); g:insert(o); g:insert(t); g.y = zIndex \* 20 + 20; g.zIndex = zIndex; z:insert(makeIndex(zIndex), g); travelTime = 10000 + random(10000); transition.to(g, {time=travelTime, x=display.contentWidth, onComplete=function(o) -- remove old object removeIndex(o.zIndex); o:removeSelf(); -- create new object spawnObject(); end}); end for i = 1, MAX\_OBJECTS do spawnObject(); end

I hadn’t played with this code for a while, and I realized that new objects were always inserted at the bottom of the layer.

I modified the code above and added an argument so that it’s possible to insert a new object either at the top or bottom of the layer.

The default is “top”.

@ingemar, i did something similar with a game of mine, but rather than insert invisible objects, i just gave every object a .zIndex property, so they could be removed/reinserted at the correct position every time.

My use of this was fairly basic however

I give all objects a zIndex value as well so that I can remove them from the group properly.

However, I can’t think of a way to remove the reference objects without breaking the layers. I need the invisible reference objects so that I know which child number the “layer” starts with. Otherwise I’d have to traverse all visible objects in zIndex order and re-draw them one-by-one. The good thing about the approach above is that no re-draw is neccessary. Just insert an object in any layer and it’s automatically in the right display-order.

Give the code above a whirl. It’s quite fun to watch… (at least *I* think so  ;)).

@ingemar, Thanks! I had a similar solution in place but to maintain these zIndex is an overhead for since it will require me to re-insert object each frame to keep the actual draw order in line (if I understood your code, Also in my case placeholders wont work because there can be dozens of objects with the same index…

So here is what I did for now and it’s performing amazing! ((it’s still half baked but I will share it anyway :):

  1. override the group ‘insert’ method and instead of just inserting the object we do two things:

     a. find the right place to put it in the group with a binary search through the children.

     b. override the translate and removeSelf methods of the object so they trigger checking if the object is still in the right position or should be shifted with the next/prev sibling of the group.

  1. in the new object.translate we just swap neighbors if needed, so for example if object one index is 3 and the object two with index 4 has a lower ‘y’ value it will switch them, and will swap in a bubble sort manner until the object is located in the right position.

  2. the removeSelf of the object is overridden to reindex the other children of the group once an object is removed.

  3. we are assume object are translated at small deltas (or else the animation would look laggy) if you translate the object with huge deltas it will reduce performance as finding the new index is done with a bubble sort.

This solution works for us around x50 times faster than quick sorting the group each frame and the nice thing about it is that is doesn’t consume any CPU if the object are not moving or do not need a re-sort. 

Here is the code:

 local floor = math.floor local g = display.newGroup() --self sorted group g.\_insert = g.insert function g:insert( object ) --does not support indexed insert &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; --binary search the position to place local index local low = 1 local high = g.numChildren local mid = object.\_index or 1 while low \<= high do mid = floor((low+high)\*.5) if g[mid].y \> object.y then high = mid - 1 else if g[mid].y \< object.y then low = mid + 1 else index = mid break; end end end if g[mid] and g[mid].y \< object.y then index = mid+1 else index = mid end object.\_index = index for i=index+1, self.numChildren do self[i].\_index = i+1 end if not object.\_removeSelf then object.\_removeSelf = object.removeSelf end function object:removeSelf() for i=self.\_index+1, g.numChildren do g[i].\_index = i-1 end self:\_removeSelf() end --TODO: wrap x, y attributes with a metatable function object:clear() for i=self.\_index+1, g.numChildren do g[i].\_index = i-1 end self.\_index = nil self.translate = self.\_translate self.removeSelf = self.\_removeSelf end if not object.\_translate then object.\_translate = object.translate end local delay = timer.performWithDelay function object:translate( dx, dy ) local function translate() object:\_translate( dx, dy ) if dy \> 0 then while g[self.\_index] and self.\_index \< g.numChildren and g[self.\_index+1].y \< self.y do g:\_insert( self.\_index, g[self.\_index+1] ) g[self.\_index].\_index = self.\_index g[self.\_index+1].\_index = self.\_index+1 end elseif dy \< 0 then while g[self.\_index] and self.\_index \> 1 and g[self.\_index-1].y \> self.y do g:\_insert( self.\_index-1, self ) g[self.\_index].\_index = self.\_index self.\_index = self.\_index-1 end end end delay( 0, translate ) end self:\_insert( index, object ) end &nbsp;

So now we have a self sorting y group and it really has no effect on performance even with hundreds of objects there are two important points to mention:

  1. we DID NOT override the  .y property of the object so if you set directly object.y you need to re-insert it to the group. we just always use translate to move these objects so it’s not an issue for us.

  2. you have to call the removeSelf function explicity not let Corona clean up the object in some way if you are still going to use the group because Corona in some cases will not call the overridden removeSelf and will call the original one…

  3. you will notice what when we translate y we do the actual translate with a performWithDelay. The reason is that these translates are called from a loop that moves all the objects in the scene. if we change the order of the children array it will cause the loop to go crazy, process some items twice and other none, so in the specific case where we take an object and put it further in the array we are doing it after the loop completes (remember Corona is syncronous so it is called the next update). Going in the negative direction doesn’t effect the order of the following objects so it’s not needed, we still did it just to be more uniform in how we move the characters.

  4. if you have a lot of objects being created and removed you might want to consider maintaining a “link list” ._next and ._prev properties instead of ._index, these will allow removeSelf to do a O(1) removal, with the cost of maintaining one more variable per object.

Hope this help someone :slight_smile:

Cheers,

Yeah, that’s a great way to handle it.

Just a clarification with my code:

There can be any number of objects with the same “z-index”. You can also decide to insert the new object either behind or in front (default) of all objects within the layer.  *And* you don’t have to re-insert the objects every frame. Just insert any new object in any “z-index” layer and it will automatically be in the right place.

@ingemer I’m probably missing something, I’m looking at your code but I do not undetstand how it handles moving objects? if one object passes another in the y axis how when are the z-indices fixed?

Sorry, the code is a bit messy. I wrote it hastily to test a theory I had on how to make layers work.

(To see it in action you can copy-paste the code above into a main.lua)

I’ve stripped away some code below to emphasize the main concept

-- create a top-level group to hold all layers local z = display.newGroup() -- get a random "z-index" local zIndex = random(MAX\_LAYERS); -- create a rect and a text object local o = display.newRect(0, 0, 40, 40); local t = display.newText(zIndex, 0, 0, native.systemFont, 10) -- group the above objects together and create a zIndex property for the group local g = display.newGroup(); g:insert(o); g:insert(t); g.y = zIndex \* 20; g.zIndex = zIndex; -- insert the group into the z group z:insert(makeIndex(zIndex), g);

It’s the last line that does the “magic”. 

Now for a detailed (and hopefully comprehensible :)) explanation of what I’m doing:

Each display object created by corona has its own display order much like a FIFO. The objects will be rendered in sequential order. First-In, First-Out.

To emulate a layer hierarchy I create a top level z-group to hold all layers. Corona allows you to insert a display object within a display group at a certain index, effectively allowing you to insert new objects behind/in-front of older ones. The problem is that as objects are created/destroyed you have no easy way of knowing which index to use.

To solve this problem, this first thing I do is to create invisible place-holder objects who’s only purpose is to act as markers for where layers begin within the z-group. Every time a new object is inserted into a layer I call makeIndex() which returns the correct index to where the new object is to be inserted. Each layer has a minIndex property to keep track of which index the layer starts with (pointer to the place-holder object).

As an example: With 10 layers, 10 placeholder objects will be created with indices 1-10

Each layer’s minIndex will then be as follows:

z.minIndex[1] = 1 (placeholder object position)

z.minIndex[2] = 2 

z.minIndex[3] = 3 

z.minIndex[4] = 4 

z.minIndex[5] = 5 

z.minIndex[6] = 6 

z.minIndex[7] = 7 

z.minIndex[8] = 8 

z.minIndex[9] = 9 

z.minIndex[10] = 10 

If an object is inserted into layer 5, makeIndex(5) will +1 minIndex for layers 6 to 10 and return 6 (placeholder + 1).
z.minIndex[1] = 1 
z.minIndex[2] = 2 
z.minIndex[3] = 3 
z.minIndex[4] = 4 
z.minIndex[5] = 5 
z.minIndex[6] = 7 
z.minIndex[7] = 8 
z.minIndex[8] = 9 
z.minIndex[9] = 10 
z.minIndex[10] = 11 

If an object is later inserted into layer 9, makeIndex(9) will +1 minIndex for layer 10 and return 11.
z.minIndex[1] = 1
z.minIndex[2] = 2
z.minIndex[3] = 3
z.minIndex[4] = 4
z.minIndex[5] = 5
z.minIndex[6] = 7
z.minIndex[7] = 8
z.minIndex[8] = 9
z.minIndex[9] = 10
z.minIndex[10] = 12

If a second object is later inserted into layer 5, makeIndex(5, “bottom”) will +1 minIndex for layers 6 to 10 and return 6. makeIndex(5, “top”) will return 7 (“top” is the default if omitted).

z.minIndex[1] = 1
z.minIndex[2] = 2
z.minIndex[3] = 3
z.minIndex[4] = 4
z.minIndex[5] = 5
z.minIndex[6] = 8
z.minIndex[7] = 9
z.minIndex[8] = 10
z.minIndex[9] = 11
z.minIndex[10] = 13

Also, before removing an object the function removeIndex(object.zIndex) must be called so that minIndex for each layer is updated properly. 

I hope this makes some sense…

I realized that my original sample code only worked with Graphics 2.

I’ve updated it to work with both G1 and G2 now.

Darn I wish I had time to have a stab at knocking up some code, you guys have got me rather interested :slight_smile:

Still, great work :slight_smile:

OK, now I’ve modularized it a bit to keep the logic separated. Give it a whirl and say what you think.

Now there’s a layer.lua with the layer logic and main.lua with program logic.

-- -- layer.lua -- local M = {}; local z; -- z-index display group local MAX\_LAYERS -- max number of layers -- helper functions to keep track of where current z-index is local makeIndex = function(i, order) order = order or "top"; if (i \< MAX\_LAYERS) then -- push indexes up for j = i + 1, MAX\_LAYERS do z.minIndex[j] = z.minIndex[j] + 1; end end local retVal; if (order == "top") then if (i == MAX\_LAYERS) then retVal = z.numChildren + 1; else retVal = z.minIndex[i + 1] - 1; end else -- assume "bottom" retVal = z.minIndex[i] + 1; end return retVal; end M.insertObject = function(object, order) if (not object.zIndex) then print("LAYER: Display object is missing a zIndex property"); return; end z:insert(makeIndex(object.zIndex, order), object) end M.removeObject = function(object, options) options = options or {}; local i = object.zIndex; if (i \< MAX\_LAYERS) then -- pop indexes down for j = i + 1, MAX\_LAYERS do z.minIndex[j] = z.minIndex[j] - 1; end end if (not options.keepObject) then object:removeSelf(); end end M.changeIndex = function(object, newIndex, order) M.removeObject(object, {keepObject=true}); object.zIndex = newIndex; M.insertObject(object, order); end M.init = function(maxLayers) if (not maxLayers) then print("LAYER init(): Must specify number of layers") return; end MAX\_LAYERS = maxLayers; z = display.newGroup(); z.minIndex = {}; for i = 1, MAX\_LAYERS do local r = display.newRect(z, 0, 0, 1, 1); -- z-index placeholder object r.isVisible = false; z.minIndex[i] = i; end return M; end return M;

-- -- main.lua -- local buildInfo = system.getInfo("build"); local buildVersion = tonumber(buildInfo:sub(buildInfo:find("%.")+1)); math.randomseed(os.time()); local random = math.random; local MAX\_LAYERS = 10; -- max # of layers local MAX\_OBJECTS = 100; -- max # of objects local travelTime; -- time to travel across screen local spawnObject; -- predefined function local layer = require("layer").init(MAX\_LAYERS); local onTap = function(event) local object = event.target; local newIndex = object.zIndex \> 1 and object.zIndex - 1 or MAX\_LAYERS; layer.changeIndex(object, newIndex); object.y = object.zIndex \* 20 + 20; return true; end spawnObject = function() local zIndex = random(MAX\_LAYERS); local o = display.newRect(0, 0, 40, 40); local t = display.newText(zIndex, 0, 0, native.systemFont, 10) if (buildVersion \> 2000) then -- Graphics 2.0 o:setFillColor(random(), random(), random()); t:setFillColor(0); else -- Graphics 1.0 o:setFillColor(random(255), random(255), random(255)); t:setTextColor(0); t:setReferencePoint(display.CenterReferencePoint); t.x, t.y = 20, 20; end local g = display.newGroup(); g:insert(o); g:insert(t); g.y = zIndex \* 20 + 20; g.zIndex = zIndex; g:addEventListener("tap", onTap) layer.insertObject(g); g.xScale, g.yScale = 0.01, 0.01; transition.to(g, {time=800, xScale=1.0, yScale=1.0, transition=easing.outElastic}); travelTime = 10000 + random(7000); transition.to(g, {time=travelTime, x=display.contentWidth, onComplete=function(o) transition.to(o, {time=200, alpha=0, xScale=0.01, yScale=0.01, onComplete=function(o) layer.removeObject(o); spawnObject(); -- create new object end}); end}); end -- create MAX\_OBJECTS objects with a random z-index for i = 1, MAX\_OBJECTS do spawnObject(); end &nbsp;

layer.lua exposes these functions:

init(maxLayers)

Must be called to initialize the module. maxLayers is the number of layers wanted

insertObject(object [, “top” | “bottom”])

Inserts a display object into a layer.   IMPORTANT : object must have a zIndex property set.

“top” will insert the object above all other objects within the layer.

“bottom” will insert the object under all other objects within the layer.

Defaults to “top” if omitted.

removeObject(object)

Removes an object

changeIndex(object, newIndex [, “top” | “bottom”])

Changes the zIndex of an object

main.lua creates 100 objects (multi-colored square boxes) each with a random zIndex. The boxes move across the screen and when they hit the edge they are removed and a new box is created with a random zIndex. Rinse and Repeat…

New feature: You can tap on any square to send it up to the previous layer.

This is all done without having to redraw the whole stack.

For fun, I did my take on it. You can find it here:

https://github.com/Rakoonic/Sprite-sorting

It works by requiring a file which extends the normal display object, so you end up with:

[lua]local sortableGroup = display.newSortableGroup()[/lua]

then you need to define how to set up the sorting, by either supplying your own sort function, or specifying a property of each of the children, and then a sort order.

Example of doing your own sort function:

[lua]sortableGroup:setSort( function( a, b ) return ( a.x + a.y ) < (b.x + b.y ) ; end )[/lua]

To specify a property and a sort direction you’d do:

[lua]sortableGroup:setSort{ property = “y”, direction = “bigger=nearer” }[/lua]

where the property can be anything that all the children share (eg, x, width, alpha etc), and the direction specifies what values of that property are considered nearer to you or not. The two values for that are “bigger=nearer” and “smaller=nearer” - hopefully reasonably obvious :slight_smile:

Then in the future, once you have set up said sort function somehow, all you need to do is call:

[lua]sortableGroup:sort()[/lua]

and by the wonders of modern magic it will rearrange all the sprites in the group correctly.

The github library above has a working sample and a few varieties set up so you can quickly test tweaking the properties and direction etc.

This is on our feature request list, e.g. add a “z” property to control the order.

For now, you have to manage this manually. One suggestion I have is to divide your “z” plane into, say, 5 sections, so one group in front, 3 in between, and 1 in the background. Then, you can limit the sorting done to groups via some invalidation logic. In the best case, you only have to sort 1 or 2 groups, and the rest can be untouched.

If you have lots of objects on screen, you might want to do that anyway even if we had this feature, b/c you would have higher level knowledge about how to organize your scene, whereas Corona would not have that information and so would have to organize/sort via brute-force.

I created a z-index test a while ago where you can insert and remove objects without having to redraw everything.

I haven’t used it in a project yet but the concept seems to work quite well. 

The idea is to have a top level z-index group and to insert invisible placeholder objects for each z-index. The trick is to keep track of the index of these placeholder objects so that’s it’s easy to insert game-objects into the correct index.

Here’s the code if anyone’s interested: (EDIT: Modified to work with Graphics 1 and 2)

-- -- main.lua -- local buildInfo = system.getInfo("build"); local buildVersion = tonumber(buildInfo:sub(buildInfo:find("%.")+1)); math.randomseed(os.time()); local random = math.random; local spawnObject; -- predefined function local z; -- z-index display group local MAX\_LAYERS = 10; local MAX\_OBJECTS =100; -- helper functions to keep track of where current z-index is local makeIndex = function(i, order) order = order or "top"; if (i \< MAX\_LAYERS) then -- push indexes up for j = i + 1, MAX\_LAYERS do z.minIndex[j] = z.minIndex[j] + 1; end end local retVal; if (order == "top") then if (i == MAX\_LAYERS) then retVal = z.numChildren + 1; else retVal = z.minIndex[i + 1] - 1; end else -- assume "bottom" retVal = z.minIndex[i] + 1; end return retVal; end local removeIndex = function(i) if (i \< MAX\_LAYERS) then -- pop indexes down for j = i + 1, MAX\_LAYERS do z.minIndex[j] = z.minIndex[j] - 1; end end end -- create z-index group z = display.newGroup(); z.minIndex = {}; for i = 1, MAX\_LAYERS do local r = display.newRect(z, 0, i\*20, 10, 10); -- z-index placeholder object r.isVisible = false; z.minIndex[i] = i; end local travelTime; -- create objects in random z-index spawnObject = function() local zIndex = random(MAX\_LAYERS); local o = display.newRect(0, 0, 40, 40); local t = display.newText(zIndex, 0, 0, native.systemFont, 10) if (buildVersion \> 2000) then -- Graphics 2.0 o:setFillColor(random(), random(), random()); t:setFillColor(0); else -- Graphics 1.0 o:setFillColor(random(255), random(255), random(255)); t:setTextColor(0); t:setReferencePoint(display.CenterReferencePoint); t.x, t.y = 20, 20; end local g = display.newGroup(); g:insert(o); g:insert(t); g.y = zIndex \* 20 + 20; g.zIndex = zIndex; z:insert(makeIndex(zIndex), g); travelTime = 10000 + random(10000); transition.to(g, {time=travelTime, x=display.contentWidth, onComplete=function(o) -- remove old object removeIndex(o.zIndex); o:removeSelf(); -- create new object spawnObject(); end}); end for i = 1, MAX\_OBJECTS do spawnObject(); end

I hadn’t played with this code for a while, and I realized that new objects were always inserted at the bottom of the layer.

I modified the code above and added an argument so that it’s possible to insert a new object either at the top or bottom of the layer.

The default is “top”.

@ingemar, i did something similar with a game of mine, but rather than insert invisible objects, i just gave every object a .zIndex property, so they could be removed/reinserted at the correct position every time.

My use of this was fairly basic however

I give all objects a zIndex value as well so that I can remove them from the group properly.

However, I can’t think of a way to remove the reference objects without breaking the layers. I need the invisible reference objects so that I know which child number the “layer” starts with. Otherwise I’d have to traverse all visible objects in zIndex order and re-draw them one-by-one. The good thing about the approach above is that no re-draw is neccessary. Just insert an object in any layer and it’s automatically in the right display-order.

Give the code above a whirl. It’s quite fun to watch… (at least *I* think so  ;)).

@ingemar, Thanks! I had a similar solution in place but to maintain these zIndex is an overhead for since it will require me to re-insert object each frame to keep the actual draw order in line (if I understood your code, Also in my case placeholders wont work because there can be dozens of objects with the same index…

So here is what I did for now and it’s performing amazing! ((it’s still half baked but I will share it anyway :):

  1. override the group ‘insert’ method and instead of just inserting the object we do two things:

     a. find the right place to put it in the group with a binary search through the children.

     b. override the translate and removeSelf methods of the object so they trigger checking if the object is still in the right position or should be shifted with the next/prev sibling of the group.

  1. in the new object.translate we just swap neighbors if needed, so for example if object one index is 3 and the object two with index 4 has a lower ‘y’ value it will switch them, and will swap in a bubble sort manner until the object is located in the right position.

  2. the removeSelf of the object is overridden to reindex the other children of the group once an object is removed.

  3. we are assume object are translated at small deltas (or else the animation would look laggy) if you translate the object with huge deltas it will reduce performance as finding the new index is done with a bubble sort.

This solution works for us around x50 times faster than quick sorting the group each frame and the nice thing about it is that is doesn’t consume any CPU if the object are not moving or do not need a re-sort. 

Here is the code:

 local floor = math.floor local g = display.newGroup() --self sorted group g.\_insert = g.insert function g:insert( object ) --does not support indexed insert &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; --binary search the position to place local index local low = 1 local high = g.numChildren local mid = object.\_index or 1 while low \<= high do mid = floor((low+high)\*.5) if g[mid].y \> object.y then high = mid - 1 else if g[mid].y \< object.y then low = mid + 1 else index = mid break; end end end if g[mid] and g[mid].y \< object.y then index = mid+1 else index = mid end object.\_index = index for i=index+1, self.numChildren do self[i].\_index = i+1 end if not object.\_removeSelf then object.\_removeSelf = object.removeSelf end function object:removeSelf() for i=self.\_index+1, g.numChildren do g[i].\_index = i-1 end self:\_removeSelf() end --TODO: wrap x, y attributes with a metatable function object:clear() for i=self.\_index+1, g.numChildren do g[i].\_index = i-1 end self.\_index = nil self.translate = self.\_translate self.removeSelf = self.\_removeSelf end if not object.\_translate then object.\_translate = object.translate end local delay = timer.performWithDelay function object:translate( dx, dy ) local function translate() object:\_translate( dx, dy ) if dy \> 0 then while g[self.\_index] and self.\_index \< g.numChildren and g[self.\_index+1].y \< self.y do g:\_insert( self.\_index, g[self.\_index+1] ) g[self.\_index].\_index = self.\_index g[self.\_index+1].\_index = self.\_index+1 end elseif dy \< 0 then while g[self.\_index] and self.\_index \> 1 and g[self.\_index-1].y \> self.y do g:\_insert( self.\_index-1, self ) g[self.\_index].\_index = self.\_index self.\_index = self.\_index-1 end end end delay( 0, translate ) end self:\_insert( index, object ) end &nbsp;

So now we have a self sorting y group and it really has no effect on performance even with hundreds of objects there are two important points to mention:

  1. we DID NOT override the  .y property of the object so if you set directly object.y you need to re-insert it to the group. we just always use translate to move these objects so it’s not an issue for us.

  2. you have to call the removeSelf function explicity not let Corona clean up the object in some way if you are still going to use the group because Corona in some cases will not call the overridden removeSelf and will call the original one…

  3. you will notice what when we translate y we do the actual translate with a performWithDelay. The reason is that these translates are called from a loop that moves all the objects in the scene. if we change the order of the children array it will cause the loop to go crazy, process some items twice and other none, so in the specific case where we take an object and put it further in the array we are doing it after the loop completes (remember Corona is syncronous so it is called the next update). Going in the negative direction doesn’t effect the order of the following objects so it’s not needed, we still did it just to be more uniform in how we move the characters.

  4. if you have a lot of objects being created and removed you might want to consider maintaining a “link list” ._next and ._prev properties instead of ._index, these will allow removeSelf to do a O(1) removal, with the cost of maintaining one more variable per object.

Hope this help someone :slight_smile:

Cheers,