Procedural Chunk-Based Universe Part 10: Dijkstra Would Probably Hate Me for This

Background information on the title joke: Dijkstra was a mathematician who was pondering how to logically calculate the fastest way to traverse a city with a number of bridges separating parts of it, which led to him inventing the famous Dijkstra's Algorithm, which in turn is the foundation for cutting edge modern path-finding algorithms such as A* used in games and simulations today.

My last entry on this topic teased that I'd be linking my bridge generator to my procedural chunk system, but to do that, first I had to investigate how it would respond to the variety of situations it would be likely to encounter in a randomly generated environment. As often happens in software development, simply putting together a new test scene with what seemed like an equivalent situation - two movable end points, a bridge generator to connect them, and a selection of segment prefabs for said generator to use - revealed some bugs in the system, in this case a whole menagerie of them, such that it took a whole day's work and more to resolve them and adjust the code to reinforce it against similar issues in the future. I remember the wave of joy and relief I felt when I finally beheld a procedurally generated structure with closed loops in it, as I had sought for so long, even though it was very simple:

Eventually I had a more robust and polished version of both my "roguelike" random level generator and my bridge generator coexisting peacefully alongside a few helper scripts:

First the level generator runs for a few seconds, generating some randomized pathways. Initially this began at a single starting point, but in later tests I was able to have it start from multiple locations for a more varied final shape.

A helper script caps the end of each path with an intersection segment, with the intent of providing plenty of usable attachment points for bridges.

A helper script identifies the unoccupied attachment nodes on each of these junctions, then iterates through them, pairing each one with each of the others in sequence (as indicated here by the colored lines) and passing them to the bridge generator.

Whenever a bridge is successfully built between two nodes (as shown here via green highlights), that pair of nodes is removed from the list. Work continues until every node has been examined, then a helper script closes off any leftover unoccupied nodes with an end cap.

By having a few of the segment prefabs come with big gray boxes attached that, with randomized height offsets, vaguely resembled buildings, the system made for a surprisingly satisfying low-poly city generator.

The mini-map at top left shows the full road network from above.

Performance, however, was incredibly slow!

It turned out that determining whether a bridge was possible by actually attempting to build one, while the most direct and surefire way to know, was way, way too slow to be useful on a large scale. When working on my chunk system before, I spent a lot of time optimizing for efficiency so that the basic creation, arrangement, and updating of chunks would take as little computation time as possible so that any game using it would still run smoothly and have headroom for interesting level generation within these chunks (such as terrain). Imagine trying to play a version of Minecraft that needs a full second, or even a full tenth of a second, to generate every one of the hundreds of chunks that can appear on screen at once - not what people like calling a "playable" experience!

Well at this point the bridge generator needed a full frame to do every step of the construction process, meaning that a bridge that required twenty segments to construct would also require more than twenty frames - a third of a second at a typical 60 FPS. This would be the situation whether the bridge ended up failing (due to an obstacle or some problem with the spatial relationship of its end points) or not, so if there were even ten nodes to connect, and each one had to try to form a bridge to each of the other nine, it could require up to 55 attempts and thus easily take, if the bridges formed an average of twenty segments apiece, 1100 frames or over 18 seconds - and that's a pretty minimal scale. My test runs actually were a little more complex than this and took even longer, sometimes exceeding two or three full minutes. If every chunk ended up trying to do this and it thus took several minutes to generate a few dozen chunks of playable space, which would happen every time the player moved from one chunk into a neighboring chunk and thereby triggered a refresh operation, one can imagine how the result would feel completely unusable.

Fortunately I was able to speed this up by literal orders of magnitude with some basic optimizations, most significant of which were ways I found for the system to fail fast - if, for instance, two nodes were aimed away from each other, then it was already certain that the existing bridge generation code wouldn't be able to connect them, so I could check for that case between pairs of nodes and discard them without having to proceed with any of the other bridge generation code, even many times in a single frame. After a number of tweaks like this, a decent road network could be fully generated in about ten seconds or so. To optimize any further, I would probably have to start calculating the positions of all of the bridge segments before instantiating any of them, which would take a lot more math and debugging, so for the time being I've deemed this acceptable.

I'd have liked if this post could have covered more ground-breaking topics, but an interlude explaining how I got from where I was before to where I am now felt necessary. I'm currently working on getting the bridge generator to be able to use the random "doors" produced by the chunk system and thereby enable chunks to generate level geometry similar to what's shown above that smoothly connects to that of neighboring chunks. As usual, though, that's already giving me a host of new problems to tackle.