Sorry this isn't a real post :C

I've entered graduate school and, as I expected, suddenly become far busier than I had been before, leaving no time to maintain my blog, let alone actually work on much of anything worth sharing on said blog. I figured I'd at least leave this note here, though, lest anyone think the blog is kaput. I intend to resume my pace of independent work and blogging about it once I have some spare time again. Who knows, with the upcoming holidays I may get enough time off to do something neat, or I might not get back to this until later on. In the meantime, my apologies for the lack of any new content and my thanks for any interest you take in the existing entries here :)

The Octorial: Part 3

Having still not turned the octree into something actually useful yet, I'll explain in this entry how to give it the functionality it needs to provide useful information once it has been built. This more or less boils down to querying the octree for objects that intersect a given arbitrary volume. For instance, to resolve collisions, each object can query the octree for objects within its own bounding box (or more precisely, within cells that touch said bounding box) and perform precise collision detection for each of those rather than for every other object in the world.

To start off, first it needs to be possible to determine whether a given cell touches a given bounding box. As I mentioned before, it's a simple task to treat a cell as if it is itself an axis-aligned bounding box: the box is a cube with the same center as the cell and an extent along each axis equal to the scale value that cell has stored. Collisions between two axis-aligned bounding boxes are covered in detail in various other places, so I won't bother reinventing the wheel here.

With the ability to quickly evaluate whether a cell touches a bounding box, extracting cells from an octree that touch said box is roughly a breadth-first search:

1. Start with the root node of the octree - the first cell within which all other cells are contained
2. Create a list of results
   
3. Create a queue of cells and add this root node to that queue
4. Start a loop that repeats as long as there is at least one item in the queue:
• Remove the first cell from the queue and see if it touches the given bounding box
• If it does, and it has children, add all of its children to the queue
• If it touches the box and does not have any children, add it to the list of results
5. When the queue is empty, i.e. all cells have been removed from it, every leaf node (cell with no child cells within it) either did not touch the bounding box or is contained in the results list.

The above in pseudocode form:

Touches(box (axis-aligned bounding box)):    returns a boolean value
    Define an axis-aligned bounding box based on this Octree's center and scale
    Return whether the two bounding boxes overlap (the actual amount of overlap need not be calculated)

OverlapBox(box (axis-aligned bounding box)):    returns a List of Octrees
    allocate result (List of Octrees)
    allocate queue (Queue of Octrees)
    queue.Enqueue(this Octree)
    while queue is not empty:
        allocate current Octree reference
        current = queue.Dequeue()
        if(current.Touches(box)):
            if(current has children):
                for each child Octree in current.children:
                    queue.Enqueue(child Octree)
            else    add current to result
    return result

And here is a visual explanation that hopefully makes some sense:

Despite the seeming complexity and number of steps, this technique can end up taking much less time than the "brute force" approach of examining every object. It can even be done many times in a single frame in a real-time environment:

Due to the orthographic camera projection and view directly down the global Y axis, the octree looks like a quadtree in this animation, but is in fact fully three-dimensional and composed of cubic rather than square cells.

In this animation, a yellow cube passes through an octree containing a cloud of 1000 small objects while querying the octree every frame for which objects it might intersect. Every cell that the cube touches is outlined in red, and lines are drawn linking the cube to each potential obstacle.

Note that it is not only the cube that has the potential to touch multiple cells at once - even despite their small size, the obstacles can intersect multiple cells as well, so it is important to check both the occupants and the visitors of each cell in the results. Above, yellow lines denote objects assigned as occupants and green lines indicate visitors that intersect one or more of the result cells despite not being assigned as occupants of them.

With the ability to search the octree for cells and objects within a specified volume, a variety of tasks become available for optimization using this octree. For instance, in a game about building things (or a procedural generator) it is possible to check for space before inserting an object without having to perform a large number of precise collision checks. An AI could use the octree to find targets within a certain range. A level loading system could use the player's location within the octree (or a quadtree) to load more detailed scenery near the player while using less detailed representations in cells further away. Space Engine and Kerbal Space Program, which I've mentioned several times on this blog, both rely on quadtrees for planetary terrain, and Space Engine uses octrees for organizing and loading procedural stars and galaxies.

Octrees have also been gaining visibility as the basis for Sparse Voxel Octrees, but that's a topic that, while fascinating, I myself have barely begun to grasp, let alone something I've tried to implement to date, so for the time being I'll leave that topic to the experts.

Hopefully this series has demystified some of the details of actually implementing an octree in your own projects, why it could be useful, and how its underlying logic works. I'm eager to hear any feedback on parts I could explain in more depth or may have overlooked.

The Octorial: Part 2

I left off having explained how to build a basic octree, but having mentioned nothing about how to use it. In fact, what I detailed before is effectively useless! The octree can be filled up with objects, and they'll be organized into cells, but there is no way to identify which cell an object occupies (except by iterating through all cells) or to use the octree to reduce the workload during tasks such as collision detection. I'll get to that in time, but first there's an issue that becomes apparent when planning such tasks.

A tempting place to start is, given an object, to determine which cell it occupies and then examine its collection of occupants, but since objects are not single points but rather occupy a certain volume of space, if an object exists near the edge of a cell it may extend out of that cell so that part of it is inside a neighboring cell. Identifying which cell it occupies and then identifying all of that cell's neighbors seems like it would be a solution, but only under a certain circumstance - if there is no way for an object to reach from one cell all the way through another and into the one on the other side (Jan Michael Vincent can't be in two Quadrants at once). If an object can do this, that means that any object could collide with any other, regardless of which cells either of them occupy!

The gray blob shown here is so large that even though it is centered on the large black dot, it reaches out of the cell containing it and into nine other cells.

The situation seems a lot like the earlier situation I described that threatened to send my hypothetical approach back to square one, but not all is lost if the non-zero volumes of objects are considered when building the octree to begin with. When inserting an object into the data structure, one could consider its extents and mark every cell that it touches in addition to the cell it "occupies." Some way to determine whether an object touches a given cell is going to be needed anyway, so that functionality can be assumed to be available and referenced here. Here's a bit more pseudocode corresponding to the additions and changes necessary (anything not shown here is the same as before):

class Octree:
    
    List of visitors (objects that do not belong to this Octree but may extend into it)

    Insert(occupant):
        if occupant is non-zero in size (how to determine this varies based on the specific development environment) InsertBox(occupant's axis-aligned bounding box)
        else InsertPoint(occupant's position)
       
        allocate point (3D vector)
       
        InsertPoint(position (3D vector)):
            point = position
            InsertPointRecursive(this Octree)
       
        InsertPointRecursive(current Octree):    same as before
       
        InsertBox(box (axis-aligned bounding box)):
            InsertPoint(box's center point)
            for each cell (Octree) returned by OverlapBox(box):
                add occupant to cell's visitors List

    OverlapBox(axis-aligned bounding box):    returns a List of Octrees
        return all Octrees that the given bounding box touches

In other words, each octree cell will now keep a second list of objects that refers to all objects that extend into its assigned volume even if they are not occupants assigned to it. When a new object is inserted, it will be added to this list for every cell that it intersects. For the time being, this is determined using an axis-aligned bounding box for simplicity, since intersections between axis-aligned bounding boxes are very simple to compute and the octree cells happen to be equivalent to axis-aligned bounding boxes already.

These lists of visitors also need to be addressed when a cell splits. Each of its new children will have to be checked for whether any of the visitors touch it and, if so, have that visitor added to its own list of visitors:

 Split():
    Do the same operations as before
    
    if there are visitors:
        for each child Octree in children:
            for each visitor in visitors:
                if visitor is touching child    add visitor to child.visitors
    optionally clear the list of visitors

This may seem like a lot of redundant data. In a sense it is, insofar as many references to any given object may exist in the octree, but this is part of a tradeoff of memory footprint for performance. By encoding more information about how the objects in the octree are related to its structure, it becomes possible to make more intelligent decisions later on when using the octree, thereby avoiding redundant work and saving valuable time. As of today, modern computers tend to have huge amounts of memory available and relatively little extra time for extraneous computations in situations such as games or other real-time simulations.

Now I did just make a lot of mentions of some way in which, given a bounding box, all of the cells touching it can be found, but not how, specifically, that gets done. Unfortunately I think that will require a third entry in this series, so look forward to that.

The Octorial: Introduction

My predilection for procedural generation and the underpinnings of large game worlds has led me to encounter the concept of an octree time and time again, to the point where I started to feel weird being so familiar with others' implementations without ever having cooked up my own. Naturally I started by looking for tutorials and reference implementations, but with limited success (though I will shout out this video and its sequels which I found fairly illuminating). Thus, true to my nature, now that I've managed to figure out enough of the basics to create something usable, I want to share what I've learned. And so:

≾ HOW TO OCTREE ≿

Octrees are a type of spatial partitioning data structure, i.e. a way to organize objects in game worlds based on their locations so that tasks related to said locations can be done efficiently. An oft-cited example is physics engines: a game world may contain a large number of objects, while the game (or simulation) requires that, like solid objects in real life, objects should avoid overlapping each other (e.g. by bouncing). A tempting naive solution for eliminating overlap is to check each object against each other object in a nested loop, but when there are numerous objects this becomes an enormous task of many thousands or millions of operations. By organizing the references to all of these objects in memory in a clever manner, one can enable the engine to make safe generalizations about them and thereby eliminate most of the work.

To start off, imagine if I ruled that the virtual world is to be treated as four adjoining squares: the Northwest Quadrant, the Northeast Quadrant, the Southwest Quadrant, and the Southeast Quadrant. Whenever some object, say Jan Michael Vincent, comes into existence, I examine where it is (its coordinates on two axes, traditionally X and Y or X and Z) and compare these values to the zero point representing the world origin. I can take the first axis to represent West and East - if the value is negative, then the object is somewhere to the West of the world origin and thus in one of the two Western Quadrants, and if it is positive then it is in one of the Eastern Quadrants. Then, making the same comparison with the second axis, I can determine whether it belongs to the Northern or Southern Quadrants.

Because all objects in the simulation exist somewhere in the simulating machine's memory, there is effectively a master list of all objects in the world. With the decisions I have just made, though, I can instead keep four distinct lists of objects - one for each Quadrant. On its own this organization does nothing, but say I want to add another Jan Michael Vincent, but I don't want there to be two in the same Quadrant. I can simply examine which Quadrant would contain the new one and then examine the objects in the list corresponding to that Quadrant, rather than all objects - if the objects are roughly uniformly distributed, then I've already eliminated 3/4 of the work.

Things like physics engines often need to go a little bit further, though. I could easily put something near the edge of a Quadrant in such a way that it extends slightly into another Quadrant. In order to see if one object overlaps another, then, I'll need to consider this possibility - not only whether this object extends into another Quadrant but whether objects in some other Quadrant are reaching into the one I'm currently examining. The end result is that I'll have to examine not just one specific Quadrant but every Quadrant that touches it, which is, unfortunately, all four Quadrants.

But what if I divide the Quadrants into Quadrants? Each Quadrant that contains some objects could be divided up and contain its own set of four sub-Quadrants with their own lists of objects, for a potential total of sixteen, just like in the hypothetical movie. Then, when a new Jan Michael Vincent appears, I can look at his current sub-Quadrant and every sub-Quadrant it touches, but not every sub-Quadrant in the world. If I'm lucky, I'll be back to eliminating 3/4 of the work again.

The fun part is that these rules can be extended with no limit. I can keep subdividing regions of space into smaller and smaller cells and organizing the data into ever more specific partitions, in so doing making it possible to eliminate ever greater portions of the total work later on. Eventually I'll be able to reach a point at which, even if many objects exist in the world, any one cell may only contain a small number of objects or none at all. If this number is small enough, I need not divide it any further because examining this small number of objects becomes a simple and short task. Visually, this would look a bit like a Piet Mondrian painting, with squares of different sizes nestled together, but the data could also be visualized as a tree, with smaller cells being connected together as branches of the larger cells from which they arose:

In this example, I have randomly distributed some black dots and then organized them with the rule that each square may contain at most one dot. Note that some squares are empty, but only squares containing more than one dot have been divided into smaller squares.

All the references to Quadrants may make it unsurprising that this data structure is known as a quadtree. An octree is the same concept extended into three dimensions - rather than partitioning space into square cells and creating 2^2 or 4 new cells each time one is divided, an octree partitions space into cubic cells and creates 2^3 or 8 cells whenever one is divided. Both quadtrees and octrees have uses for which they are better suited - for instance, a quadtree is useful for dealing with huge tracts of land that need to be loaded at different levels of detail based on how far they are from the viewer.

So far, nothing I've described hasn't been covered one place or another. My goal is to demystify how to get from this theoretical point to an actual usable octree implementation. To start, here's a sort of pseudocode adaptation of what I've discussed:

class Octree:

    List of occupants
    
    capacity (positive integer)
    
    Array (length 8) of Octree children <- Octrees contain references to "child" octrees that occupy regions of space within them
    
    scale (floating point value)
    
    center (3D vector)
    
    Constructor(parent Octree, octant (integer value from 0 to 7)):
        capacity = parent capacity
        center = parent center
        treat octant as three bits, e.g. 000, 101, or 111:
            if first bit (fours place) is 1, add half the parent scale to the center's X coordinate
            if second bit (twos place) is 1, add half the parent scale to the center's Y coordinate
            if third bit (ones place) is 1, add half the parent scale to the center's Z coordinate
            (the center is thus now shifted so that it is halfway to one of the corners of the space occupied by the parent)
        scale = parent scale / 2
    
    Insert(occupant):    <- This is structured in such a way that it is easy to extend later
        allocate point (3D vector)
        point = occupant's position (how to obtain this will vary based on the development environment)
        InsertPointRecursive(this Octree)
    
        InsertPointRecursive(current Octree):    <- This is a recursive function that will repeatedly call itself with deeper and deeper nested Octrees until it finds a suitable stopping point. I implemented it as a local function but if this is not feasible you can instead allocate the occupant and point variables separately
            if current octree has children:
                for each child:
                    if child.Contains(point) InsertPointRecursive(child)
            else:
                add occupant to occupants
                if there are more occupants than capacity    current.Split()
    
    Contains(point (3D vector)): returns a boolean value
        Compute whether point is within a cube with center equal to this octree's center and extents along each axis equal to this octree's scale (i.e. dimensions equal to double the scale). This is typically done by examining each coordinate of the given point, comparing it to the center plus or minus the scale, and returning false if the point does not fall within the appropriate range. If all checks pass, return true.
    
    Split():
        create an array of 8 children
        allocate octant (integer value from 0 to 7) and set it to 0
        while octant is less than 8:
            children[octant] = Constructor(this Octree, octant)
            (create a new child using the Constructor and a reference to this Octree and the current octant value, then add it to the array of children)
        for each occupant:
            octant = 0
            treat octant as three bits:
                if occupant's X coordinate is greater than that of the center, set the first bit to 1, i.e. add 4
                if occupant's Y coordinate is greater than that of the center, set the first bit to 1, i.e. add 2
                if occupant's Z coordinate is greater than that of the center, set the first bit to 1, i.e. add 1
            children[octant].Insert(occupant)
            (use the octant value as an array index to get the child Octree corresponding to the occupant's location and then insert the occupant into that child Octree)
        optionally clear the list of occupants, since all objects should now be referenced by the children

 
As with any pseudocode, the final implementation is bound to vary somewhat, as mine did, depending on choice of language, optimizations, and other decisions.

Since, in the interest of being clear and thorough, I've ended up making this article quite long already, I'll once again split it up and call this the "introduction." Look forward to follow-up entries detailing how I moved forward from here.

Procedural Chunk-Based Universe Part 12: Squiggles

("BLAME!" by Tsutomu Nihei, chapter 7 page 28)

As of my last post, my bridge generator had stepped out of the 2D realm into the wider (or should I say thicker? deeper?) world of 3D and gained the ability to work at angles and generate staircases. This should enable it to successfully build bridges in a wider variety of conditions, but viewed from above and strictly examining its functionality on a horizontal plane (that is, for whatever definition of "horizontal" is relevant), its capabilities haven't really changed. I've concluded that they need to change, however - randomized end points turn out to rarely fall into configurations amenable to the existing bridge generation logic, as I shall explain by recounting my efforts to explore the full possibility space.

Many game developers (or at least those who make tutorials) advise starting new endeavors by proverbially stepping away from the computer and using low-tech tools such as paper models or pencil and paper (whatever involves paper I guess). I confess I don't do this as often as these tutorials seem to suggest I should, but along my journey with this procedural generation project I've done so a fair number of times.

As before, I simplified the problem into one of connecting two locations on a line. Every bridge with two end points will necessarily have some line that would connect its end points, so if I base my coordinate system around this (i.e. pretend it's just a horizontal line of fixed length), I can skip all the reasoning around whether one point is behind the other, which one is on the right or left, etc. as long as the final code I write retains this agnosticism (e.g. don't hard-code anything based on the global X axis). The two locations on this line (represented below by circles and spheres) each have a facing direction (represented below by small arrows or cones). Drawing and contemplating a few sketches, I was able to identify six "classes" of bridge that could exist - of which my current algorithm could handle only one!

Since my original notes are very poorly suited to being read on a screen, I recreated the important parts digitally.

These classes are separated by whether the angles between the end point directions add up to more or less than 180 degrees, whether the end point directions are on the same side of the connecting line, and whether one or both end directions are facing away from the center point (i.e. have an angle from the center line of more than 90 degrees).

Only five classes are pictured because I examined the sixth (F) and determined that it should be impossible - it illustrated an "S" shaped bridge (explained in more detail below) connecting end points whose facing directions were on the same side of the connecting line (a situation that would inevitably put the bridge in class A or B and thereby not produce an S bridge).

My existing logic was able to handle class A easily enough; as the illustration shows, the end point directions and the connecting line together form a triangle, and the generator can proceed from there to find a good elbow position and connect everything.

Class B shouldn't be too complicated either - the generator simply needs to be adjusted to forgive angles in excess of 90 degrees when building its two elbow chains (the groups of curved segments at one end and at the elbow).

I'd like if my generator could be made able to handle all of these classes, though. For the other three classes, the angles themselves should be nothing the algorithm can't handle, but a new ingredient was needed - the bridge had to be able to curve twice, first from one end to some midpoint on the connecting line and then from that midpoint to the opposite end, forming a vague "S" shape. So far I've encountered no compelling reason not to simply make this midpoint be the halfway point between the end points (their arithmetic mean), so for now that's what I have done.

The generator now "plans" a bridge by examining the configuration of the end directions, identifying the class of bridge needed, and storing all of the important bridge data in a container class. This container class can itself contain two "sub-bridges" with their own sets of data; if an S bridge is needed, as in classes C, D, and E, the generator identifies the midpoint, computes suitable "average" directions leading out from it in opposite directions, and then plans out these two sub-bridges, each using the midpoint and one of the two end points. This container is then used in actual bridge generation, and if the sub-bridges are assigned, the task is split into two separate bridge generation tasks.

Honestly this debug readout hardly even makes any sense to me, the one who programmed it, so I'm not going to bother trying to explain what's going on this time. I felt like I needed another picture and this one was the most relevant.

When working out how to calculate facing directions for the midpoint, I made sure that each facing direction was always on the same side of the connecting line as the end point toward which it pointed - thus, each of the two sub-bridges will have to fall into class A or B. While sketching out the problem, I determined that the properties of classes C, D, and E result in certain sets of possibilities for which classes the sub-bridges can take:

• Class C will have sub-bridges that always both fall into class A.
• Class D will have one sub-bridge in class A and the other sub-bridge in either class A or class B.
  
• Class E will always have one sub-bridge in class A and one in class B.

This means that for now, my existing code is sure to be able to handle generating sub-bridges for bridges in class C, and sure enough, once I had done a fair bit of debugging (added complexity tends to add exponentially more bugs), I was treated to the beautiful first sight of an S bridge forming on my screen:

As has surely been implied heavily enough in this post already, this new chunk of work I've given myself is still far from finished. I have yet to see if my logic can handle class B (and in the likely case it can't, upgrade it), investigate whether it can handle classes D and E, or plug it back into other systems such as the city generator I showed before to see if it still works or if new bugs have appeared - let alone begin tackling the task of (finally) wiring it up to the procedural chunk system. I look forward to detailing my (mis)adventures with those hurdles soon. But hey - at least now I can finally imitate that manga panel at the top of the page!

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.

Procedural Chunk-Based Universe Part 9: Across this New Divide, Part 2

Picking up where my last entry left off: Once I had the basic ingredients for an adjustable bridge whose segments could change angle and length, the next task was to give these to an algorithm and have it use these features to construct a bridge of whatever shape and size would be needed.

Computers, and in turn algorithms they run, are fundamentally mathematical objects and thus - sigh - I resigned myself to digesting a heavy serving of math, specifically trigonometry in this case. Each end of the bridge would be a segment that had to face a particular direction - that of whatever connected to the bridge at that end (e.g. one of a pair of doors). Thus, in mathematical terms, each end comprised a point in space (I was only worrying about two dimensions at this point) and a direction vector which had to be followed for at least the length of one bridge segment. By combining these direction vectors with a line connecting the two points, I could create one side and two angles. My task, therefore, reduced to its most basic mathematical formulation, was to complete a triangle given these ingredients, a situation often denoted as "ASA" for "Angle, Side, Angle" in academic settings:

Points A and B are the bridge's end points and arrows indicate the direction vectors; combined together, these constraints yield the rest of the figure including point C and the various angles labeled with lower case letters.

Having drawn this triangle, I considered how I would use curved segments to accomplish the change in direction. I couldn't rely on a single corner to do this, because any curved segments would change their overall lengths as their curvatures were adjusted, and I had set them up in such a way that they could be constructed with various shapes and amounts of curvature. If I started building a curve at one end, by the time that curve was in alignment with the direction needed on other end, the end of the curve would very likely be out of alignment with the position of the other end such that a straight segment couldn't properly connect them.

Fortunately there was a way out! Curves facing opposite directions had the potential to cancel out these offsets in position if they curved by the same amount. In other words, if I split the curved part of the bridge into two halves, an isosceles triangle, having two corners that have the same angle, would permit me great freedom in how the curves were actually shaped while maintaining the certainty that the ends of the curves could line up with both ends of the bridge. In the above image, triangle ACD is an isosceles triangle, in which the exact angles are unknown but angles b and c are known to equal each other. Thus, if I could find point D, I could simply build a bridge connecting A to D and then easily connect that bridge to B using only straight segments.

After doing some calculations using Al-Kashi's Law of Cosines, I was able to find places to put the curved parts of the bridge and then align them with the end points and with each other:

In my experimental setup, a bridge is being generated to connect the platforms at the top of each of these two cylindrical towers. Note how each curved segment here is attached at one end to the corresponding point in the isosceles triangle, rather than being centered on it. The goal, after all, is to have the ends of the bridge and its constituent segments aligned; the positioning of the centers of the pieces is of little importance.

Because the two curved segments curve the same amount in opposite directions, the offsets that occur at their end points cancel out and thus they are in alignment with each other. So far I've only experimented with a single pair of curved segments; but the system is designed with the concept of chaining multiple curved segments together in mind, in case individual curved segments are unable to curve far enough to achieve a full alignment on their own.

Now it's a matter of repeatedly spawning straight segments in the gaps to fill them in. This process makes use of the same Node Attachment system I implemented before that was used for manually constructing and later automatically generating levels. To minimize complexity for the sake of performance, first a series of straight segments is attached, continuing until the remaining gap is within the extension range of a single telescoping segment.

In the first draft of this system, only one type of "normal" straight segment was included, but recently I have implemented an array of segment templates from which to choose. The system iterates through this array, sorted from the longest template to the shortest, until it finds one that fits in the remaining gap without extending too far; thus the final bridge ends up being built out of significantly fewer total segments, which should improve performance overall.

For the sake of clarity I have colored the two segments yellow and green. First the longer yellow segment is attached in the gap, then the shorter red segment. Since the remaining gap is less than the maximum length of a single telescoping segment, no more "normal" segments have been inserted.

Now that a single telescoping segment can span the remaining gap, it is inserted and its length is adjusted to match the remaining distance:

The telescoping segment consists of a base (red) and an extended section (yellow), which slides in or out to match the desired total extension distance.

The second gap is then filled in the same manner as the first:

Diagram of the full construction process. For clarity I have shrunk the visual models of the segments slightly to create small gaps.

This system has served my purposes quite well so far, and I have compiled an interactive demo which is available on my itch.io page. In the demo the bridge construction process is set up as a coroutine with a small delay so that one can watch the bridge form.

It does have some constraints, though. It can only build bridges if the triangle depicted above can be formed, i.e. some point exists in between the two end pieces toward which both pieces are pointing (point C, even though point C itself is not directly used in the calculations). If, say, both ends are pointing toward one another but offset by some amount so that the bridge would have to curve in two directions (a sort of "S" shape), a bridge is not formed. Also, naturally, a bridge cannot be formed if the end points are facing away from one another. In the future, it should be possible to address either of these situations, if needed, by chaining two or more bridges together.

The ability this system provides to connect arbitrary locations (if they meet the aforementioned constraints) is valuable for both the 3D chunk system I discussed (for connecting doors between neighboring chunks) and the level generator I discussed before that (for creating closed loops). My goal is eventually to have all three of these work together to create a system capable of generating a limitless interconnected network of traversible spaces. I expect it to be just as complicated and difficult as it sounds, and I look forward to sharing many more of my adventures along the way.

Procedural Chunk-Based Universe Part 8: Across this New Divide

I remember black skies, the lightning all around me. I remembered each flash, as time began to blur, like a startling sign that fate had finally found me... and your voice was all I heard. Did I get what I deserve?

SO GIVE ME REASON! To prove me wrong, to wash this memory clean, let the thoughts cross the distance in your eyes! Give me reason to fill this hole, connect the space between; let it be enough to reach the truth that lies across this new divide...

Sadly (or perhaps happily, if we're being honest), this post actually has nothing to do with Linkin Park or the Transformers franchise.

My earlier post "Going in Circles" detailed at length how my random level generator is able to piece together rooms and passageways into a tree structure but is unable to create cycles or loops that allow multiple paths from one area to another. I explained how this was important for game level design and then left off without having provided a solution.

What I did say was that my next step in solving the problem would involve adjustable pieces. The need for these arises from my insistence on not having the shape of the level be bound to a grid, as I detailed in my previous post about doors. When room prefabs aren't based on a grid, they can vary in dimensions in ways that easily and rapidly become unpredictable. A series of rooms can easily be generated that loops back toward an existing room's doorway, but it's all but inevitable that it won't line up in a usable fashion at all, let alone perfectly:

In this example, I've constructed a hallway that, due to the diagonal segments, can't align properly to reconnect to the central hub. A hallway segment spawned in the gap isn't able to fit without overlapping so badly it obstructs the player from moving past it.

How can I possibly connect the space between and bridge this new divide?

The solution I found was to implement "stretchy" segments that were able to telescope between a minimum and maximum length. By replacing some of the hallway segments with these, I gained the ability to fine-tune the dimensions of the hallway and align it precisely with the door:

One "stretchy" segment is placed at the end of the hallway and one in a perpendicular section, allowing the hallway to be adjusted on two axes.

Of course, however well manual adjustments may work, they won't be available during procedural level generation. I had to craft some kind of automated system that would find the correct alignment values and adjust the segments accordingly. Along the way I devised a way for segments to have a "secondary axis" for extension so that staircases (or in practice, ramps) could be used to join areas at different heights. The result was a surprisingly satisfying animation:

When given a target location, horizontal catwalks and ramps both have the ability to calculate the needed displacement and change their extension values accordingly so that their endpoints align with their destinations.

I didn't have to make it an animation, naturally - in practice these adjustments can be made in a single step when generating a level.

Nearly all the ingredients were in place at this point, but there was one more problem that arose - doors had no reason to end up perfectly oriented toward one another. Only because the angles happened to cancel out was it possible for me to achieve alignment in the above images, but while working on the random doors in my previous post, I realized that unless they were given random orientations as well as positions, the grid structure would still not quite be hidden - anywhere a player went, it would be easy to detect the orientation of the underlying grid cells by examining the orientations of the doors, and from there it would be easy to approximate the grid cells' locations. It sounds more subtle and complicated than it actually is when seen first-hand in a game world.

Thus in addition to segments that could extend linearly, I had to create a way for them to bend. As of this post I'm still working out a few kinks in this system, but what I have so far is able to calculate the direction in which a target position lies and then rotate the hallway to run parallel to that direction (which is slightly different from pointing straight toward it):

This functionality can be chained and combined with the existing telescoping functionality to create a self-adjusting bridge that does its best to maintain a connection between two points:

It's still far from perfect, and more importantly, it's of very limited use in this state. I can manually design a bridge that connects two points if it can, but the bridge still has no way to deal with the orientations of whatever exists at those points, and at this point I didn't have a system for automatically constructing bridges like this. In my next post I'll describe the solution I devised.