Procedural Chunk-Based Universe Part 11: Stairs!

From "Avengers: Endgame" - The Incredible Hulk is irritated at having to use the stairs in a tall building because he is too heavy for the elevator.

As of my last entry, the bridge generator was working fairly reliably under favorable conditions, i.e.

• The attachment nodes marking its ends must point roughly toward one another, as opposed to away from each other or one pointing toward the other while the other points away.
• The attachment nodes must exist in the same horizontal plane - there can be no "elevation" between them, save for a small amount specified by a "linear tolerance" variable.
• The attachment nodes are assumed to both have their local "up" directions be vertical, i.e. equivalent to the global Y axis. Deviation from this state leads to increasingly unpredictable behavior and usually causes the bridge to fail to generate.

This is nice and all for a flat, two-dimensional road network as seen in the previous entry, but virtual worlds tend to be more interesting when the terrain has vertical depth. Perhaps there is a building atop a hill and I want a road that leads to it from the bottom of the hill, or there is a sidewalk leading to a basement or second-floor doorway and I want it to have a staircase to address the vertical displacement. Also I may want the option of building tilted bridges that aren't aligned with the global horizontal plane and vertical axis for whatever reason.

Thus, with the basic system hammered out and made vaguely dependable, my next task was to improve its capabilities, starting with the ability to work at any arbitrary orientation. It took, unsurprisingly, a bit more work than I had hoped or expected, but wasn't terribly difficult, and along the way it afforded me opportunities to examine the logic and make adjustments in anticipation of future changes (such as how to position the "elbow" of the bridge when there is a vertical displacement, explained further below). Soon I had a bridge that worked normally at a nice wonky angle, as long as the end nodes' local "up" directions were parallel (within an "angular tolerance") and there wasn't much "vertical" displacement along this shared direction.

Next I had to focus on changes to accommodate the likely case that there was in fact a significant vertical displacement. I figured that the best place to put stairs should always be within whichever straight "leg" of the bridge is longer, so I figured out a strategy for identifying this leg (using more trigonometry), then I drafted a bit of code to incrementally eliminate vertical displacement. Along the way I took some time to refactor the existing code to remove duplicate code (for the first time having fun using local functions).

Since at this point vertical displacement was eliminated simply by offsetting straight horizontal segments, the bridge had unsightly gaps rather than proper stairs, so naturally building some staircase prefabs and incorporating them into the algorithm was my next task. I had previously designed my telescoping prefab code to be useful for staircases via having "primary" and "secondary" extension axes - a prefab could extend to eliminate an offset along its primary axis, but in so doing it would extend along its secondary axis as well. For instance a staircase could adjust its height to reach a platform, but it would also extend forward and thereby maintain its slope. For the time being, though, I simplified the problem by making staircase prefabs with only a single step that only extended vertically.

 

At this point the steps of the algorithm are roughly as follows:

1. Determine whether a bridge can be formed, and if so, store information about its geometry in a container class.
2. Identify which end of the bridge is oriented at a greater angle to a straight line connecting the two ends and begin construction at this end.
3. Chain flexible prefabs together to eliminate half of the angle between the two ends.
4. Duplicate this first chain and align it with the "elbow" position defined within the bridge's geometry data.
5. Fill the gap between the first chain and the elbow chain using straight prefabs and stair prefabs if necessary.
6. Fill the gap between the elbow chain and the final end of the bridge.

Steps 5 and 6 are done using a local function that accommodates vertical displacement between the starting and ending positions of the gap:

1. If there is any vertical displacement, stack staircase prefabs until the vertical displacement is eliminated.
2. Stack straight prefabs to eliminate the remaining horizontal distance.

The elbow is always positioned such that the longer leg of the bridge will include all of the vertical displacement, meaning that only the gap within the longer leg will contain stairs.

For the moment, "fixed" straight segments are available and can be used to fill most of the gap before using a final telescoping segment at the end, but there is not yet any such dichotomy of fixed and adjustable stair segments, which I intend to implement later. As it stands for now, the bridge generator now has the capability to connect attachment nodes at a much wider variety of positions and orientations in 3D space, which should make it much more effective in conjunction with procedural level generators I create in the future and with my chunk system. Unfortunately, I'm not completely out of the woods yet...

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.

Can You Paint with All the Colors of the Cyber-Wind?

I've been hard at work (yes it's still called work even if you think it's fun. Don't let anyone convince you otherwise) on ShipBasher and my untitled procedural generation project, but today I want to digress a bit and blather on with opinions I have on the cyberpunk genre, as a bit of a follow up to my post from a while back about BLAME! (or perhaps more accurately a tangent from it).

It'd be weird if today, in 2021, I didn't mention the recently published game Cyberpunk 2077, so I'll get that out of the way first. As far as my cursory research indicates, its name is due to it being an adaptation of a pre-existing and much older tabletop RPG system known simply as "Cyberpunk" - so if, like myself, any of you are mildly irked that the name of the genre itself was co-opted for a single commercial product, I suppose it's only proper to consider the developers of said tabletop system the true guilty party. Of course most of you I imagine see the name issue as insignificant, particularly as overshadowed by the franchise's more general effects on the genre and its associated fandom.

Lest I sound negative and bitter, I first want to give credit for the positive impacts I believe it had. First and greatest, it got a lot of people - a lot of gamers, at least - using the word and thus talking about the genre. More visibility usually means more fans, and more fans are necessary to keep the fandom alive. Second, I think it illustrated, and reminded the industry at large, that the ancient truth still stands today - a product can be profitable whether it's singleplayer, DRM-free, single-purchase, or whatever, if it's made with love. Maybe that sounds empty and wishy-washy but hang on a moment - I think it's fair to say that consumers can tell when creators put love into their work, and as a result they enjoy it and thus it sells. It wasn't the publishers, of course; it was the developers. In interviews and social media they consistently brought up hardships but rarely if ever claimed to dislike the game itself or cite wanting to work on some other project as one of their sources of grief, and their positive statements were commonly centered on the game itself and where along the way they felt pride. And yes, perhaps something made by experts in profitability but devoid of passion or soul can outsell it, but it doesn't change the fact, established afresh, that something done with loving care can be successful even in an environment saturated with hollow titles the way the modern game development industry is.

Where the thing fell flat was in the way it portrayed what, specifically, the creators loved within the cyberpunk genre. Whatever it actually was, the game made it seem as though it was the look and none of the deeper themes or messages. In fact it did so well as a result of said love for the look that I suspect it drew in a lot of fans who were unaware there even were any deeper themes or messages, which would be sad because they do exist and are both beautiful and important. That's universal within the cyberpunk genre as I see it, but exactly what those themes and messages are is what I want to examine today. I don't want to make this post about Cyberpunk 2077 any more than it needs to be (it's already taken over enough of the industry, right?), so I'll try to avoid bringing up which things it tragically missed or handled poorly in favor of just pointing out what's there and leaving it to the reader to notice the gaps.

For some time now the term "cyberpunk" to me has actually meant a collection of at least three related but not quite equivalent genres, each of which carries its own general set of philosophical ideas (though there is significant overlap) and vague color scheme; thus I refer to them by colors, hence the title of this article. I'll dive into each in turn, but to give a primer, the colors are as follows:

Pink Cyberpunk: Cyberpunk 2077's sub-genre, so named for featuring distinctive pink colors that the others don't. This appears in neon signage, gaming PC case lighting, and car decorations for example. Not everything is pink and other colors (such as yellow) may predominate, but there's certainly more pink here than in any of the below sub-genres.

Green Cyberpunk: The Matrix's sub-genre, so named for its characteristic green tinge. "Matrix code" is the most obvious example, but others exist including the back lighting of retro-style computer displays and often even the tint of metals and entire environments depicted in this sub-genre's media.

Brown Cyberpunk: The best example in my mind of this is Battle Angel Alita - the manga and OVA, not the live-action movie (not that I disliked it). Brown and tan are commonly seen in rust, sand, engines, armor, and metallic surfaces in general.

Gray Cyberpunk: Manga artist Tsutomu Nihei is a master of this sub-genre. Color is minimal, giving way to concrete, harsh white lights and black shadows, and gray metal. I think this is my personal favorite sub-genre.

I foolishly thought I'd cover all of these in one post - and maybe I could have - but I'm tired now and splitting it up gives me the opportunity to equally foolishly try to feature each one in a post of its own, so I'll leave off here for now.

P.S.: Before I conclude discussing all of the colors together, I want to point out a few things. As I mentioned, there is overlap. Each color seems to feature a few philosophical ideas more prominently than the others, but many ideas are shared and a setting or story that fits one color better than another may yet explore ideas characteristic of another. A single setting or story can also meander among colors, exploring the ideas of one and then another and changing its aesthetics along the way. Some settings have the look of one but focus on the ideas of another. This "system" is really only the result of me finding patterns that I can use as a framework for analyzing the spectrum of cyberpunk aesthetics and ideas.