# complex Z-sorting

## Recommended Posts

Hello, I've got a little (or perhaps big) problem with my Z-sorting. My levels are now not flat anymore, they have multiple heights and you are theoretically able to stand onto every tile / block. That means Z-sorting is no longer just from back to forth, but also from bottom to top. Now for the level itself it's not a problem really, because every tile has its place in a grid. But if a moving object moves from one tile to another, its feet "sink" inside the tile that's nearer to the front. Of course in a flat level, you could get it right by just drawing the floor at first, and then draw all the other objects that stand on it, and it's done. Now this is not possible anymore, because everything can be "floor" in some way, as any object can stand on another object. At first I thought it would work with doubling the value of the Z-POSITION of the objects when calculating their Z-SORT-value. And it really worked for most cases. But then there was another display error: Imagine three tiles in a row. Now the one in the middle is significantly higher than the others (physically; not PLACED higher!). Now when the player is standing on the tile that is in the back the most, it should be overlapped by the middle tile. But now the player overlapped it! So no matter which way I choose, I always get graphical errors. Is there anything I can do? Has someone solved this problem before? Thanks for your help

##### Share on other sites
www.dr-wuro.de/games/shot1.gif

Here's an example shot (sorry it's without people). If I multiplicate the Z-Position of every object with 2, my dudes will be perfectly displayed, except if they are between those high walls (there are two of them). When my dude stands between those and walks to the more left wall, he doesn't get overlapped by the wall.

In the other case, as I said, it works correctly but every dude sinks inside the tile he is standing on.

At the moment I'm calculating the Z-value like this:

float zResolution = (1.0 / (App::getInstance()->getScreenHeight() * 2));float z = (drawPos.y + mapPos.z * 2 + entity->getZPos(currentTime) * 2) * zResolution;

First I calculate the Resolution, so my end-result will be a number between 0 and 1. That's important because I'm using the hardware-Z-buffer.

EDIT: drawPos is the actual position where the tile gets drawed, so it's already transformed for "isometric correctness" ;)
EDIT 2: Actually it's the bottom y point of the sprite, the height of the sprite gets subtracted when it's actually drawed!

[Edited by - ZeHa on September 28, 2006 6:57:12 AM]

##### Share on other sites
Well I actually came to a solution by myself, but I'm not able to implement it until Tuesday probably.

If someone is interested though, I'll explain it here in full detail.

Now for a somehow "quick" description:

My way of calculating the Z-value was good for the "flat" landscape I had before, but now that I have a 3dimensional one, I have to calculate it some other way.
The basic idea is to give every pixel, that represents a possible Z-value (on the screen it's vertically), a wider range in resolution of the Z-values. So that the landscape in the end is built up from back to forth, but every step of that also from the bottom to the top.

Unfortunately the float resolution is limited to 23 Bit, which means that in my case, a level with 256x256 tiles can only store up to 20 height blocks. If I manage to use the sign-bit, I can double that value. Another possibility would be to divide the height positions by 2, which could result in minimal graphical errors but I'll try that, it shouldn't be noticed. Of course another way would be to make the tiles smaller, but I don't want to do that because there are some graphics finished by now and I wouldn't make them smaller.

Perhaps you noticed I'll calculate an ABSOLUTE z-value. My previous way was to make it depending on which part of the level is displayed. Perhaps I can find a way to do that with the new system, too (has anybody got a good idea how to calculate them in that case?)

##### Share on other sites
Why all the complexity? Step back and simplify it.

Set z sort based on height only.

Now just...

for(z=0; z<zMax; z++)
for(y=0; y<yMax; y++)
for(x=0; x<xMax; x++)
draw(tile[x][y][z]);

Works for me.

##### Share on other sites
If there are only tiles on fixed positions, that's no problem of course.

But if a character can move freely without always taking a full step to the next tile, it becomes a lot more complicated. And even more complicated, if he can jump and also have every imaginable height position...

##### Share on other sites
If you had a screenshot or two where I could visualize it better... my gears my start turning and after the cobwebs clear out, I might can help you come up with a solution.

Though I do have an excellent idea...

This is super pesudocode, but the concept will probably work.

DrawPos {
Point screenPos;
int z;
Tile *tile;
}

void addToDrawList(int mapX, int mapY, int mapZ) {
//Create a new DrawPos, calculate your screen Position and set screenPos.
//Just as if you were going to draw to screen right now.
//After you store your screen coords... store the original Z value as well
}

DrawPos drawList[numTiles]; //depending on your language you could probably use a dynamic collection type if you don't know how many tiles will need to be drawn.

foreach z{ foreach y{ foreach x{ addToDrawList(x,y,z); } } }

Now... sort drawList by the x,y draw order. Sort any overlaps by Z.

Draw things in the draw list in the order they appear.

Would that work? It might need some fine tuning.

##### Share on other sites
Well I made a little sketch:

www.dr-wuro.de/games/iso.bmp

Look at the red line. That would be the basic drawing order if the map was completely 2-dimensional. There are some little red lines up there, which is drawn there to indicate how big your resolution should be. Because a person doesn't need to stand exactly on a tile, he can stand on two or more tiles at once. So the resulution is not just the x- and y-indexes of the tiles.

Now there's a yellow sphere, which is located behind a wall. But it is very high compared to the ground. Now if there is another object UNDER the sphere, the sphere must be drawn AFTER the other object. But BEFORE the wall. So instead of just using the resolution for 2d-maps, I have to give EVERY position in that resolution a SECOND resolution for the height. This would mean, in the end, that the values of the little red lines is not +1 but +1000 if I would like to be able to have 1000 height differences in my level. With a block height of 40, I would be able to e.g. stack 25 boxes on top of each other.

So the calculation is basically adding x to y, dividing it so that the value fits to the 2d-resolution of the map, multiplicating it with (e.g.) 1000 and then adding z.

That's my current approach and it is working at the moment, except for a small graphics bug. My persons always sink into the ground when they are walking across the tiles. This could mean that I have to give the z-position more weight or something...

##### Share on other sites
Hmm... my spidey-sense is telling me that there must be a correct, analytical solution to this problem as long as you can guarantee you don't have inter-penetrating objects (because you have no zbuffer, you have to have an algorithm along the lines of the painter's algorithm).

Of course, my gut instinct is to dispense with all the cleverness of working in isometric/2D space and treat the problem like it really is, a 3D sort. The fact that your visuals are camera-facing sprites instead of polygonal meshes shouldn't play a part.

In that case, you'd define a true floating-point 3D space (or fixed-point if your domain is well-enough defined and discrete) where you store the world-space positions of all of your tiles, objects, etc. You then transform the world-space coordinates into the correct isometric frame (which since its parallel projected and fixed should algebraicly simplify down to a trivial equation) and sort the objects using a 3D painter's algorithm. This gives you the sort order for your rendering.

Of course, this is likely to be overkill if you do it brute force. You'll most certainly want to factor out the facts that the camera orientation doesn't change, only its translation relative to the viewing plane, and the fact that a great many of your objects are static (like the environment tiles). You should be able to get to the point of having to only re-calculate "depths" for moving objects, and then its just a matter of adjusting their order in the master list using a quick incremental sort (something tuned for nearly-sorted lists; bubble sort should actually be fine).

I don't know how this fits with your numeric limitations as I couldn't quite follow what you described in the earlier post, but you mentioned floats and 23-bits, which you should be plenty of resolution (8 million distinct depths!) for anything remotely resembling a traditional isometric environment.

##### Share on other sites
I'm with Simagery on this.

Treat them as if they were 3d objects and sort them the same.

As far as your character sinking into the ground is concerned, I don't really know without looking at some code. Are you testing collision against teh ground? Or do you just 'know' where it is? If you're testing collision... maybe your gravity is high enough that the character is jumping over your bounds?

## Create an account

Register a new account

• ## Partner Spotlight

• ### Forum Statistics

• Total Topics
627657
• Total Posts
2978471

• 10
• 12
• 22
• 13
• 33