Jump to content

[TOPIC: topicViewTemplate]
[GLOBAL: userSmallPhoto]
Photo

Rendering order of groups children
Started by gtt Nov 05 2013 02:34 PM

13 replies to this topic
[TOPIC CONTROLS]
This topic has been archived. This means that you cannot reply to this topic.
[/TOPIC CONTROLS]
[modOptionsDropdown]
[/modOptionsDropdown]
[reputationFilter]
[TOPIC: post.html]
#1

gtt

[GLOBAL: userInfoPane.html]
gtt
  • Contributor

  • 164 posts
  • Corona SDK

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 :)



[TOPIC: post.html]
#2

walter

[GLOBAL: userInfoPane.html]
walter
  • Moderator

  • 726 posts
  • Alumni

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.



[TOPIC: post.html]
#3

ingemar

[GLOBAL: userInfoPane.html]
ingemar
  • Corona Geek

  • 2,733 posts
  • Enterprise

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



[TOPIC: post.html]
#4

ingemar

[GLOBAL: userInfoPane.html]
ingemar
  • Corona Geek

  • 2,733 posts
  • Enterprise

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".



[TOPIC: post.html]
#5

Danny

[GLOBAL: userInfoPane.html]
Danny
  • Corona Geek

  • 2,597 posts
  • Corona Staff

@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

[TOPIC: post.html]
#6

ingemar

[GLOBAL: userInfoPane.html]
ingemar
  • Corona Geek

  • 2,733 posts
  • Enterprise

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  ;)).



[TOPIC: post.html]
#7

gtt

[GLOBAL: userInfoPane.html]
gtt
  • Contributor

  • 164 posts
  • Corona SDK

@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.

2. 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.

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

4. 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
                                --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
 

 

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 :)

 

Cheers,



[TOPIC: post.html]
#8

ingemar

[GLOBAL: userInfoPane.html]
ingemar
  • Corona Geek

  • 2,733 posts
  • Enterprise

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.



[TOPIC: post.html]
#9

gtt

[GLOBAL: userInfoPane.html]
gtt
  • Contributor

  • 164 posts
  • Corona SDK

@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?



[TOPIC: post.html]
#10

ingemar

[GLOBAL: userInfoPane.html]
ingemar
  • Corona Geek

  • 2,733 posts
  • Enterprise

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..



[TOPIC: post.html]
#11

ingemar

[GLOBAL: userInfoPane.html]
ingemar
  • Corona Geek

  • 2,733 posts
  • Enterprise

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

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



[TOPIC: post.html]
#12

rakoonic2

[GLOBAL: userInfoPane.html]
rakoonic2
  • Contributor

  • 503 posts
  • Corona SDK

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

Still, great work :)



[TOPIC: post.html]
#13

ingemar

[GLOBAL: userInfoPane.html]
ingemar
  • Corona Geek

  • 2,733 posts
  • Enterprise

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
 

 

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.



[TOPIC: post.html]
#14

rakoonic2

[GLOBAL: userInfoPane.html]
rakoonic2
  • Contributor

  • 503 posts
  • Corona SDK

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:

 

local sortableGroup = display.newSortableGroup()

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:

 

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

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

 

sortableGroup:setSort{ property = "y", direction = "bigger=nearer" }

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 :)

 

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

 

sortableGroup:sort()

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.

 




[topic_controls]
[/topic_controls]