Sign in to follow this  

Sorting Isometric Objects

This topic is 4034 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on a 3d isometric game in C++ and Direct3d and I just can't seem to figure out how to sort my isometric objects. For example: Using objects such as 1x1 Block or 2x1 block Photobucket - Video and Image Hosting Currently I have all of the objects in a std:list and I'm using sort() comparing their ZOrder variable. Currently 0,0 on the object would be the furthest south corner. This variable is made like this: ZOrder = PositionX-PositionY; And so far it seems to work perfectly fine as long as the objects are square (ie: 1x1 or 5x5) but when I make an object that is 1x2 tiles long my sorting function doesn't work very well. Any help is appreciated.

Share this post


Link to post
Share on other sites
In my own game I check for the lowest y value of the sprite (with the crates in your case that'd be somewhere near coords 16,0 (assuming 0,0 is the bottomleft)), if one is higher than the other I switch it.

That method has worked pretty well for me.

Share this post


Link to post
Share on other sites
Hmm well let me see if I can explain what I'm looking for.
3 seperate blocks
The picture above is 3 separate blocks colored red,green, and blue.
Using the formula: ZOrder = PositionX-PositionY; (which simply finds out which one is lower on the screen) you get something like this.
3 separate blocks
Now that works great for blocks that are only 1 unit long but what about blocks that are say 3 or 4 units long.
1x4 block and 1x1 blockPhotobucket - Video and Image Hosting

Now this is where it becomes a problem. These two blocks now have a zorder that is equal to eachother even though common sense tells us that the longer block should be in the back. Here is another example.

Photobucket - Video and Image HostingPhotobucket - Video and Image Hosting
The second image is how the game would draw it.

So I need a new formula that takes into account the length and or width of the box but I can't seem to put my finger on how that would even work.

Share this post


Link to post
Share on other sites
Avoid using larger objects. Break the large ones into single boxes, and repeat them as normal. Should get the same effect if they're made right. Might not be the answer you are looking for, and for some things might take a few special case issues to draw, but for most shouldn't work too badly.

Share this post


Link to post
Share on other sites
How about instead of just having one entry in your list for the row of green boxes, you have four entries - one for each tile occupied. Then sort the list as normal. Iterate through the list and once you have drawn an object, mark it so it doesn't get drawn again.

Share this post


Link to post
Share on other sites
Seems to me you can solve it by making sure the ones with lower x-values are always drawn before the ones with higher ones. So maybe ZOrder = PositionX * (height* of the map) - PositionY; ... or some such.

*height, like, as if it was a normal square-tiles-map; max y-value+1

Share this post


Link to post
Share on other sites
Well the only problem with that is the game is built in a 3d plane where there is no real limit to x,y,z and 0,0,0 is the middle of the screen.
Photobucket - Video and Image Hosting
The game uses only objects (no tiles) and as so I really need to make sure that my drawing order for the objects is spot on.

Confusing I know. The renderer converts those coordinates to d3dvectors.

0,0,0 on the object = D3DXVECTOR3(PositionX+PositionY, -PositionX/2+PositionY/2+PositionZ-Width/2, 0.0f );

Share this post


Link to post
Share on other sites
Ah. Yeah, need to sort some different way then, I suppse.

I have about one week of C++ experience. Not awfully familiar just that sorting function, but... From what I got from a little Google-search; the sort function compares objects using the less-than operator, right? So, the current less-than operator for them objects returns a.ZOrder < b.ZOrder or some such? If that isn't how things are done at all, then, uh, at least you know how I thought it was, so maybe the point comes across anyways :P

So:

bool operator<(const Somethingsomething& a, const Somethingsomething& b) {
if (a.PositionX != b.PositionX) return a.PositionX < b.PositionX;
return (a.PositionY > b.PositionY);
}

... so that the return-value is based on the x-coordinate, unless objects has the same x, then it's based on the y-value. I think I got the ><-things right :S

Share this post


Link to post
Share on other sites
Ok well I followed your idea and found out that for some reason you can't use more than one variable in a std:list's sorting function. Not sure why but it doesn't matter since I can just combine the to variables into one.

Figuring out the Zorder (not sure how to display code yet)
Quote:
for (std::list <_LObject*>::iterator j = Objects.begin(); j!=Objects.end();++j)
{
(*j)->ZOrder = 0;
for (std::list <_LObject*>::iterator i = Objects.begin(); i!=Objects.end();++i)
{
if ((*j)->PositionX > (*i)->PositionX || (*j)->PositionY < (*i)->PositionY)
(*j)->ZOrder++;

}
}

Sorting function looks like this
Quote:

if (o1->ZOrder < o2->ZOrder)
return true;

Seems to work great although the are a few instances in which the result seems random. I'm guessing that happens when object j has a larger X and object i has a larger Y. Still will need to do some more research.

Anyway I also need to figure out how to add a Z variable. An object that has a higher Z should be drawn last unless the other object is in front of it.
6 blocks

Share this post


Link to post
Share on other sites
Quote:
Ok well I followed your idea and found out that for some reason you can't use more than one variable in a std:list's sorting function. Not sure why but it doesn't matter since I can just combine the to variables into one.

That sounds quite odd. Tried some myself now, and pretty much managed to do what I suggested in my last post :|

And seems there's a [ source ]-tag.

bool sortingFunction(const _LObject& o1, const _LObject& o2) {
if (o1.PositionX != o2.PositionX) return o1.PositionX < o2.PositionX;
if (o1.PositionY != o2.PositionY) return o1.PositionY > o2.PositionY;
return o1.PositionZ < o2.PositionZ;
}


// sort with:
Objects.sort(sortingFunction);



I'm able to run that code 'tleast, and I'd imagine it would deal with X/Y/Z-values properly.


Also:
Quote:
if ((*j)->PositionX > (*i)->PositionX || (*j)->PositionY < (*i)->PositionY)
(*j)->ZOrder++;

That will in some cases increase ZOrder even tho j's X is lower than i's X (like you said, pretty much).

if ((*j)->PositionX != (*i)->PositionX) {
if (*j)->PositionX > (*i)->PositionX) (*j)->ZOrder++;
} else if ((*j)->Positiony != (*i)->PositionY) {
if (*j)->PositionY < (*i)->PositionY) (*j)->ZOrder++;
} else if (*j)->PositionZ > (*i)->PositionZ) (*j)->ZOrder++;



I'd much rather try'n get something like that sorting function above to work tho, and avoid all that extra iterating through the list in addition to whatever sort() does...

Share this post


Link to post
Share on other sites
Hmm well your function does compile which is great but for my game it basically is only comparing the X values when it needs to compare both the X and Y at the same time since an object that has a higher X value but might not be in front of the other object.

I'm not really sure how to explain it so I'll just link a quick build of my game. Right now I'm using graphics from Super Mario RPG but I'll be using my own later on.

Anyway, this build is using your code below to sort the objects.

bool sortingFunction(const _LObject& o1, const _LObject& o2) {
if (o1.PositionX != o2.PositionX) return o1.PositionX < o2.PositionX;
if (o1.PositionY != o2.PositionY) return o1.PositionY > o2.PositionY;
return o1.PositionZ < o2.PositionZ;
}


Run around all sides of the blocks (using the number pad to move, space bar to jump, and hold B to see the bounding boxes) and you should see what I mean.

Designed for WinXp and DirectX9+. Let me know if you get any errors to.

Game.zip

Share this post


Link to post
Share on other sites
Oh. Yep. That doesn't work at all :P

I suppose the problem with the sorting funcion is that the if-conditions in the sort function doesn't take the length/width of the objects into account. Those are hereby called LengthX and LengthY by me. So, maybe:
bool sortingFunction(const _LObject& o1, const _LObject& o2) {
if (o1.PositionX > o2.PositionX || o1.PositionX < o2.PositionX - o2.LengthX)
return o1.PositionX < o2.PositionX;
if (o1.PositionY < o2.PositionY || o1.PositionY > o2.PositionY + o2.LengthY)
return o1.PositionY > o2.PositionY;
return o1.PositionZ < o2.PositionZ;
}


That way the return-value should be based the Y-value if o1's X value is equal to any of the X-values covered by o2, which seems to be the problem with the row of boxes furthest down at the screen.

I can't quite make sense of what happens when walking behind the row of boxes to the right.

The only movement made by the Mario between those two pics is along the Y-axis, right? The Y-value of Mario shouldn't affect drawing order any unless the other object has the same X-value as him, and the Mario's X-value should be about 1 less than the object's in both pics. So, only reason why he's drawn in front of the boxes in one pic but not in the other is that "something's up with something" :|

Share this post


Link to post
Share on other sites
Wouldn't it be easier to sort them not by x and y (screen coordinates) but by map coordinates?

This way you would draw the lowest layer first(for the stacks of blocks)
Then for each layer you would draw the rows that are projected the furthest away first which means that you need to know for each block what squares on the map are covered by the block.

Does this make sense?
Cheers

Share this post


Link to post
Share on other sites



If you want to stack in the same tile you would add an additional calc to the sorting value (to use the height as a sub range for the calculated depth Z value -- which is based on the tile XY value).

Multiply the Z value by something like 100 (sufficient to cover the highest height of any stacked object in a tile) and add the stack height of the object (you might need to adjust by a constant if you allow negative heights ... so that you will get a range of 0..n).

Now you would sort as you did before and the lower objects (in the same tile) will be draw first and the one above will overlay correctly.

Share this post


Link to post
Share on other sites
Quote:
Original post by ernow
Wouldn't it be easier to sort them not by x and y (screen coordinates) but by map coordinates?


Actually that's exactly what we are trying to do. These coordinates put into the sort function are the map coordinates and not the final screen coordinates.

Maybe this will make things easier. Here is how you convert what you see into what the game sees.
Photobucket - Video and Image Hosting
Photobucket - Video and Image Hosting
The Grey arrow is where the camera is looking. The two black lines are of course the x and y axis.

Quote:
Original post by wodinoneeye
If you want to stack in the same tile you would add an additional calc to the sorting value (to use the height as a sub range for the calculated depth Z value -- which is based on the tile XY value).


Hmm that actually might work although it could cause issues with objects that are close to the screen and really tall getting overlapped with an object behind it that is just a little off the ground. Currently my object detection code will stop a character or object from falling below 0 on the Z axis so if I could figure out a way to do just add a "sub range" I wouldn't even hat to worry about negative Z numbers.


Quote:
Original post by Gnarf
I can't quite make sense of what happens when walking behind the row of boxes to the right.


Now this is just a guess but I'm guessing I sent you the wrong game.exe in that zip since I was completely and utterly incapable of replicating that result. I updated it and included a file called v1.txt in the zip. If you don't see that then I probably sent you the wrong version again.

game.zip

Adding the length and width as you said just seemed to make it worse. I included 2 versions in this zip.

//** Game0.exe uses **
if (o1->PositionX != o2->PositionX) return o1->PositionX < o2->PositionX;
if (o1->PositionY != o2->PositionY) return o1->PositionY > o2->PositionY;
return o1->PositionZ < o2->PositionZ;

//** Game1.exe uses **
if (o1->PositionX > o2->PositionX || o1->PositionX < o2->PositionX - o2->Width)
return o1->PositionX < o2->PositionX;

if (o1->PositionY < o2->PositionY || o1->PositionY > o2->PositionY + o2->Length)
return o1->PositionY > o2->PositionY;

return o1->PositionZ < o2->PositionZ;

Share this post


Link to post
Share on other sites
Couple'a things I didn't think of, as usual :)

So, uh, this one might be worth giving a shot:
if (o1->PositionX - o1->Width + 1 > o2->PositionX || o1->PositionX < o2->PositionX - o2->Width + 1)
return o1->PositionX < o2->PositionX;

if (o1->PositionY + o1->Width - 1 < o2->PositionY || o1->PositionY > o2->PositionY + o2->Length - 1)
return o1->PositionY > o2->PositionY;

return o1->PositionZ < o2->PositionZ;


Now the checks should be if the lowest X-value covered by o1 is larger than the highest X-value covered by o2, and vica versa.

Share this post


Link to post
Share on other sites
treat things as single tile blocks in a 2d space, and then sort all objects belonging to a a tile by lowest Z value.

Something that is in a row lower on the screen, but a higher Z value is ALWAYS going to be drawn over the higher rows, no matter what the Z value is.

Share this post


Link to post
Share on other sites
I understand why everyone keeps saying to treat everything as single blocks but I can't really do that. The main reason is that graphics would have to be split up into multiple pieces along with the fact that my current object detection code would probably crash if objects were split up to individual 1x1x1 blocks.I really do think that we can figure out a formula instead of using a workaround like that.

Anyway some more builds. I realize now that it would probably be better to draw out a little graph of the exact map instead of just giving the sort() function out. I changed the map around to cause a more complex sorting requirement. Images are a thumbnails(click to see full image). The draw order should be purple, green, blue, mario, then orange.

Photobucket - Video and Image Hosting
Photobucket - Video and Image Hosting

Now if needed I can change around the origin of the objects (represented by circles on the first image) or any other part of the code as long as I can still have objects of any size.

game.zip

This build using the most accurate formula I've seen so far.
if (o1->PositionX != o2->PositionX) return o1->PositionX < o2->PositionX;
if (o1->PositionY != o2->PositionY) return o1->PositionY > o2->PositionY;
return o1->PositionZ < o2->PositionZ;

Share this post


Link to post
Share on other sites
Quote:
Original post by Ntsc8


Quote:
Original post by wodinoneeye
If you want to stack in the same tile you would add an additional calc to the sorting value (to use the height as a sub range for the calculated depth Z value -- which is based on the tile XY value).


Hmm that actually might work although it could cause issues with objects that are close to the screen and really tall getting overlapped with an object behind it that is just a little off the ground. Currently my object detection code will stop a character or object from falling below 0 on the Z axis so if I could figure out a way to do just add a "sub range" I wouldn't even hat to worry about negative Z numbers.


*


This is assuming all objects occupy only 1 tile (thought they can have any height -- and that height is used to determine the position of objecte stacked above another......)

It should wirk fine, remember that in the equation the closer tiles will always have multiples of the maximum height range apart from the further tiles -- its like a magnitude. I gave 100 as an example so one row will have 100 difference between its sort value and the row behind it (and the row behind will still have a lower value even if somethin there is at height 99...)
That means that the forground tiles will ALWAYS be drawn last no matter how high the further back object is in its tile.


It works for flying too, but when something floats you ysually will bave an unclear tile position (unless you have some other indicator mechanism to show its true tile pos).

Share this post


Link to post
Share on other sites

This topic is 4034 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this