depth sorting algorithm not sorting properly in various scenarios

[GoogleCodeExporter]

What steps will reproduce the problem?
Put many boxes on stage (lay them on the grid) and try to move one just
near another.

What is the expected output? What do you see instead?
I see (but rarely) that the box behind is for some time displayed in front
of the box that is in the front.

What version of the product are you using? On what operating system?
Vista 64bit.

Please provide any additional information below.

Solution: I changed the sorting routine to:

////////////////////////////////////////////////////
        //  SORT
        ////////////////////////////////////////////////////

        private function isoDepthSort (childA:Object, childB:Object):int
        {
            var boundsA:IBounds = childA.isoBounds;
            var boundsB:IBounds = childB.isoBounds;

            if (boundsA.right <= boundsB.left)
                return -1;

            else if (boundsA.front <= boundsB.back)
                return -1;

            else if (boundsA.top <= boundsB.bottom)
                return -1;

            else if (boundsA.left >= boundsB.right)
                return 1;

            else if (boundsA.back >= boundsB.front)
                return 1;

            else if (boundsA.bottom >= boundsB.top)
                return 1;

            else
                return 0;
        }

I just moved all 3 "<=" "if"-s to the top - somehow now it works (but
didn't do much testing).
Aditionally, I think that this algorithm should run faster because it exits
the testing loop earlier. That's because statistically the items appearing
earlier in the array are already sorted in the loop before, so it exits the
loop somewhere in the upper 3 "if"-s.

Btw I don't know what's the "return 0;" for - because this can happen by
error only (?). Two different objects in the list shouldn't have the same
depth (?).

Original issue reported on code.google.com by danko.ko...@gmail.com on 12 Mar 2009 at 10:06

[GoogleCodeExporter]

Thanks for submitting this.   I will try implementing your changes into the 
sorting
algorithm and see what I can come up with.  I have a few test cases (scenes 
rather).
 It does make sense now that you point it out that the series of if..else statements
exit more quickly.  Good tip to know.  Thanks again.  J

Original comment by jwopitz on 13 Mar 2009 at 3:03

• Changed state: Started

[GoogleCodeExporter]

Forgot to answer your question about the "else return 0"

I think originally I had put that there for spacial collisions.  I was going to 
have
a collision solver class handle that for further sorting mechanisms but haven't
gotten too far down that road.  Will need to rethink that later on.

Original comment by jwopitz on 13 Mar 2009 at 3:50

[GoogleCodeExporter]

This "return 0" is an impossible case, because it happens only when one object 
is 
inside another. This line hits only if no proper collision testing is 
implemented.

Btw I use a testing example like this when testing proper sorting: 
http://test.flexbytes.com/flash/Iso.swf
Since no collision detection is implemented here, the objects can be placed one 
inside another and then the sorting fails, but if you move objects with no 
overlapping, the sorting seems good to me.

The issue about exiting the loop earlier is important, because of the 
'separating 
axis theorem', which can be also used in the collision detection (basically try 
to 
exit the testing loop as soon as possible). More in this tutorial: 
http://www.metanetsoftware.com/technique/tutorialA.html

If you'll extend the framework with a collision detection (as I see on 
the 'features' page), perhaps you will need to use a broad-phase collision 
detection 
(a grid-based collision detection) in addition to your fine-grained detection. 
For a 
large number of objects in the view it could introduce some performance gains 
(for a 
small number of objects it can be a performance loss).

Another useful resource for isometric games is this document (Jon Ritman, the 
outhor 
of "Head over Heels" gives some tips for isometric games): 
http://dankokozar.com/documents/Jon_Ritmans_Isometric_Tutorial.pdf

ps. I am interested in isometry since 80-ties, and back in 2003 I've made my 
first 
attempt using AS1.0 and no OOP :-|, check it out: 
http://dkozar.com/flash/izometrija.swf

Original comment by danko.ko...@gmail.com on 13 Mar 2009 at 9:16

[GoogleCodeExporter]

Grid-based collision detection: 
http://www.metanetsoftware.com/technique/tutorialB.html

Original comment by danko.ko...@gmail.com on 13 Mar 2009 at 9:17

[GoogleCodeExporter]

I tested this algorithm again, but sorting errors in occur when changing the 
object's
z coordinate. Note that in my test app you can toggle objects z coordinate by
pressing SPACE, or set a height using NumPad keys 0-9.

Original comment by danko.ko...@gmail.com on 13 Mar 2009 at 11:42

Attachments:

• Iso.swf
• bad_sort.png

[GoogleCodeExporter]

Firstly thanks for all the resources provided.  I have quite a bit to look 
over.  I
did test using the SWF you provided in comment #5.  I was unable to recreate 
the PNG
but I do acknowledge that the issue exists.  

The problem I believe is not with our sorting algorithm but rather the 
implementation
of the algorithm by the Array.sortOn method the flash player uses.  I had done 
some
tested a while back where I was able to inspect the render pass on a small 
group of
objects.  I found that the Array.sortOn does not necessarily do a comparison on 
all
possible pairs of objects.  Implementing a manual sort is not ideal due to
performance issues.  Unfortunately I do not think there is an easy solutions.

I do plan to tinker a bit with our algorithm and see if reordering some of those
if..else statements might provide a solution.  The other thing is that I have 
been
working on a different sort of ISceneLayoutRenderer where animated objects are
thought of as direct children of the scene, however their display list gets 
owned by
the closest non-animated child in the scene effectively eliminating this issue. 
 The
problem with this solution is that there are some visual issues to address with 
which
parent owns the animated child in question given the child's coordinates at the 
time.

I am going to close out this issue for now.  I encourage discussion of this 
topic at
the user group and/or blog:

http://tech.groups.yahoo.com/group/as3isolib/
http://as3isolib.wordpress.com/

Original comment by jwopitz on 13 Mar 2009 at 4:47

• Changed title: depth sorting algorithm not sorting properly in various scenarios

[GoogleCodeExporter]

I agree that a depth-sorting is the greatest problem in isometric games. I never
solved it properly. I asked the 'isometric guru' Jon Ritman for tips. You should
check the document I mentioned
(http://dankokozar.com/documents/Jon_Ritmans_Isometric_Tutorial.pdf)
Jon describes the depth sorting using the linked list and overlapping axis. 

Original comment by danko.ko...@gmail.com on 13 Mar 2009 at 9:03

[GoogleCodeExporter]

[deleted comment]

[GoogleCodeExporter]

looks like testing1324 may have found a manual sorting algorithm that address 
most
situations.  It has been tested in a few scenarios, however developers should 
apply
this fix to their individual situation and report back if it fails to address 
your
sorting needs.

Original comment by jwopitz on 27 May 2009 at 9:11

• Changed state: Fixed

[GoogleCodeExporter]

I am facing a problem when am trying to "high-let" the grid cells .
What i done is
first of all am create a grid , in that am putting a isobox that means each 
cell have 
one isobox .When the user trying to move the obj from one place to another 
place cells
are highlighted but it takes some time to response .
And its create too much burden on CPU. And IsoEvents are taken too much memory 
to dispatch , i think this is the problem but am not able to reduce the 
isoEvents memory
can some body help me to resolve this problem.
thanks in advance 
M.Raju

Original comment by raj.virt...@gmail.com on 7 Sep 2010 at 2:54