Depth Sorting

[.dank]

I've been trying to sort objects depths based on their Y position but have not been able to do it efficiently. I was able to successfully sort objects with a selection sort algorithm and a quick sort algorithm; however, both have only been partly successful. Selection sort gets about 8-10/30 FPS with 13 objects and gets about 14-18/30 FPS. This is not good enough as I figure I could have as many as a hundred objects to be sorted at once.

After digging around, I found that array.sort() is more efficient than a quick sort implemented in AS3 and that calling swapChildren() or swapChildrenAt() at every swap was bogging it down. So now I am copying the objects array and sorting it with sort() and then comparing the two and swapping displayObjects so as only to call the swapChildren() or swapChildrenAt() method once per element. It appears to be running, and at full speed, though it won't swap correctly. Here is my code:


public class DepthSorter extends Sprite{

////////////////////////////////////////////////////////////////////
//// Constructor ////
public function DepthSorter() {
this.addEventListener(Event.ENTER_FRAME, SortDepths);
}

////////////////////////////////////////////////////////////////////
//// Sort Depths ////
public function SortDepths(e:Event):void {
var oldArr:Array = MovieClip(root).objectsArr;
// Copy Array
var sortedArr:Array = new Array();
for(var i = 0; i < oldArr.length - 1; i++){
sortedArr.push(oldArr[i]);
}
// Sort on the Y parameter
sortedArr.sort(sortOnY);

//Compare sorted with old and swap indices
for(i = 0; i < oldArr.length - 1; i++){
for(var j = 0; j < oldArr.length - 1; j++){
// Swap when match is found
if(sortedArr[i] == oldArr[j]){
//trace("Swapped children");
MovieClip(root).swapChildren(oldArr[i], sortedArr[i]);
break;
}
}
}
}

////////////////////////////////////////////////////////////////////
//// Sort On Y ////
private function sortOnY(a, b):Number {
if (a.y > b.y) {
return 1;
} else if (a.y < b.y) {
return -1;
} else {
return 0;
}
}
}

I can't figure out where the problem is or even if this algorithm will work at all. I would be very grateful if anyone could tell me what it is that is wrong as I have been working on this for a much longer time than I thought I would be.


Here is the source (http://flak-games.com/medieval/wp-content/uploads/2008/06/depthsorting.zip)

Thanks

[Fidodo]

Ok, your problem is that you are approaching this from the wrong perspective. First of all you are sorting every frame meaning that you have a cost of n. Then you have a nested for loop where you are checking each object with every other object, costing you n^2 which means as you add objects your cost will rise exponentially, each object costing even more than the last.

To fix the first problem, you only need to rearrange the object when it is moving. If the y value is changing the indexes should never change so why waste processing power right? The second problem you can fix by only checking the object directly above and below it at any time.

I implemented this in a simple example:


package {
import flash.display.Sprite;
import flash.events.MouseEvent;
import flash.events.Event;
public class Order extends Sprite {
var objects:Array = new Array();//Array of all objects
var activeSprite:Sprite;//This sprite will be checked for depth
public function Order() {
var temp:Sprite;//A temp sprite to modify until added to object
var color:int;
for (var i:int = 0; i<8; i++) {
//Create a random shade of red
color = Math.ceil(0xFF - Math.random()*0xAA)<<8*2;
temp = new Sprite();
//Code to draw the boxes
temp.graphics.beginFill(color);
temp.graphics.drawRect(-20,-50,40,50);
temp.graphics.endFill();
temp.graphics.lineStyle(2,0x000000);
temp.graphics.moveTo(-20,-50);
temp.graphics.lineTo(20,-50);
temp.graphics.lineTo(20,0);
temp.graphics.lineTo(-20,0);
temp.graphics.lineTo(-20,-50);
//Places the sprite in a straight diagonal, where each sprite overlaps.
temp.x = i*20+50;
temp.y = i*40+70;
//Mouse listeners for dragging
temp.addEventListener(MouseEvent.MOUSE_DOWN,mouseD own);
temp.addEventListener(MouseEvent.MOUSE_UP,mouseUp) ;
//Executes to check for active sprites since MouseEvents only runs once
stage.addEventListener(Event.ENTER_FRAME,enterFram e);
objects.push(temp);
addChild(temp);
//Note: Sprites are manually placed in order based on how I set the y value
}
}
function enterFrame(e:Event) {
//Only runs depth checking code if a sprite is active
if (activeSprite) {
checkDepth();
}
}
function checkDepth() {
var checkSprite:Sprite;//The sprite who's y coords we will check against
var activeSpriteDepth:int;//The current depth of the activeSprite
activeSpriteDepth = getChildIndex(activeSprite);
//Checks y coords of sprite above (below in depth)
if (activeSpriteDepth>0) { //Don't check if we are already at the bottom
checkSprite = Sprite(getChildAt(activeSpriteDepth-1));
//Loop in case the sprite is multiple depths out of place
while (activeSprite.y<checkSprite.y) {
swapChildren(activeSprite,checkSprite);
activeSpriteDepth = getChildIndex(activeSprite); //Update the sprite depth so we can loop
if (activeSpriteDepth<=0) {
break; //We need to break here so we don't check a depth less than 0
}
checkSprite = Sprite(getChildAt(activeSpriteDepth-1));
}
}
//Same thing but for y coords below (above in depth)
if (activeSpriteDepth<numChildren-1) {
checkSprite = Sprite(getChildAt(activeSpriteDepth+1));
while (activeSprite.y>checkSprite.y) {
swapChildren(activeSprite,checkSprite);
activeSpriteDepth = getChildIndex(activeSprite);
if (activeSpriteDepth>=numChildren-1) {
break;
}
checkSprite = Sprite(getChildAt(activeSpriteDepth+1));
}
}
}
function mouseDown(e:MouseEvent) {
//Since we are dragging the sprite, it's position may change and the sprite is thus active
activeSprite = Sprite(e.target);
activeSprite.startDrag();
}
function mouseUp(e:MouseEvent) {
activeSprite.stopDrag();
//We might stop dragging while a frame hasn't executed yet so run a final check depth
checkDepth();
//The sprite can no longer change positions now that we aren't dragging it
activeSprite = null;
}
}
}
Because only the objects above and below are checked it should be infinitely scalable and run with any amount of objects. Even in the least efficient scenario (every object has it's y position moving at once) you would have a processing cost of n at most.

The only thing to note is that this assumes the objects are in order to begin with because it only checks depths when something is active. That means that every time you add a new object you will need to check it's depths to get it in position. I didn't do this because I added them in order.

Here's the swf
http://ieng9.ucsd.edu/%7Etetler/swf/Order.html

EDIT: I altered the swf to have 100 constantly moving objects to show the efficiency... I got bored.

[BMA]

Maybe you could try this one: http://www.kirupa.com/forum/showthread.php?p=1897023&highlight=depth#post1897023

[omgnoseat]

woops double post, read below

[omgnoseat]

Ok, your problem is that you are approaching this from the wrong perspective. First of all you are sorting every frame meaning that you have a cost of n. Then you have a nested for loop where you are checking each object with every other object, costing you n^2 which means as you add objects your cost will rise exponentially, each object costing even more than the last.

To fix the first problem, you only need to rearrange the object when it is moving. If the y value is changing the indexes should never change so why waste processing power right? The second problem you can fix by only checking the object directly above and below it at any time.

I implemented this in a simple example:


package {
import flash.display.Sprite;
import flash.events.MouseEvent;
import flash.events.Event;
public class Order extends Sprite {
var objects:Array = new Array();//Array of all objects
var activeSprite:Sprite;//This sprite will be checked for depth
public function Order() {
var temp:Sprite;//A temp sprite to modify until added to object
var color:int;
for (var i:int = 0; i<8; i++) {
//Create a random shade of red
color = Math.ceil(0xFF - Math.random()*0xAA)<<8*2;
temp = new Sprite();
//Code to draw the boxes
temp.graphics.beginFill(color);
temp.graphics.drawRect(-20,-50,40,50);
temp.graphics.endFill();
temp.graphics.lineStyle(2,0x000000);
temp.graphics.moveTo(-20,-50);
temp.graphics.lineTo(20,-50);
temp.graphics.lineTo(20,0);
temp.graphics.lineTo(-20,0);
temp.graphics.lineTo(-20,-50);
//Places the sprite in a straight diagonal, where each sprite overlaps.
temp.x = i*20+50;
temp.y = i*40+70;
//Mouse listeners for dragging
temp.addEventListener(MouseEvent.MOUSE_DOWN,mouseD own);
temp.addEventListener(MouseEvent.MOUSE_UP,mouseUp) ;
//Executes to check for active sprites since MouseEvents only runs once
stage.addEventListener(Event.ENTER_FRAME,enterFram e);
objects.push(temp);
addChild(temp);
//Note: Sprites are manually placed in order based on how I set the y value
}
}
function enterFrame(e:Event) {
//Only runs depth checking code if a sprite is active
if (activeSprite) {
checkDepth();
}
}
function checkDepth() {
var checkSprite:Sprite;//The sprite who's y coords we will check against
var activeSpriteDepth:int;//The current depth of the activeSprite
activeSpriteDepth = getChildIndex(activeSprite);
//Checks y coords of sprite above (below in depth)
if (activeSpriteDepth>0) { //Don't check if we are already at the bottom
checkSprite = Sprite(getChildAt(activeSpriteDepth-1));
//Loop in case the sprite is multiple depths out of place
while (activeSprite.y<checkSprite.y) {
swapChildren(activeSprite,checkSprite);
activeSpriteDepth = getChildIndex(activeSprite); //Update the sprite depth so we can loop
if (activeSpriteDepth<=0) {
break; //We need to break here so we don't check a depth less than 0
}
checkSprite = Sprite(getChildAt(activeSpriteDepth-1));
}
}
//Same thing but for y coords below (above in depth)
if (activeSpriteDepth<numChildren-1) {
checkSprite = Sprite(getChildAt(activeSpriteDepth+1));
while (activeSprite.y>checkSprite.y) {
swapChildren(activeSprite,checkSprite);
activeSpriteDepth = getChildIndex(activeSprite);
if (activeSpriteDepth>=numChildren-1) {
break;
}
checkSprite = Sprite(getChildAt(activeSpriteDepth+1));
}
}
}
function mouseDown(e:MouseEvent) {
//Since we are dragging the sprite, it's position may change and the sprite is thus active
activeSprite = Sprite(e.target);
activeSprite.startDrag();
}
function mouseUp(e:MouseEvent) {
activeSprite.stopDrag();
//We might stop dragging while a frame hasn't executed yet so run a final check depth
checkDepth();
//The sprite can no longer change positions now that we aren't dragging it
activeSprite = null;
}
}
}
Because only the objects above and below are checked it should be infinitely scalable and run with any amount of objects. Even in the least efficient scenario (every object has it's y position moving at once) you would have a processing cost of n at most.

The only thing to note is that this assumes the objects are in order to begin with because it only checks depths when something is active. That means that every time you add a new object you will need to check it's depths to get it in position. I didn't do this because I added them in order.

Here's the swf
http://ieng9.ucsd.edu/%7Etetler/swf/Order.html

EDIT: I altered the swf to have 100 constantly moving objects to show the efficiency... I got bored.

your code works wonderfull, good job :)
When I try to use it in my own project however, it just refused to work :(



//xml
var xmlRequest:URLRequest = new URLRequest("gallery.xml");
var xmlLoader:URLLoader = new URLLoader(xmlRequest);

var walkTimer:Timer = new Timer((Math.random()*5000)+ 3000);
walkTimer.start();

//information for movement
var moveRight:Boolean = true;
var walkingDirection:Number = -1;

//arrays
var walkers:Array = new Array();
var loaders:Array = new Array();
var preloaders:Array = new Array();

//speeds
var xSpeed:Number = 2;
var ySpeed: Number = 0.5;
var xSpeeds:Array = new Array();
var ySpeeds:Array = new Array();
var maximumSpeed:Number;
var minimumSpeed:Number;

//xml data
var xmlData:XML;
var xmlDescription:String; //description from the xml

//tooltip
var Tooltip:tooltip;

//image iinformation
var currentImage:Number;
var fullHeight:Number;
var fullWidth:Number;

//preloader
var preloader:Preloader;

//walkers
var blockHolder:walkingImage;
var overWalkers:Boolean = false;
var currentWalker:Number;



xmlLoader.addEventListener(Event.COMPLETE, xmlLoaded);

function xmlLoaded(e:Event):void{

xmlData = new XML(e.target.data);

//loop for each image in the xml
for(var i:Number = 0; i< xmlData.image.length(); i++){

//make a new walking character
blockHolder = new walkingImage;
blockHolder.x = Math.random()*stage.stageWidth;
blockHolder.y = Math.random()*stage.stageHeight;

blockHolder.buttonMode = true;
walkers.push(blockHolder); //push in array


//make a new loader for the image
var imageLoader:Loader = new Loader;
var imgURL:URLRequest = new URLRequest(xmlData.image[i].imageURL);
imageLoader.load(imgURL);
imageLoader.name = String(i);

//add the imageloader in the character
walkers[i].addChild(imageLoader);
loaders.push(imageLoader);

//set the speeds for every generated object
xSpeeds[i] = 2;
ySpeeds[i] = 0.2;

// -- load the variable values from the xml --
//-------------------------------------------------
fullWidth = xmlData.options.maximumWidth;
fullHeight = xmlData.options.maximumHeight;

maximumSpeed = xmlData.options.maximumWalkerSpeed;
minimumSpeed = xmlData.options.minimumWalkerSpeed;


imageLoader.contentLoaderInfo.addEventListener(Eve nt.COMPLETE, imageLoaded);
}//end of loop
}


function imageLoaded(e:Event):void{

//check which imageLoader triggered the complete event, and add the corresponding walker
addChild(walkers[e.target.loader.name]);

loaders[i].addEventListener(MouseEvent.MOUSE_OVER, overWalker);
loaders[i].addEventListener(MouseEvent.MOUSE_OUT, outWalker);
loaders[i].addEventListener(MouseEvent.CLICK, clickImage);
walkTimer.addEventListener(TimerEvent.TIMER, changeDirection);
stage.addEventListener(Event.ENTER_FRAME, walkRandomly);
arrangeButton.addEventListener(MouseEvent.CLICK, clickArrange);
}
}



function changeDirection(e:TimerEvent):void{

* code for random movement, of no importance *

boundaries();
perspective();
}
}

function boundaries():void{

*code for screenwrappig, not important aswell*
}

function perspective():void{

*code for proportional scaling, not important aswell*

if (activeMovieClip) {
checkDepth();
trace("checkDepth() executed");
}


}

function checkDepth() {

var checkMovieClip:MovieClip;//The MovieClip who's y coords we will check against
var activeMovieClipDepth:int;//The current depth of the activeMovieClip
activeMovieClipDepth = getChildIndex(activeMovieClip);

//Checks y coords of MovieClip above (below in depth)
if (activeMovieClipDepth>0) { //Don't check if we are already at the bottom
checkMovieClip = MovieClip(getChildAt(activeMovieClipDepth-1));
//Loop in case the MovieClip is multiple depths out of place
while (activeMovieClip.y<checkMovieClip.y) {
swapChildren(activeMovieClip,checkMovieClip);
activeMovieClipDepth = getChildIndex(activeMovieClip); //Update the MovieClip depth so we can loop

if (activeMovieClipDepth<=0) {
break; //We need to break here so we don't check a depth less than 0
}

checkMovieClip = MovieClip(getChildAt(activeMovieClipDepth-1));
}
}

//Same thing but for y coords below (above in depth)
if (activeMovieClipDepth<numChildren-1) {
checkMovieClip = MovieClip(getChildAt(activeMovieClipDepth+1));

while (activeMovieClip.y>checkMovieClip.y) {
swapChildren(activeMovieClip,checkMovieClip);
activeMovieClipDepth = getChildIndex(activeMovieClip);
if (activeMovieClipDepth>=numChildren-1) {
break;
}
checkMovieClip = MovieClip(getChildAt(activeMovieClipDepth+1));
}
}
}


The code places movieclips on the stage from the library which move in random speed. I'm trying to use your code to get the depths right.

There are actually several things that I don't understand about your code. Like the use of activeMovieClip/checkMovieclip, there never is any reference to the objects in the array, so how do those movieclips know to which objects they should respond?

Your code is a little too smart for me haha. Hope someone can help me out with this.

[omgnoseat]

bump

also tried senoculars:

var sortedItems:Array = new Array(mc1, mc2, mc3);
function arrange():void {
sortedItems.sortOn("y", Array.NUMERIC);
var i:int = sortedItems.length;
while(i--){
if (getChildIndex(sortedItems[i]) != i) {
setChildIndex(sortedItems[i], i);
}
}
It works, but when 2 objects reach the same y value they begin to flash and stutter. Seems logical since 2 objects can't share the same index, but I can't think of a way to work around this.

[FizixMan]

Why don't you make your indices multiples of 10 or 100? Then you can do checks that if you have multiple objects at the same depth (say, depth 40) then subsequent ones can be placed at 41, 42, 43, 44 etc. Then as you make your checks (your getChildIndex() != i check), you should check that it's within the valid range (40 to 49).

[omgnoseat]

Why don't you make your indices multiples of 10 or 100? Then you can do checks that if you have multiple objects at the same depth (say, depth 40) then subsequent ones can be placed at 41, 42, 43, 44 etc. Then as you make your checks (your getChildIndex() != i check), you should check that it's within the valid range (40 to 49).
I'm not sure if I exactly understand what you mean, but doesn't the index only go as far as the number of items on the display list in as3?
Maybe you could show an example? =]

I've also found this: http://mike.newgrounds.com/news/post/59329
Which seems to work when I look at the swf, but I don't understand anything of it. My experience with custom classes are still very small.

Hope someone can help me out, this has been driving me mad, it's only thing I need to get sorted before finishing my project.

[FizixMan]

I don't know if this will work, just whipped it off the top of my head. Replace your code:

while(i--){
if (getChildIndex(sortedItems[i]) != i) {
setChildIndex(sortedItems[i], i);
}
}

With this code:


var placedClips:Object = new Object(); //to keep track of the number of objects at the same Y depth
var multiplier:Number = 10; //change this to 100 if you expect to have more than 10 clips at a single Y value
var intendedDepth:Number = -1;
var currentDepth:Number = -1;
while(i--)
{

//initializes the collection for this depth
if (placedClips[i] == null)
{
placedClips[i] = 0;
}

//the intended depth means even if you wanted to set the depth based on Y value, it will use a multiplier of that
//so instead of 1, 2, 3, it will be 10, 20, 30, which leaves 11-19, 21-29, 31-39 open for overlaps
intendedDepth = i * multiplier;
currentDepth = getChildIndex(sortedItems[i]);

//if the clip isn't already in the valid range, shift it there
if (currentDepth < intendedDepth || currentDepth > intendedDepth)
{
setChildIndex(sortedItems[i], intendedDepth + placedClips[i]);
}

//increment the number of clips placed at that depth
//this makes it so subsequent ones will be placed at depths 11, 12, 13, 14 etc instead of always at 10
placedClips[i]++;
}

[omgnoseat]

I don't know if this will work, just whipped it off the top of my head. Replace your code:

while(i--){
if (getChildIndex(sortedItems[i]) != i) {
setChildIndex(sortedItems[i], i);
}
}With this code:


var placedClips:Object = new Object(); //to keep track of the number of objects at the same Y depth
var multiplier:Number = 10; //change this to 100 if you expect to have more than 10 clips at a single Y value
var intendedDepth:Number = -1;
var currentDepth:Number = -1;
while(i--)
{

//initializes the collection for this depth
if (placedClips[i] == null)
{
placedClips[i] = 0;
}

//the intended depth means even if you wanted to set the depth based on Y value, it will use a multiplier of that
//so instead of 1, 2, 3, it will be 10, 20, 30, which leaves 11-19, 21-29, 31-39 open for overlaps
intendedDepth = i * multiplier;
currentDepth = getChildIndex(sortedItems[i]);

//if the clip isn't already in the valid range, shift it there
if (currentDepth < intendedDepth || currentDepth > intendedDepth)
{
setChildIndex(sortedItems[i], intendedDepth + placedClips[i]);
}

//increment the number of clips placed at that depth
//this makes it so subsequent ones will be placed at depths 11, 12, 13, 14 etc instead of always at 10
placedClips[i]++;
}
hey, thanks for responding, even though my understanding has been quite low in this topic.
Nice job on the code, I understand what you mean now. Unfortunatly the code generates the following error for each item in the loop [9 times in this case]:

RangeError: Error #2006: The supplied index is out of bounds. I'm not quite sure what could be wrong, when I trace currentDepth it gives me 9 for each item in the loop.
I also don't understand the use of the placedClips object, it doesn't contain anything so what is the use of checking what it contains?

Thanks alot for the help again :)

[FizixMan]

The error might be coming out simply because I wrote this in an Actionscript 2.0 mindset (I imagine instead of using a dynamic Object type for placedClips you should use a Dictionary).

The "placedClips" is simply a list that keeps track of the number of clips stored at a single depth. So if you already placed one at depth 40, it increments the listing for index "40" by 1.

Think of the listing like this:
placedClips[key] = [value]
read as:
placedClips[DepthZone] = [NumberOfClipsInDepthZone]

When the next entry comes around it adds that number into the depth at: setChildIndex(sortedItems[i], intendedDepth + placedClips[i]);

So it says, "set my depth to 40 PLUS the number of clips already in the 40-zone", which makes it 41, 42, 43 and so on.

EDIT: on what line exactly is the error coming up?

[Valaran]

The error might be coming out simply because I wrote this in an Actionscript 2.0 mindset (I imagine instead of using a dynamic Object type for placedClips you should use a Dictionary).

The "placedClips" is simply a list that keeps track of the number of clips stored at a single depth. So if you already placed one at depth 40, it increments the listing for index "40" by 1.

Think of the listing like this:
placedClips[key] = [value]
read as:
placedClips[DepthZone] = [NumberOfClipsInDepthZone]

When the next entry comes around it adds that number into the depth at: setChildIndex(sortedItems[i], intendedDepth + placedClips[i]);

So it says, "set my depth to 40 PLUS the number of clips already in the 40-zone", which makes it 41, 42, 43 and so on.

EDIT: on what line exactly is the error coming up?

This is not possible in AS3, the display list is restricted by the number of items within it, you cannot place objects on an arbitrary index as in AS2. If the number of children in the displaylist is 5, means you have 0, 1, 2, 3, 4 available, nothing more, nothing less :)

[FizixMan]

><

Then you'll probably have to apply this before as part of your original sorting of DisplayObjects.

[omgnoseat]

This is not possible in AS3, the display list is restricted by the number of items within it, you cannot place objects on an arbitrary index as in AS2. If the number of children in the displaylist is 5, means you have 0, 1, 2, 3, 4 available, nothing more, nothing less :)
Thats why I thought aswell.

I'm not sure if I exactly understand what you mean, but doesn't the index only go as far as the number of items on the display list in as3?


Thanks for the help anyway FisixMan.
Why did they have to make depth sorting so complicated =/
I'll try if I can find an other solution, but thanks alot for responding :)

[far100]

Lee Brimelow used in his carousel tutorial, here is the tutorial (http://www.gotoandlearn.com/play?id=92)and here is his blog post (http://theflashblog.com/?p=470)

However it is for 3D and Flash10.