Has anyone actually come up with perfect isometric depth sorting?

Ive been going back to isometrics again recently, and Ive been trying to come up with the elusive perfect depth swapping method. By perfect I mean the following that objects can move freely in 3D isometric space in units of pixels, and depth swapping is independent of tile size. My definition of isometric space is where the x-axis runs NW-SE, the z-axis runs NE-SW, and the y-axis runs N-S.

Ive come close to it before by using a method like the following, but I dont think I ever came up with a perfect solution. This is just off the top of my head now so it might not be perfect. Note that this presumes all MovieClips that were attached to the stage where attached at the same depth level (e.g. -100) and their depth sorted isometrically immediatly.

Code:

---

function isoDepthSort (mc, isoPos) {
 mc.swapDepths((isoPos.x*103)+(isoPos.z*100)+(isoPos.y*103));
}

---

my 2 cents:

1. you need to track the tile you are on. This could be done by knowing the tileX,tileY, number of rows and colls etc..
2 dupliate the tile not by usign depth+=1 rather depth+=2; so you will get tiles like 1,3,5 etc..etc..
3.once you know the tile you are on then the hero depth=tile-1;
or:
if you have tiles 1 and 3 the hero will be put in between or 2.

ms

Do you literally mean to duplicate the tile the hero is on, or just to get its base depth and place the hero slightly higher than it. Either way it sounds like to me that this would work where there is only possible 1 object per tile area. I actually created a few things using that above idea ages ago but it didnt seem very efficient or flexible to me.

Thanks for the input btw.

no no you dont chage the tile depth, just the hero depth, and yes it works for only one object per tile, however 2 objects cannot occupy same place at the same time thus this should not be a problem.

ms

Yeah thats what I thought you meant.

But 2 or more objects can occupy the same tile as movement is allowed by pixel. Lets say each isometric tile is a grid of 16x16 squares, than there could potentially be more than 1 object on each tile if the objects grid size is smaller than that of the tile grid size (say 2x2 squares).

Hi Covenent,

Not sure if you have my game book or not, but I developed an exact depth sorting algorithm that applies to isometric worlds. It is discussed in the chatper on isometrics.

In MX I created an isometric class. When you use it, depth sorting is sort of built-in to it. Atttached is an example file that uses it.

For anyone interested in just seeing the class code in MX, here it is:

Code:

---

isometricAS = function (maxx, maxz) {
        this.maxx = maxx;
        this.maxz = maxz;
        this.theta = 30;
        this.alpha = 45;
        this.theta *= Math.PI/180;
        this.alpha *= Math.PI/180;
        this.sinTheta = Math.sin(this.theta);
        this.cosTheta = Math.cos(this.theta);
        this.sinAlpha = Math.sin(this.alpha);
        this.cosAlpha = Math.cos(this.alpha);
        this.leeway = 5;
};
isometricAS.prototype.mapToScreen = function(xpp, ypp, zpp) {
        var yp = ypp;
        var xp = xpp*this.cosAlpha+zpp*this.sinAlpha;
        var zp = zpp*this.cosAlpha-xpp*this.sinAlpha;
        var x = xp;
        var y = yp*this.cosTheta-zp*this.sinTheta;
        //var z = zp*this.cosTheta+yp*this.sinTheta;
        return [x, y];
};
isometricAS.prototype.mapToIsoWorld = function(screenX, screenY) {
        var z = (screenX/this.cosAlpha-screenY/(this.sinAlpha*this.sinTheta))*(1/(this.cosAlpha/this.sinAlpha+this.sinAlpha/this.cosAlpha));
        var x = (1/this.cosAlpha)*(screenX-z*this.sinAlpha);
        return [x, z];
};
isometricAS.prototype.setLeeWay = function(value) {
        this.leeway = value;
};
isometricAS.prototype.calculateDepth = function(x, y, z) {
        var x = Math.abs(x)*this.leeway;
        var y = Math.abs(y);
        var z = Math.abs(z)*this.leeway;
        var a = this.maxx;
        var b = this.maxz;
        var floor = a*(b-1)+x;
        var depth = a*(z-1)+x+floor*y;
        return depth;
};

---

And here is an AS 2.0 class:

Code:

---

class isometric {
        var maxx:Number, maxz:Number, theta:Number, alpha:Number, sinTheta:Number, cosTheta:Number, sinAlpha:Number, cosAlpha:Number;
        var leeway:Number;
        function isometric(x:Number, z:Number) {
                maxx = x;
                maxz = z;
                theta = 30;
                alpha = 45;
                theta *= Math.PI/180;
                alpha *= Math.PI/180;
                sinTheta = Math.sin(theta);
                cosTheta = Math.cos(theta);
                sinAlpha = Math.sin(alpha);
                cosAlpha = Math.cos(alpha);
                leeway = 5;
        }
        function mapToScreen(xpp:Number, ypp:Number, zpp:Number):Array {
                var yp:Number = ypp;
                var xp:Number = xpp*cosAlpha+zpp*sinAlpha;
                var zp:Number = zpp*cosAlpha-xpp*sinAlpha;
                var x:Number = xp;
                var y:Number = yp*cosTheta-zp*sinTheta;
                return [x, y];
        }
        function mapToIsoWorld(screenX:Number, screenY:Number):Array {
                var z:Number = (screenX/cosAlpha-screenY/(sinAlpha*sinTheta))*(1/(cosAlpha/sinAlpha+sinAlpha/cosAlpha));
                var x:Number = (1/cosAlpha)*(screenX-z*sinAlpha);
                return [x, z];
        }
        function setLeeway(value:Number) {
                leeway = value;
        }
        function calculateDepth(x:Number, y:Number, z:Number):Number {
                var x:Number = Math.abs(x)*leeway;
                var y:Number = Math.abs(y);
                var z:Number = Math.abs(z)*leeway;
                var a:Number = maxx;
                var b:Number = maxz;
                var floor:Number = a*(b-1)+x;
                var depth:Number = a*(z-1)+x+floor*y;
                return depth;
        }
}

---

Some interesting stuff;
http://www.geocities.com/~dr_ericlin.../indexgeo.html
check out the "Depths sorting in isometric tiles" section.

Ahhh excellent stuff you guys, I shall have a good old play when I get home later.

Thank you! :D

This is all very fancy and very complex.
You can actually use easy and simple way to calculate iso depth:

depth=x+y*width

where x and y are objects x/y coordinates on the screen (not in iso space) and width is some high enough number like 1000.

of course, you cant have 2 objects on exact same coordinates

tony, if you read the link posted above by Blink, you will see that that method has problems with overlaps.

Not really, iopred, I am familiar with ericlins works and all his examples use coordinates in ISO space (rows and columns).

If you read again what I said, you can see that I wasnt suggesting ISO space, I said screen coordinates. Beside, I have actually tested it before posting :)

I havent actually had much time to try these different methods (I only tried Ericlins quickly), so I cant rate them against each other but Tonypa's seems to work absolutely perfectly. I even tried quickly to expand it into 3 dimensions and it worked fine.

Code:

---

// _x - screen x
// _y - screen y
// z - iso z (axis running from the screens top to its bottom)
this.swapDepths(this._x+this.z*500+this._y*1000);

---

Im so surprised that something that simple actually works! I literally tried hundreds of simple numeric method like that ages ago, but I couldnt get any of them just right.

Thank you guys very much! :D

Tony, Im an avid user of that technique, I used it AAAGES ago in an example I made for these forums, but in certain situations in Iso, it fails to do its job properly.

Can you perhaps give an example of such situation?

Its a real old test of mine.. but it uses swapDepths(y*width+x);

Lots of errors near the edges of the high tiles.. and a noticable difference when you move down.

Not sure if anyone will read this but oh well here it goes:

Funny how this subject goes in spurts. Anyway, I am the developer for the as3isolib and have encountered a few problematic areas with my default layout algorithm for absolute positioning of isometric objects (much like Covenant, the thread's owner). For the most part, a flat map generates little or no errors, however any variable height terrain proves to be too much for the algorithm to handle.

I based my default algorithm on the Filmation algorithm. The problem is not necessarily the algorithm itself but rather the array sort on mechanism in AS3.

My problem is that if you rely on the low-level array.sortOn sort algorithm, not all of you objects necessarily get compared to one another. Implementing a manual sort would be performance prohibitive at best.

So I decide to go back and try a more brute force approach to this. Namely I re-tried Tonypa's sort method modified to AS3 and for 3 dimension with variable height terrain. Did not work in certain situations. Tonypa, if you are interested in seeing examples to maybe try to refine your algorithm, I would be happy to do so.

I also tried Jobe Makar's method outlined here and in his old game dev book. That did not work at all.

I have seen some interesting approaches to this: One is what I will call the tile-owner approach. Basically your depths are presorted by a terrain map. Since terrain never moves, its depth can be set ahead of time and sorted as such. Then for animated content, rather than treat each animated object as a sibling of the terrain objects, it gets passed amongst the terrain objects as a child. This is still not perfect as I have seen many examples of this not ordering correctly. This also requires that bigger-than-tile-size objects to be sliced up in most cases. I know for certain the OpenSpace Engine utilizes this technique and I think Dofus might use it as well. Any thoughts on this?

For now it seems that the perfect isometric depth sorting algorithm is still evading us. Well I wanted to throw this out here just to say my 2¢.

did you checked the last date this thread has been active? its been 2003 so many many many many years ago in the age of internet.

PHP Code:

---

array.sortOn("zDepth",Array.NUMERIC); 


---

or

PHP Code:

---

array.sortOn("zDepth",16); 


---

http://livedocs.adobe.com/flash/9.0/...=00005045.html

always worked for me

MasterX and I have been toying with real 3d iso- engine depth sortings but its still not perfect. I cant show my recent stuff but some of his can be seen here:
http://board.flashkit.com/board/showthread.php?t=787321
http://board.flashkit.com/board/showthread.php?t=786270
http://board.flashkit.com/board/showthread.php?t=787370

but aside from that often its quite difficult to determine the actual depth or order like here
http://board.flashkit.com/board/imag.../2006/09/1.jpg

Yeah I was aware of the original posting date. Fortunately isometric development is still in style for the Flash Player and as such, very little progress has been/can be made for improving the sorting algorithms.

At one time I had considered doing something with 3D in an isometric perspective. Regarding primitives, you break all complex objects down into their core constituents. So a box is comprised of 6 rectangles. Then you sort those core objects using a 3D sorting algorithm and assemble the scene based on their order.

The problem I ran into was getting all the interactive events to hook up properly.

Quote:

---

Originally Posted by as3isolib

Yeah I was aware of the original posting date. Fortunately isometric development is still in style for the Flash Player and as such, very little progress has been/can be made for improving the sorting algorithms.

At one time I had considered doing something with 3D in an isometric perspective. Regarding primitives, you break all complex objects down into their core constituents. So a box is comprised of 6 rectangles. Then you sort those core objects using a 3D sorting algorithm and assemble the scene based on their order.

The problem I ran into was getting all the interactive events to hook up properly.

---

I spent a lot of time last year trying to think up a good algorithm for isometric sorting. It's a bugger if what you want is a fully explorable world in all 3 directions. This is why tile-based isometric games are so popular... because you can ignore the z-sorting to a large degree; but I wanted to be able to jump, and climb, and go under things.

I put it away in November of last year, until this January when a recent project made it relevant again. I've since come up with what I think is a reliable, fast, and foolproof way of sorting in an isometric map. The only caveat is the overlap paradox, which is avoided in the level design phase by carefully placing blocks so that the paradox is not visible. All other sorting issues have been resolved in the algorithm.

You can check out a sample here:
http://www.fenstalker.com/content/isoworld

Your thoughts?

That looks great, fenstalker :)

yeah awesome fenstalker. cast shadows are fantastic.

Quote:

---

Originally Posted by fenstalker

I put it away in November of last year, until this January when a recent project made it relevant again. I've since come up with what I think is a reliable, fast, and foolproof way of sorting in an isometric map. The only caveat is the overlap paradox, which is avoided in the level design phase by carefully placing blocks so that the paradox is not visible. All other sorting issues have been resolved in the algorithm.

You can check out a sample here:
http://www.fenstalker.com/content/isoworld

Your thoughts?

---

fenstalker, your demo is impressive. I'm curious about the overlap paradox you mention... can you show an example?
Also, any chance that you can give some insight on the algorithm you use for sorting?
Thank you.

Quote:

---

Originally Posted by paolobax

fenstalker, your demo is impressive. I'm curious about the overlap paradox you mention... can you show an example?
Also, any chance that you can give some insight on the algorithm you use for sorting?
Thank you.

---

In isometric worlds, object ordering is relative rather than absolute. Because of this, it's possible to place 3 objects in such a way that A is behind B, B is behind C, and C is behind A.

Check out this image for a sample: http://code.google.com/p/as3isolib/w...b_tutorial_002

The sorting algorithm is just a 2d array of relational data, combined with a bubble sort based on that data to constantly output a master "order" of all visible objects. Unfortunately the code is being developed as proprietary software so I can't post it. :(

Thanks for the feedback!

Map the positions to their relevant 3D co-ordinates i.e. an [ x, y, z ] now create a point infront of the iso grid at where the viewer would be looking at it from. Now make a vector from the view point to the x, y, z co-ordinate of each tile and get the vectors length, last but not least, sort so that the longest vectors are placed first :D

RipX

P.S. for overlapping tiles, you'd have to mask them!

Quote:

---

Originally Posted by fenstalker

... Unfortunately the code is being developed as proprietary software so I can't post it. :(

Thanks for the feedback!

---

That is a big pity!

Is there anyone working on an open source iso engine that offers these capabilities?

I had another go with depth sorting of large multi-tile objects in isometric view:
http://www.tonypa.pri.ee/test/isotest.html
The yellow, green and red blocks are objects covering several tiles. Last part of the text in each tile is its depth (higher depth means closer to viewer or above another tile with lower depth). Objects of course need to be concave, you cant use something like T, L or U shapes but they can fill any number of tiles. Blue object is the "hero" moving around with mouse.

Example of moving blue "hero" smoothly around:
http://www.tonypa.pri.ee/test/isotest2.html
Click to get focus, arrow keys to move.

Example of 3 dimensions, blocks stacked on top of others. Hero can move higher when next block is higher by 1 step, it will also fall back down when no blocks are below it.
http://www.tonypa.pri.ee/test/isotest3.html
Click to get focus, arrow keys to move.

I read a book "ActionScript for Multiplayer Games and Virtual Worlds"
in that book (P214) provide a way to sort the iso ojbect
the code is like this way:

Code:

---

private function sortIsoObjects(_objs:Vector.<IIsoObject>) : void
{
    var list:Vector.<IIsoObject> = _objs.slice(0);
    _objs = new Vector.<IIsoObject>();
    for (var i:int = 0 ; i < list.length ; i++)
    {
        var newSortObject:IIsoObject = list[i];
        var added:Boolean = false;
        for (var j:int = 0 ; j < _objs.length ; j++)
        {
          var sortedObject:IIsoObject = _objs[j];
          if (newSortObject.col <= sortedObject.col+sortedObject.maxCols -1
                && newSortObject.row <= sortedObject.row + sortedObject.maxRows -1)
          {
                _objs.splice(j,0,newSortObject);
                added = true;
                break;
          }
        }
        if (!added)
        {
            _objs.push(newSortObject);
        }
    }
    for (var k:int = 0 ; k < _objs.length ; k++)
  {       
      isoObjectMangerContainer.addChildAt(_objs[k].container,k);
    }
}

---

the key code is :
if (newSortObject.col <= sortedObject.col+sortedObject.maxCols -1
&& newSortObject.row <= sortedObject.row + sortedObject.maxRows -1)

i also check the as3lib sort code.

the key code is like :

var rightA:Number = objA.x + objA.width;
var frontA:Number = objA.y + objA.length;
var topA:Number = objA.z + objA.height;

for (var j:uint = 0; j < max; ++j)
{
var objB:IsoDisplayObject = children[j];
if ((objB.x < rightA) &&
(objB.y < frontA) &&
(objB.z < topA) &&
(i !== j))
{
behind.push(objB);
}
...


i use first one in my code,
the spped test is

Child Number :100 Cost :7
Child Number :200 Cost :28
Child Number :300 Cost :60
Child Number :400 Cost :108
Child Number :500 Cost :167


as you can see , if the objs is under 100+ , the speed is acceptable.


is there have any fast way to do it.

and i also have a prb about
Is this have to render all objs if have one object moved?
or just find those objects beside , and only render those object inside?

here is new update:

for those day i try to use As3 own sort function. it's really really fast. but unfortunately, it's only work with single tile. means every object maxCol = maxRow = 1 otherwise it's not working.
so , i start to optimize current function.

1` not use get/set function just use public property
it really fast a little bit . you can try yourself.

2` not caulate the vetror.length evert time. just use one property to reocrd it.

here it's my optimize result

* Sort:
100 1
200 3~4
300 8~9
400 13~14
1600 180 ~ 188

the key code is :

Code:

---

private function sortAndDisplayIsoObject():void
{
        var isAdd:Boolean = false;
        var swapIsoObjectLength:int = swapIsoObjectList.length = 0;
        var i:int;
        var j:int;
        var newSortObject:IsoBox;
        var sortedObject:IsoBox;
        for(i = 0 ; i < isoObjectListLength ; i++)
        {
                newSortObject = isoObjectList[i];
                isAdd = false;
                for(j = 0 ; j < swapIsoObjectLength ; j++)
                {
                        sortedObject = swapIsoObjectList[j];
                        if (newSortObject.col <= sortedObject.col+sortedObject.maxCols -1
                                && newSortObject.row <= sortedObject.row + sortedObject.maxRows -1)
                        {
                                swapIsoObjectList.splice(j,0,newSortObject);
                                isAdd = true;
                                break;
                        }
                }
                if (!isAdd)
                {
                        swapIsoObjectList.push(newSortObject);
                }
                swapIsoObjectLength++;
        }
       
        for(i = 0 ; i < isoObjectListLength ; i++)
        {
                sortedObject = swapIsoObjectList[i];
                j = isoObjectMangerContainer.getChildIndex(sortedObject.container);
                if(i != j)
                {
                        isoObjectMangerContainer.addChildAt(sortedObject.container,i);
                }
        }
}

---

if you want see the all demo you need to check out my opensource engine http://code.google.com/p/copyengine/
but currently it's under developing , so the code maybe have mess up :)

by the way . i think use Alchemy to override this function will get mush more optimize .
but i'm good at it. so if some guy want do it ,or have fast way to sort objects.
please let me know .
it will mush helpful for me. thanks a lot.

My email is iamzealotwang at 126.com

I know this thread is quite old, but it helped my a lot last week, when I was changing the rendering of my TD game from 2d to isometric. There is not much info about isometric sorting on the web, and if so it is mostly about the more trivial cases with no fluently moving units. I documented my final implementation as well as the used resources here. Maybe someone else doing research on this topic might find it useful!

Thanks for the in-depth info on this board!