   Sorting Problems!?
  This is driving me crazy. I can't figure out how to sort my objects correctly, based on Y & Z. Z is front-back, Y is altitude. Z-positive is going towards the front, Y-positive is going into the sky. The game has a perspective such as ScreenX = X and ScreenY = (Z - Y) / 2.Here is a snapshot of my problem:Sorting ProblemI'm trying to sort my Z first, then Y if Z is overlapping. This doesn't work because (as in the image) objects can be completely behind each other and still need to be drawn on top. This is my callback routine for qsort():   // Sort By Z Positionsif(B->Pos.back >= A->Pos.front)return -1; // (A drawn first)if(A->Pos.back >= B->Pos.front)return 1; // (B drawn first)// Beyound this, objects are either inside, on top, or X-side-by-side with each other// Sort by Altitudeif(B->Pos.bottom >= A->Pos.top)return -1; // (A drawn first)if(A->Pos.bottom >= B->Pos.top)return 1; // (B drawn first)// Fail-Safe Z Sortreturn A->Pos.Zcenter - B->Pos.Zcenter;I also can't swap the coding order of Y & Z, because it's also totally possible for objects higher than others to be drawn behind them. Like I said, it's driving me nutts. If anyone can help, I would really appreciate it.Thanks in advance[edited by - Jiia on March 18, 2004 2:52:28 PM]
  Ah, GUI sorting.Myself I simply threw each new gui panel into a linked list and drew them in a single swoop.Because they are added dynamically (via linked list) you can be sure last in is active and should be foremost. That was by design.Therefore starting from the headnode and working to the tail node, render each panel and they are automagically in order ;] ;  What is the actual problem? I don''t seem to be able to work it out from the image and your explanation alone. Surely only the Z value is of importance when determining drawing order? Why would an image at the back need to be drawn on top?   [ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost  Asking Questions | Organising code files | My stuff | Tiny XML | STLPort] ;  EDIT: I uploaded another crappy image: hereI'm not sorting a GUI. The image shows some generic item box-looking images stacked on top of each other.Kylotan -> The image shows 4 boxes (a 5th one is half-way visible on the left, ignore it) stacked on top of each other. The very top box is behind the very bottom box on the Z axis, but it obviously needs drawn after it, because of the way they are stacked.I know I'm asking for a lot here, but if anyone can help, I would forever hold your name in greatness.I'm pretty sure I need to calculate a screen-Z based on world-Y AND World-Z. Is that right? This further causes me problems because I have to draw objects in order by tile-rows.Tiles are drawn from back to front, a row at a time. I loop through the sorted list of objects for each row, and draw only objects that are on-or-behind that row, in the sorted order. Once done with a row, I mark the last object drawn, and begin there on the next row. If objects which have lower Z values are placed ahead of objects that have higher Z values, I can't figure out when to stop drawing objects for a specific tile row.If I do manage to calculate a Screen-Z value for objects, could I possibly do the same with tiles, and use that instead? Be easy on me, as I've never encountered this problem before. The sort-by-world-z method has always worked until I decided to throw stacked objects in there.Thanks again   [edited by - Jiia on March 18, 2004 5:19:00 PM];  I Think you should always draw them from bottom up, and with the screen-z coordinatescreate a list of objects to draw (usually only the visible ones) and sort them according to their distance from the viewpoint ( sqrt((dx*dx)+(dz*dz)) good old z-buffer )They''re some pretty interesting sorting algorithms of the site of java.sun  --- At The Edge Of Time ;  What makes the difference if I draw bottom-up? Do you mean draw objects in order of their Y position? If I did that, Z would be taken completely out of the equation..?I''m not sure why you''re giving me a Z buffer that calculates using X. X should never be used to order my objects. This is a 2D game, with a pretend-perspective. It has 3 coordinates, but objects do not grow and shrink with distance from the screen.My Screen Z is simply (World Z - World Y). If you add to Z and subtract the same amount from Y, it looks as though the object does not move (except it''s shadow), because it''s going exactly towards the screen.However if I sort by this amount, the glitches are worse than before. Should the object origin be bottom-front? Top-front? Or do I need to do more calculations based on their Y size?For an example, a little guy is standing exactly behind a huge tall tree. He is of course behind the tree because their Y values are almost the same, and his Z is less than the tree. As soon as he jumps, his Y value begins to increase, and shortly after, he appears in front of the tree. This should not happen. The tree is extremely tall, and objects should only be put in front of it if their Y value is higher than Tree-Y + Tree-Height.Is this some hole with 2D pretend-perspective games? It doesn''t seem like I can have it both ways.Thanks again for any help ;  Forget the X  i was thinking of a 45deg projection ...the main idea was simply to calculate the distance of you object bettween the obj and the viewerthe fartest (?) object being drawn frist, it wont be a problem if some are close together or if the guy jump behind that tree.The distance to the guy is greater than the distance to the tree, so the tree will always be drawn before the guy even if the guy jumps ... and if you game draw everything the same way (like : looking bigger if the Y is higher and stuff) you dont have to care about the X nor the Y. --- At The Edge Of Time ;  You have a problem really. You have a Z-value for the front and back of an object but in reality every point on your sprite might have a different Z value if you want sort it properly. In your box example, Z values vary across every single face of those cubes. Or to word it another way, if one object partially obscures another, it's no good only having Z-values for the far side and the near side, as it's the value in between that is important.So you can't expect to model things correctly without doing per-pixel calculations. This type of projection doesn't lend itself to any simple solution.Most 2D games avoid this issue by keeping things inside a grid and thereby disallowing partial overlaps like the ones in your example. This unambiguously places every object either in front of or behind the other, allowing you to sort by closest first with altitude as the tiebreaker.   [ MSVC Fixes | STL Docs | SDL | Game AI | Sockets | C++ Faq Lite | Boost  Asking Questions | Organising code files | My stuff | Tiny XML | STLPort]   [edited by - Kylotan on March 23, 2004 5:48:00 PM];quote:Original post by Kylotan  You have a problem really.Thanks. That''s what I needed to hear. At least now I can try to come up with an alternate solution. The only reason Y would be important is if one object is over top another, right? My objects already keep a record of other objects over and under them for physics. So perhaps I can sort stacked object together as a single object, using the bottom object''s position, then draw them all from bottom to top.Thanks again. And sorry if I brought this thread way back from the dead. I was rummaging through my profile to see if any of my posts had been replied. 