I really love Casey Muratori’s Handmade Hero series. It is exactly the resource that I wish I had when I was growing up and learning how to program. I, unfortunately, don’t have time to watch every stream (being busy working on RCRU). But the latest episode (299), about graphics sorting, piqued my interest.

To summarise the video (it is an hour long), the gist of it is that Casey struggles to come up with a way to sort 2D sprites in 3D space. I spent most of the video shouting at my monitor, because this is exactly the problem that I struggled with – and solved – on River City Ransom: Underground.

Sorting Example

I want to share an overview of that solution with Casey and the Handmade Hero viewers, as well as River City fans:

~

Before solving this problem, there is an important decision to make: Do you want to split up interpenetrating sprites?

If you do, then this is not the blog post for you. The approach you’d probably take is something along the lines of Z-buffering (to do it per-pixel). We could have done this on RCRU. We have the depth information. We have the 1-bit transparent pixel-art. We have the technology.

However, there is an important aesthetic reason that we don’t: Splitting sprites looks bad. Consider this example:

Alex Car

Here Alex is sorting in-front of the car. In 3D space his hand is interpenetrating the car. The collision boundary for players is smaller than they appear graphically – something that is also necessary for good graphics and good gameplay.

Alex Car Bounds

If we rendered the actual game world using voxels (which is actually how we get the above view from our debug tools) then Alex’s hand would disappear inside the front of the car. And nobody wants to see that!

~

Once that decision has been made, sorting can be broken down into two distinct parts: How to determine the ordering between just two objects; and how to determine the ordering of an entire scene.

~

The first part is somewhat game-specific. In our case, we start by attempting to sort by bounding-box on the Y and Z axes. If one object is clearly above or in-front of another object, then the ordering is obvious.

If the bounding boxes interpenetrate, then we have to look at the 3D data for the object itself (this is the game-specific part). Basically: we could do something like a Z-buffer where we look at which object has the most “in front” pixels in a 2D area. But that would be very expensive.

To avoid the 2D calculation, we take advantage of the fact that our solid objects are represented as heightmaps. We basically look at our heightmaps side-on to pre-compute “depth slices” that bound the heightmap at that Y position. Because a heightmap cannot have overhangs, we know that any given slice will fully-contain the slices above it.

Depth Bounds

To compare the depth of two objects, we simply select the slice on each object that is at the lowest Y coordinate that the two objects have in common. We can then do a 1D depth comparison for that slice, with special consideration for being above part of the object.

(The green/red lines surrounding objects, in the above image, are the slices at Y=0 for that object.)

While this does not produce the exact result that a 2D test would, it is close-enough. In fact, it is actually better because it reduces the possibility of objects flickering as they move – especially on the Y axis.

Now we want to sort an entire scene…

~

Once we have a way to determine the ordering between any pair of objects, we can construct a directed graph. That is: a set of vertices (one for each object), connected by edges, where each edge points in a direction that gives the draw order for the two objects it connects.

Sort Arrows

(Here comes some graph theory. I highly recommend learning at least the basics, because it comes up over and over again in game development.)

The first thing to recognise about this graph is that it is not a complete graph. We don’t want to calculate the sort direction for two objects that don’t overlap. Aside from the fact that this could be a relatively expensive operation, every edge in the graph is essentially a constraint that has to be solved for (and – as will become apparent – the fewer the better).

(Aside: in RCRU, we check overlap with a per-animation bounds, rather than per-frame, to reduce the risk of depth flickering, especially for looped animations.)

Because it is not a complete graph, this precludes the use of standard sorting algorithms (examples: insertion sort, bubble sort, merge sort). Instead we need to use a topological sort (example: depth-first sort).

The second thing to recognise about this graph is that it is not necessarily an acyclic graph! It can contain strongly connected components (SCC; effectively: cycles). This precludes any kind of sorting at all! This is basically the “painter’s dilemma”.

So the first step to writing a good 2.5D sorting algorithm is to admit that you have a problem.

How do we solve this problem? For RCRU, we simply identify edges that are contributing to any strongly connected components, and try to automatically delete as few as possible to remove that SCC. Basically: try to get the best sort possible, under the circumstances.

Graph Test

This is actually really difficult to cause, in practice, in the game. So the above is a screenshot from my algorithm testbed, showing two resolved SCCs. I suspect that the reason that it is so difficult to cause this issue in-game is a combination of having relatively blocky and sensibly-shaped objects that don’t rotate, and having good collision-detection that uses the same data as the ordering function described earlier – thus preventing interpenetration.

The algorithm that we use to do this is a modified version of Tarjan’s Algorithm.

Tarjan’s Algorithm is an efficient way to find all the strongly connected components in a graph, with the added bonus that it also produces a topological sort. Once a SCC is found, we can then try to delete edges until that component is no longer strongly connected. The component can then be sorted independently, as it does not affect the ordering of the surrounding graph.

We do some simple things to try to pick edges to remove that will have the least visual impact. But because it is such a rare occurrence, we have not had to spend too much time on this.

Sorting Example Arrows

~

So, Casey, I hope you at least found that interesting, and maybe it might inform what you do next on Handmade Hero.

PS: I’m really looking forward to the next season of The Jeff and Casey Show!

~

Update: This blog post was featured on Handmade Hero episode 300:

Just to respond to a few things Casey said in the video:

  • First pronunciation of my name is the correct one (‘us’, not ‘oo’)
  • River City Ransom: Underground is a licenced reboot of / sequel to River City Ransom (originally on the NES). The original was by Technōs, who also did… Double Dragon 😀 (Retro City Rampage is an unrelated game with a cheekily similar name.)
  • There are a few places in RCRU where we do explicitly set the sort order of a pair. Most notably when characters pick up objects (order: character, object, hand) and when some grapple animations require a particular order (but the characters are on the same integer Z). We try not to over-use this, because it is a good way to create SCCs if we force a sort that is not physically plausible.

I’m really chuffed to have my blog appear on Handmade Hero. Thanks Casey! Looking forward to see where you go with it.

~

Update 2: There is now a video version of this blog post, and an entire series of videos on River City Ransom: Underground technical features. It’s called “River City Ransom: Underground: Underground“.

Comments

My name

2:14 pm, Saturday 18 June 2016

neat

Josh

8:25 am, Thursday 23 June 2016

Great post! I was wondering, though, what tool you used for the algorithm visualization?

Andrew Russell

2:25 pm, Thursday 23 June 2016

Josh: Custom programmed (on top of XNA)

Beej

3:58 am, Saturday 30 July 2016

Fantastic Write up… btw… River City Ransom, one of my fav games as a kid. So happy to have discovered this.