22
\$\begingroup\$

In a normal top-down 2D game one could use the screen y axis to sort the images. In this example the trees are properly sorted but the isometric walls are not:

Example image: sorted by screen y

Wall 2 is one pixel below wall 1 therefore it is drawn after wall 1, and ends up on top.

If I sort by the isometric y axis the walls appear in the correct order but the trees do not:

Example image: sorted by isometric y

How do I do this correctly?

\$\endgroup\$
1
  • 3
    \$\begingroup\$ Sounds like you've hit the problems common in Painter's Algorithm. The "common" solution is to use z-buffer =). Some workarounds include using object center as sort key instead of some corner. \$\endgroup\$ Feb 8, 2011 at 14:42

9 Answers 9

14
\$\begingroup\$

Isometric games are functionally 3D, so internally, you should be storing the 3D coordinates for each entity in the game. The actual coordinates you pick are arbitrary, but let's say X and Y are the two on-the-ground axes, and Z is off the ground up into the air.

The renderer then needs to project that into 2D to draw stuff on screen. "Isometric" is one such projection. Projecting from 3D to 2D isometrically is pretty simple. Let's say that the X axis goes from top-left to bottom-right and down one pixel for each two horizontal pixels. Likewise, the Y axis goes from top-right to bottom-left. The Z axis goes straight up. To convert from 3D to 2D then is just:

function projectIso(x, y, z) {
    return {
        x: x - y,
        y: (x / 2) + (y / 2) - z
    };
}

Now to your original question, sorting. Now that we're working with our objects directly in 3D, sorting becomes much simpler. In our coordinate space here, the farthest sprite has the lowest x, y and z coordinates (i.e. all three axes point out from the screen). So you just sort them by the sum of those:

function nearness(obj) {
    return obj.x + obj.y + obj.z;
}

function closer(a, b) {
    if (nearness(a) > nearness(b)) {
        return "a";
    } else {
        return "b";
    }
}

To avoid re-sorting your entities every frame, use a pigeonhole sort, detailed here.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I know this is old, a good start but do you know how to might also incorporate the 3d bounds of a object not just simply its translation. When they're overlapping the depth sorting becomes more complicated. \$\endgroup\$
    – Rob
    Jul 1, 2014 at 15:22
4
\$\begingroup\$

Assuming that your sprites occupy sets of tiles that are rectangles (if they occupy arbitrary sets, then you cannot draw the correctly at all in the general case), the problem is that there is no total order relation between the elements, so you cannot sort them using a sort that would result in O(nlogn) comparisons.

Note that for any two objects A and B, either A should be drawn before B (A <- B), B should be drawn before A (B <- A) or they can be drawn in any order. They form a partial order. If you draw yourself a few examples with 3 overlapping objects, you may notice that the even though the 1st and the 3rd object may not overlap, thus not having a direct dependency, their drawing order depends on the 2nd object that's between them - depending how you place it, you will obtain different drawing orders. Bottomline - traditional sorts don't work here.

One solution is to use the comparison (mentioned by the Dani) and compare each object to each other object to determine their dependencies and form a dependency graph (which will be a DAG). Then do a topological sort on the graph to determine drawing order. If there aren't too many objects, this may be fast enough (it's O(n^2)).

Another solution is to use a (for balancing - pseudo) quad tree and store the rectangles of all objects into it.

Then iterate through all the objects X, and use the quad tree to check if there are any objects Y in the stripe above the object X which starts with the leftmost and ends with the rightmost corner of object X - for all such Y, Y <- X. Like this, you will still have to form a graph and sort topologically.

But you can avoid it. You use a list of objects Q, and a table of objects T. You iterate all the visible slots from smaller to bigger values on the x-axis (one row), going row by row on the y-axis. If there is a bottom corner of an object at that slot, do the procedure above to determine dependencies. If an object X depends on some other object Y that is partly above it (Y <- X), and every such Y is already in Q, add X to Q. If there is some Y which is not in Q, add X to T and denote that Y <- X. Every time you add an object to Q, you remove dependencies of objects pending in T. If all dependencies are removed, an object from T is moved to Q.

We are assuming that object sprites don't peek out of their slots on the bottom, the left or the right (only at the top, like trees in your picture). This should improve performance for a large number of objects. This approach will again be O(n^2), but only in the worst case which includes weird sized objects and/or weird configurations of objects. In most cases, it's O(n * logn * sqrt(n)). Knowing the height of your sprites can eliminate the sqrt(n), because you don't have to check the entire stripe above. Depending on the number of objects on the screen, you may try replacing the quad tree with an array indicating which slots are taken (makes sense if there are many objects).

Finally, feel free to inspect this source code for some ideas: https://github.com/axel22/sages/blob/master/src/gui/scala/name/brijest/sages/gui/Canvas.scala

\$\endgroup\$
3
\$\begingroup\$

I use a very simple formula that works well with my little isometric engine in OpenGL:

Each of you objects (trees, floor tiles, characters, ...) have a X and Y position on the screen. You need to enable DEPTH TESTING and find the good Z value for each values. You can simply to the following:

z = x + y + objectIndex

I use and different index for the floor and objects that will be above the floor (0 for the floor and 1 for all the objects that has a height). This should work just fine.

\$\endgroup\$
2
\$\begingroup\$

I don't think there is a mathematic solution. You probably don't have enough data in the 2D world your items are living in. If your walls were mirrored on X they would be in the "correct" order. Then again you might be able to do overlap testing with the bounding box of the image somehow, but this is an area I'm not familiar with.

You should probably sort by screen Y per-tile and say that anything more complicated is a "design problem". For example, if you're authoring the content, just tell your designers the sorting algorithm and to shove wall2 2 pixels up to fix the problem. That's how we had to fix it in the isometric game I worked on. This might include taking "long" items and breaking them up into tile-sized chunks.

If you are allowing users to edit the content, the completely safe thing to do is to make everything tile based and at most one tile large. That way you avoid the problem. You might be able to get by with making everything larger than a tile, but possibly only if it's square. I haven't played around with that.

\$\endgroup\$
2
\$\begingroup\$

Perfect isometric sorting is hard. But for a first approach, to properly sort your items, you should use a more complex comparision function with each overlaping object. This function must check this condition: An overlaping object "a" is behind of "b" if:

(a.posX + a.sizeX <= b.posX) or (a.posY + a.sizeY <= b.posY) or (a.posZ + a.sizeZ <= b.posZ)

Of course, this is a first idea for a naive isometric implementation. For a more complex scenario (if you want view rotation, per-pixel positions on z-axis, etc.) you'll need to check more conditions.

\$\endgroup\$
1
  • \$\begingroup\$ +1, if you have tiles with different widths/heights, look at the compare function in this answer. \$\endgroup\$
    – mucaho
    Jul 22, 2015 at 12:11
2
\$\begingroup\$

If you compare the y values at the same x position, it will work every time. So, do not compare center to center. Instead compare the center of one sprite with the same x position on the other sprite.

enter image description here

But, this requires some geometry data for each sprite. It could be as easy as two points from the left to right sides that describes the lower boundary for the sprite. Or, you could analyze the sprites image data and find the first pixel that is not transparent.

An easier approach is to divide all sprites into three groups: diagonal along x axis, diagonal along y axis and flat. If two object are both diagonal along the same axis, sort them based on the other axis.

\$\endgroup\$
2
\$\begingroup\$

Extensive answer with multiple solutions, pictures and all the math here:

https://stackoverflow.com/questions/892811/drawing-isometric-game-worlds

\$\endgroup\$
0
\$\begingroup\$

This is not really an answer, but just a commentary and an up-vote I would like to give to this axel22's answer here https://gamedev.stackexchange.com/a/8181/112940

I do not have enough reputation to up-vote nor comment other answers, but the second paragraph of his answer is probably the most important thing one should be aware of when trying to sort the entities in an isometric game without relying on "modern" 3D techniques like a Z-buffer.

In my engine I wanted to do things "old-school", pure 2D. And I spent a lot of time busting my brain trying to figure out why my call to "sort" (in my case it was c++ std::sort) was not working correctly on certain map configurations.

Only when I realized that this is a "partial-order" situation was that I was able to solve it.

So far all working solutions I have found on the web used some sort of topological sorting to deal with the problem correctly. Topological sorting seems to be the way to go.

\$\endgroup\$
-1
\$\begingroup\$

You need to assign unique ids to all objects of the same type. Then you sort all objects by their positions and draw groups of objects in order of their ids. So that object 1 in group A will never overdraw object 2 in group A etc.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .