Isometric sprite sorting MADNESS

I don't know whats stage your at or platform requirements you have but the fool proof way is to find a 3d rendering engine or api and just put your sprites on billboards. Unless your aiming for a cell phone port I think you should consider this option.

Thanks for the suggestion. Actually, I have sort of done that in the past. I made an isometric engine in XNA that used orthographic projection and 3D objects. But right now I am trying to make a 2D isometric engine in Allegro, so, I don't think 3D hardware Z-buffering is an option.

From which point on the sprites are you calculating the distance? For example, if you're calculating all the distances from the the top left corner (which usually is the origin), a sprite that's taller than another sprite that is in the background might still be drawn first, because it's top left corner ends up being "above" the sprite in the background.

Usually, you want the calculate the distance from the "feet" (if that applies, or it's equivalent otherwise) of foreground sprites, and from the top of ground-tiles.

The sprites are all currently just boxes of the same size. The point (0,0,0) is the point closest to the viewer, in the center of the screen.



Calculating distance from the players "feet" doesn't seem to be helping the problem... I mean, wouldn't that mean that the player and the ground tile he is standing on are virtually in the "same position?"

What I found worked for me is sorting by the screen-Y-coordinate of the bottom of the sprite. Sprites that would be drawn lower on the screen would be drawn later, and cover the sprites that were drown earlier, which works for flat games.

But this will not work for a 3d environment as your picture.

I don't know how you sort your axis, lets say Z is up-down, X is left-right and Y is in-out.

Just off the top of my head (meaning I am probably wrong here) I would try sorting first by the Y coordinate. Sprites more into the screen should be drawn before sprites more out, no matter the X,Z coordinates. If two sprites have the same Y coordinate then you need to sort based on X,Z and here I would fall back to my screen-Y-coordinate of bottom of sprite, if something is drawn lower then it is drawn later.

Note bottom of sprite is usually the bottom of the image, but not always. For example for a flying bullet the bottom of the sprite can be some pixels lower (to represent the "air" between the bullet and the floor.

Well I thank you guys for trying to help, but it turns out I finally figured out an algorithm that is "good enough," at least for now. After days of mind-numbing trial-and error, I found a method that works. Here it is:



1.) Create a list of sprites, starting with any player/enemy sprites you may have, and ending with the sprites of the actual level. The sprites of the level should already be sorted; this is easy to do if you just iterate through the level array in backwards order. Ensuring that the list is created in this way will make the algorithm much more efficient later on (since we have to do a bubble sort).

2.) Sort the list using (x+z) as the key comparison value. You want to put the lowest values at the end of the list. I used a merge sort for this.

3.) Sort the list in the y direction. This sort must be a bubble sort because we need to compare the sprites with every other sprite they "move past" during the sorting algorithm. You should use the following expression as a condition for "swapping" two elements:

list->at(i-1).y + TILE_SIZE <= list->at(i).y



It's unfortunate that I had to use a bubble sort... hopefully I won't run into efficiency problems in the future. But that's the best algorithm I could come up with... and as far as I know, it's the only algorithm that I can see anywhere on the internet that offers relatively fool-proof isometric sprite sorting when the sprites can move in all 3 dimensions. I'm sure there is a better way, but I can't find one for the life of me, and honestly at this point I don't really care! :)


EDIT: Wow, this algorithm is actually really inefficient... possibly too inefficient for a game to run smoothly. I'll have to come back to it and update it somehow.

Maybe I can somehow "insert" the moving sprites where they need to go, and leave the already-sorted level sprites alone.

[Edited by - UltimateWalrus on August 6, 2008 3:53:41 PM]

Quote:

Original post by UltimateWalrus Well I thank you guys for trying to help, but it turns out I finally figured out an algorithm that is "good enough," at least for now. After days of mind-numbing trial-and error, I found a method that works. Here it is: 1.) Create a list of sprites, starting with any player/enemy sprites you may have, and ending with the sprites of the actual level. The sprites of the level should already be sorted; this is easy to do if you just iterate through the level array in backwards order. Ensuring that the list is created in this way will make the algorithm much more efficient later on (since we have to do a bubble sort). 2.) Sort the list using (x+z) as the key comparison value. You want to put the lowest values at the end of the list. I used a merge sort for this. 3.) Sort the list in the y direction. This sort must be a bubble sort because we need to compare the sprites with every other sprite they "move past" during the sorting algorithm. You should use the following expression as a condition for "swapping" two elements: list->at(i-1).y + TILE_SIZE <= list->at(i).y It's unfortunate that I had to use a bubble sort... hopefully I won't run into efficiency problems in the future. But that's the best algorithm I could come up with... and as far as I know, it's the only algorithm that I can see anywhere on the internet that offers relatively fool-proof isometric sprite sorting when the sprites can move in all 3 dimensions. I'm sure there is a better way, but I can't find one for the life of me, and honestly at this point I don't really care! :) EDIT: Wow, this algorithm is actually really inefficient... possibly too inefficient for a game to run smoothly. I'll have to come back to it and update it somehow. Maybe I can somehow "insert" the moving sprites where they need to go, and leave the already-sorted level sprites alone.

Bubble sort is one of the worst sorting algorithms possible. Try using an insertion sort, at least. Though it seems you have the sorting key figured out, so it should be trivial to use quicksort.

What you need isn't bubble sort; you need a stable sort, which bubble sort can be under certain circumstances. You could at the least try a stable merge sort.

Somewhat related: what I'm going to try for my current project (non-isometric, but still need to sort my sprites) is taking the map-y value (since it's 'top down') and sorting the sprites by the y-values into a linked list. Then, when a sprite is moved, its new position is compared to its "neighbours" in the list, and if it needs to be moved in the list, it is. If a new sprite is to be inserted into the map, the list is just traversed until appropriate to insert the new sprite.

The idea is to avoid constantly sorting the sprites unnecessarily, no matter how you calculate the z-value or what type of sorting algorithm you use initially. Not sure if it'll work, but I'll certainly give it a try, and I think it's something for you to consider as well if you're going to stick with 2D.