Topological sorting optimization

I'm creating a 2d isometric game that uses topological sorting to correctly depth sort all of the oddly-shaped isometric objects. I spent a lot of time writing this from scratch, and it works great. However, it has to sort every object every frame since there are moving entities. Once I get a couple hundred objects in the list, it begins to lag significantly. I'm wondering, does anyone know a way to save on these computation costs?

My intuition is to sort immobile objects once, store this, and then only sort moving objects from then on. However, I fear that this may not be possible with something complex like a DAG.

Edit:

I used this video as a starting point, so it's a good example of what I'm sorting exactly.

• Why write it from scratch? Have you not tried it in a game engine, typically they have optimizations built-in and can help with stuff like this.
– Pow
Feb 12 at 10:54
• First, profile your code; there may be hotspots you can improve. Beyond that, can you edit to include an example of what you game is sorting? Most general topological sorts have linear growth; if it's possible to do better in your situation, it likely involves taking advantage of something specific to your problem. And showing the full problem might suggest better alternatives; maybe you don't need a full topological sort. Feb 12 at 14:07
• I edited to include the short video I used to provide a starting point here. I have profiled my code, and I'm certain that the creation of DAG and the sort itself are what bogs down the game with many items to sort. Feb 12 at 21:54
• @Pow Unity and Godot also do not have a built-in topological sort feature out of the box. I recommend researching the topic before commenting to avoid misleading readers. Feb 12 at 22:15
• @Pow that's understandable, but OP is already using an engine built for 2D and is asking about specific algorithm. Profiling revealed the sort is the bottleneck; implementing it another engine won't change that. Feb 13 at 16:37

The video you linked already shows the solution I would suggest: split large objects into a standard tile size. This increases the overall number of objects, but allows you to use more standard sort. That would make it easier to explore updating just the moving objects. Traditional sorts tend to have n*log n performance which can beat linear (n) performance under some circumstances. Performance is mostly dependent on a smaller n, but the nature of the data can also be a factor. Some sorts perform very well on data that's mostly sorted. If most of the objects aren't being moved, you could use the previously sorted data as starting point and update the moving objects.

If you want to stick with a topological search, there's been some research on dynamic topological sorts. I noticed that some of the work by David J. Pearce and Paul H.J. Kelly has been used in Tensor Flow and is open source, so that might be a good place to start.

I personally haven't seen it discussed much in the game development related research I follow and I wonder if the Computer Science Stack Exchange community might have better answers regarding topological search. There's also some topological sort question on Stack Overflow, so that might also be a consideration. If you do ask another site, please tailor your question to that community - asking the same question across multiple Stack exchange sites (also known as cross-posting) is generally not allowed & will typically result in having your question closed.

There's also been some research on GPU based topological sorting. D. Svantesson and M. Eklund found thier GPU implementation was only better for large, shallow graphs (pseudo code available). The other paper I looked at by Rahul Saxena, Monika Jain and D.P. Sharma also had some graph restrictions. As such, I'd try other solutions before exploring GPU implementations.

Lastly, consider if there's a game design or game mechanics solution instead of an algorithm solution. It's not uncommon for games to limit things (number of sprites, simultaneous sound effects, ...) based on engine or computational constraints. This could be a hard limit on the number of objects that can be spawned or using something like special foreground objects (clouds or foliage maybe) to quickly exclude some objects from the topological sort via a bounding box. We would need to know more about the specifics of your game to give specific applicable recommendations.

• Thank you for the info & sources on this! I was worried that I might have hit the limit on this particular algorithm, and that seems like it is the case. I think I will pursue some game mechanic solutions to see if I can get what I need. Otherwise, I'll just split up the objects. Feb 13 at 20:43
• @Andrachie You're welcome! Whatever you settle on, I encourage you to circle back & post a summary of your solution - I think we would benefit from a real world solution. Good luck with your game! Feb 13 at 21:27

For anyone who is coming back to this thread in the future, here is my solution:

While topological sorting does seem to be less hands-on after the initial set up, the computation cost didn't seem to be worth it. Especially when adding a lot of instances that move, running the computation every frame is slow.

So, I decided to use the tried and true method of sorting by y-coordinate and breaking up any non-square objects into tile-sized chunks and sorting respectively. Since I already have width and length defined, it's easy to tell which objects are non-square. However, to avoid manually breaking up every sprite by hand, I had to write some code that does this automatically during runtime.

In Gamemaker, there's a draw function (draw_sprite_part) that draws only a part of the sprite. With this function, I can break non-square objects into multiple chunks, separate those chunks into different objects, and draw only that chunk.

In the end, this solution is faster and easier than topological sorting in my case. It probably has less graphical glitches too. Thanks everyone for your help!