After watching episode 299 of Handmade Hero, I wanted to share with Casey and the Handmade Hero community a blog post that goes over the method I used for sorting in the game I'm currently working on:
http://andrewrussell.net/2016/06/...in-river-city-ransom-underground/
Thanks :)
Ep 299: How "River City Ransom: Underground" does sorting for 2.5D
Edited by
Andrew Russell
on
Ep 299: How "River City Ransom: Underground" does sorting for 2.5D
Edited by
Roderic Bos
on
What I was wondering why Casey is so hung up about the "rug" example spanning multiple tiles. He just created the snake that spans multiple tiles and is multiple entities.
If the rug is made up of multiple entities and each entity is Occupying a floor tile, but then the single rug entity can also have a Traversable point that a player/npc character can stand on then you just need to sort who stands on who.
That would be wrong if a player stands on a couch but the couch is facing away from the camara so the player should still be behind the back of the couch. Maybe then you could place the back of the couch at the lower most Y on the tile so it would sort first. And all sorting is then done in Y per tile.
As for particles/bullets and such that can then be done as Y sorting within a square right? Even if they are above but behind the player head sorting them behind the player would make sense, the player just doesn't occlude the particle then...
If the rug is made up of multiple entities and each entity is Occupying a floor tile, but then the single rug entity can also have a Traversable point that a player/npc character can stand on then you just need to sort who stands on who.
That would be wrong if a player stands on a couch but the couch is facing away from the camara so the player should still be behind the back of the couch. Maybe then you could place the back of the couch at the lower most Y on the tile so it would sort first. And all sorting is then done in Y per tile.
As for particles/bullets and such that can then be done as Y sorting within a square right? Even if they are above but behind the player head sorting them behind the player would make sense, the player just doesn't occlude the particle then...
Roman
9 posts
Been around ever since CPU's had 3 registers! (AtariXL800)
That is a long time to stay a kid.
Ep 299: How "River City Ransom: Underground" does sorting for 2.5D
Why not take into account the min/max range for each axis we sort by?
Use the collision volumes bounding box as your metric for comparison, and do an insert sort, or go wild with a tree.
But the bottom line is the closer an entity's min point (closest to the camera, or closest to the ground), the further it is in the rendering queue.
This should resolve most overlaps,
The only point this will fail is painter's, where entities intersect and stick out on both sides, in this specific case which will happen only to entities that do not obey full collision (i.e. sword), either have the "sword" entity always on top (add ordering priority to entities, and set it to a lower sorting priority), break the drawing into two parts along the intersecting plane, or just let it be as most likely it will be in a very small time frame to see. (or use short swords, lances are to heavy for any hero!)
Use the collision volumes bounding box as your metric for comparison, and do an insert sort, or go wild with a tree.
But the bottom line is the closer an entity's min point (closest to the camera, or closest to the ground), the further it is in the rendering queue.
This should resolve most overlaps,
The only point this will fail is painter's, where entities intersect and stick out on both sides, in this specific case which will happen only to entities that do not obey full collision (i.e. sword), either have the "sword" entity always on top (add ordering priority to entities, and set it to a lower sorting priority), break the drawing into two parts along the intersecting plane, or just let it be as most likely it will be in a very small time frame to see. (or use short swords, lances are to heavy for any hero!)
Casey Muratori
801 posts
/ 1 project
Casey Muratori is a programmer at Molly Rocket on the game 1935 and is the host of the educational programming series Handmade Hero.
Ep 299: How "River City Ransom: Underground" does sorting for 2.5D
No, as I showed on last night's stream, you can easily construct cases where the closest point on entity A is closer than on entity B, but B should still be drawn first. This is because it is only relevant which is closer _where they overlap_. So you must at least first consider the overlap region, and _then_ ask which one is closer for a ray which passes through that region!
- Casey
- Casey
Roman
9 posts
Been around ever since CPU's had 3 registers! (AtariXL800)
That is a long time to stay a kid.
Ep 299: How "River City Ransom: Underground" does sorting for 2.5D
Edited by
Roman
on
Reason: explanation
First apologies, I don't fully ask my questions as I mean them, so "full 3d sorting" is not sorting by the 3d point position, it's sorting by the entity's 3d volume, and that was explained.
As for 3d, as is done when all your data is lists of triangles, etc... and you have a z-buffer and drawing front to back.
This was my "if", if you had the data to consider every entity as a 3d with volume, how much work with it take? and once that work was done, can we take a step backwards to our current entity data and remove parts of the algorithm that are irrelevant?
So first, I'd love it if you went the z-buffer route, because I want to learn it :)
However as promised, I want to try and give the 'operator <' between entities for a total ordering solution.
Before I start, some things that must be known:
A. The camera is always perpendicular to the X axis.
B. The camera rotation range is always from parallel to the Z axis to parallel to the Y axis (see inage below).
C. No slopes, entities bounding boxes are axis aligned (and I hope I'm using the right working here).
So, for the ordering I'm using a tree, which is O(NlogN) as insertion goes, and it gives us the ability to compare each entity to all the others, without O(N^2).
Well, I'm going to put code where my mouth is.
Logically this solution is valid for any camera position from a top down view (on the Y) to a side view (on the Z),
Now if we use a tree, or any binary inserted list, we will have a total ordering solution that will be valid for any insert order.
The entity positioning I've used to test the ordering is here:
I've placed entities A-E, and the drawing order (back to front) is
1. A
2. D
3. B
4. E
5. C
I've based my logic on the fact that if we take the top right most point of any bounding box, and extend a virtual shadow down the Y and Z to infinity, any bounding box that falls into it is considered behind (as long as we keep the camera positioning rules).
This logic should work with slopes, but I did not test the code above, so no guarantees.
Bottom line, I think this is as near to an almost perfect ordering solution as we can get, without cheating.
And if we do need to cheat to get an optimal map, level generator should be able to create levels that would not break the sort logic.
Cheers,
Roman
As for 3d, as is done when all your data is lists of triangles, etc... and you have a z-buffer and drawing front to back.
This was my "if", if you had the data to consider every entity as a 3d with volume, how much work with it take? and once that work was done, can we take a step backwards to our current entity data and remove parts of the algorithm that are irrelevant?
So first, I'd love it if you went the z-buffer route, because I want to learn it :)
However as promised, I want to try and give the 'operator <' between entities for a total ordering solution.
Before I start, some things that must be known:
A. The camera is always perpendicular to the X axis.
B. The camera rotation range is always from parallel to the Z axis to parallel to the Y axis (see inage below).
C. No slopes, entities bounding boxes are axis aligned (and I hope I'm using the right working here).
So, for the ordering I'm using a tree, which is O(NlogN) as insertion goes, and it gives us the ability to compare each entity to all the others, without O(N^2).
Well, I'm going to put code where my mouth is.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | struct v3
{
float x,y,z;
}
struct cube
{
v3 top, bottom;
}
bool operator < (cube A, cube B)
{
// any entity that does not overlap on the Z, is behind if its max Z is less or equal to the min Z of the compared to entity
if (A.bottom.z <= B.top.z)
return true;
float diffZ = Max(A.top.z, B.top.z) - Min(A.bottom.z, B.bottom.z);
// an entity that overlaps on the Z, is behind if its topmost Y is equal or less than the compared to entity
if (0.0f >= diffZ)
return (A.top.y <= B.top.y);
return false;
}
|
Logically this solution is valid for any camera position from a top down view (on the Y) to a side view (on the Z),
Now if we use a tree, or any binary inserted list, we will have a total ordering solution that will be valid for any insert order.
The entity positioning I've used to test the ordering is here:
I've placed entities A-E, and the drawing order (back to front) is
1. A
2. D
3. B
4. E
5. C
I've based my logic on the fact that if we take the top right most point of any bounding box, and extend a virtual shadow down the Y and Z to infinity, any bounding box that falls into it is considered behind (as long as we keep the camera positioning rules).
This logic should work with slopes, but I did not test the code above, so no guarantees.
Bottom line, I think this is as near to an almost perfect ordering solution as we can get, without cheating.
And if we do need to cheat to get an optimal map, level generator should be able to create levels that would not break the sort logic.
Cheers,
Roman