Everyone read Part 1? you didn’t? well go do it.
So, last time I outlined the methods I’ve used in the past, but there are more than one way to skin a cat. Actually that’s a weird ass phrase, at what point in history were we skinning cats? What the fuck?
Graph Theory: Required Reading
First off I’m going to go over graph theory in basic because I wrote the below section then realised it probably didn’t make sense to someone without an understanding of what terms related to graphs mean. What’s a graph?
This is a graph of a network. In graph theory a graph is a series of nodes connected by a series of edges. edges may have a direction or be both ways, nodes may be connected or free floating. it’s a topological representation of the representation
This is a graph of the function y = x2 − x − 2. This is “graph” as in graphical representation. Which is not important for graph theory.
However it is important for things like computer graphics, and (as mentioned in last article) brushes that effect a mesh in a given area.
I’m sure there’s a reason why these are both called graphs.
Topology (mesh) and Topology (mesh) (type of network)
And here is where this becomes linguistically frustrating but kind of really important. A Mesh Network is a graph that represents the relationships between points, but in computer graphics a mesh network is also kinda how 3D objects are represented.
In computer graphics a mesh is a network of arbitrarily connected vertices with unorganised hierarchy, each vertex being a point in 3d space. a list of which vertices make up triangles are used to make a solid 3d shape from these vertices, and then… [some other maths bullshit], and you have a 3d object on your screen.
In network topology a mesh is a network of arbitrarily connected vertices with unorganised hierarchy. This is more or less the same thing, except we don’t care about the triangles it makes, just how things are connected.
Side note: a tree is a hierarchical network so the leaves of the quadtree i mentioned last time are vertices in a tree.
For a lot of forms of graphs, the distances and directions between points are ignored for the sake of readability, which leads to stuff like Topological maps, where instead of a graph being used to show where something is, it’s used to show their relationship in the most presentable form.
Crucial thing to remember here is ultimately though it’s the same concept, just applied differently.
Anyway, to tangent off to what I actually wanted to talk about…
Level Design is actually just Network Topology
I don’t know how obvious this one is but… essentially at the core of level/world design in video games is “you have a bunch of ideas for places, you have to define how the player can get between them, ergo graph where vertices are your points of interest and lines are the path between them”. There’s a couple of terms for this: Bubble Diagrams, Flow Diagrams, Flow charts, sometimes people literally just use “tube map” or “subway map”. There’s probably other ones.
![A bubble diagram, there is a big bubble labelled Player Start, from it there are 2 two-way routes to bubbles marked "Arena" and "Top of Skyscraper", and one one-way route that leads to the bubble "NPC", which then leads to the bubble "Villain's Office", which then leads back to Level Start. Each connection is labelled either "[challenge] segment" in red or "shortcut" in green depending on if they lead away from or towards the start, with the omnidirectional routes having both.](https://i0.wp.com/severalfighters.net/wp-content/uploads/2026/08/bubble-diagram.jpg?resize=372%2C494&ssl=1)
A bubble diagram by Mike “Dodger” Stout, Source: https://www.ongamedesign.net/beating-design-block-level-design/#more-140. 
A flow diagram, also from Mike “Dodger” Stout, Source: https://www.ongamedesign.net/designing-fps-multiplayer-maps-part-2/ 
A map made by reddit user Created_or_Made of the map 2fort from TF2. Not a level design tool but rather someone’s analysis of it using a similar graph. Source: https://www.reddit.com/r/tf2/comments/8nuuaq/i_made_a_map_of_2fort_so_i_can_hopefully/
See how you can easily break down a level, both singleplayer or multiplayer into the key connections between points of interest.
Anyway just keep this in mind going forward: any game environment can be defined as a series of places and the paths/sightliness between them.
Why is everything Wave Function Collapse these days?
Wave Function Collapse: The (Old) New hotness
Towards the end of when I was working on my old procgen project, a method of procedural generation called “Wave Function Collapse” was starting to rise to prominence. As it wasn’t really relevant to my project I mostly ignored it, but I’ve kept some tabs on it since. it actually originates in 2009 from a siggraph from Paul Merrell, and in 2016 a project by Maxim Gumin that used the paper to make a texture generator. I first started encountering it as a term at around the turn of the 20s.
The name “wave function collapse” is a term from quantum mechanics. it’s what happens when you look inside a box to see if a cat is… ok there’s a lot of bad things happening to cats in this post and I am not happy about it.
*sigh*
In quantum mechanics, waves/particles/whatever exist in a superposition, which is to say they could be in several states probabilistically, until you prod them, at which point it becomes apparent what state they’re in.
Similarly in Wave Function Collapse the initial algorithm, you start with a grid of cells with a number of potential fillings, then based on their neighbouring cells, eliminate possible fillings so that when it comes to roll the dice on what’s in the cell, it connects with what’s in its neighbours. These rules are called Graph Grammars (more on that later). So… a simple example would be a minecraft torch, which can take one of 6 states based on its neighbours, attached to each wall, upright, or collapsing if unsupported.
The game Quantum Chess is pretty much the best “oh, that’s what that means” demonstration of this I can think of.
I kinda like how many weird physics/maths concepts can be made play-around-able by chess. like the multiversal time travel chess, that was pretty cool.
Weren’t we supposed to be getting away from grids? Well… yes but you see this gets more complicated.
The more new hotternesses.
Hierarchical Semantic Wave Function Collapse, a paper by Shaad Alaka and Rafael Bidarra, is the next convolution here. Essentially instead of each cell potentially being able to be filled by anything, narrowed down by its neighbours, cells are filled in several passes, with each refining the type of tile further and further with each pass. The example given is that a tile on a grid could initially be selected for a castle, and then the grid subdivided and the tile then pulling from
The second convolution is “oh yeah this doesn’t have to be grid aligned”. Remember network topology (see above?) well, a grid is just a type of network called a lattice, where every point is sorta uniformly connected to each other. but we don’t have to do that. We can, for example, apply it to a tree.
One very example I can think of this, from the early 2010s, is the Minecraft Village Generator. In Minecraft a village is generated by starting with a root, in initial versions this was the well, but in current day versions this can be a well, crossroads, structure with a bell, etc. Roads are generated out of that from a selection of road pieces, with each road potentially connecting on to another road (or on a dice roll, just ending there. Each road has a series of potential spots for buildings or work sites (farmland, etc) so if the space is free a dice roll is made to fill in that slot. Finally in those buildings leaves representing villager mobs and chests are filled in. throughout this there is a rule on the maximum number of structures which limits what a leaf can be further as they are filled in.
One weird inverted example of this is the game Tiny Glade. Rather than starting with a complete network the game has a series of nodes (path, building, wall, etc). by placing them next to each other they are added to a network and are reassigned to a node that fits that connection.
Graph Grammars and Graph Rewriting
Graph Grammars are rules for how nodes in a graph should connect, so if you want to make or remake a graph where everything follows a set of rules, the grammars are those rules.
This is essentially the logic Wave Function Collapse runs on, ether in a lattice or in the more floppy types I talked about above. each node in a graph can be in multiple states but depending on the Graph Grammar it whittles down those options based on the nodes its connected with. potentially several times.
Going more broader, graph rewriting can include extending or deleting a graph, again just like those subdividing Quadtrees, or like the minecraft village above.
There isn’t really much of a conclusion to this section other than… “this is another way to look at it/more words for your lexicon”
Graph the Planet.
Let’s go back to that heightmap of the earth from the first part.
So, this is one way to represent the earth. Each pixel represents an altitude at a given longitude and latitude (probably, it doesn’t quite look like a Mercator projection), we can take the shapes of the continents from where the pixels get light enough to come above “sea level”, and the mountains and deeps from areas of extremely high/low saturation.
This is called a raster, as in Raster Graphics. Each point on a texture is discrete and exists on a uniform lattice, though when projecting a raster back on to a sphere, as noted, pixels sorta get bunched together at the poles
My big frustration with rasters with regards to procgen is that the pixels don’t really represent a concept, they’re just… descriptive of the result. Working with pixels as a basis isn’t really that representative of the environment. Like I say I’m trying to avoid heightmaps.
Let’s try something else.
So here’s a map of the earth’s continental plates, each in a different colour, and the interactions between them (in small arrows, do feel free to zoom in).
While this is very much still aa visual representation of the earth (as in the countries are drawn on and all that) if you ignore that and just look at the plates and boundaries things start to look… graphy.
Say I took each continental plate and replaced it with a vertex and each boundary and replaced it with an edge…
So that gives us a new map of the earth where each vertex is representitive of a terrain features (in this case a continental plate), and each connection representative of the interactions between them. But… this isn’t just a descriptive representation of a planet, we can work forward from a network like this to create a planet where the surface is made up of nodes that represent a feature.
Now, remember from earlier: A mesh graph (like the one we made of earth’s continents above) is, structurally, the same as a mesh in computer graphics. For a mesh in graphics, we care about the positioning of the nodes in the graph in space. and that’s what gives us the form of the graph… so let’s add that back in.
Turning a mesh into a mesh
So… What does this all mean? how does this all come together?
Essentially, what I’m trying to angle at is that if I have a graph of the features on a planet, then I can also use that as the mesh for the visual representation of a planet.
So, if a planet is made out of a graph of features, and those features are connected in a way analogous to a 3D mesh, then if we turn that into a 3D mesh we get a mesh that conforms to the shape of the features.
As you’ve seen, projecting features onto a lattice (as represented by my Quadtree planet in my earlier project) gives us less than ideal looking results which we can only really mask. My theory is if we start with a graph representing each feature, then the geometry can be generated to match, Rather than complicate and hinder its representation.
In practice
Let’s go to godot and start coding some procedural meshes.
Every point on the surface of a sphere’s distance from the centre of the sphere’s radius, or in other words on a sphere with a radius of 1 (a Unit Sphere), placed in the middle of a 3d scene, every point has a length of 1. Handily, we can Normalise a vector/point into a Unit Vector (length of 1) by dividing each of its components (X, Y, Z) by its length.
Let’s place some random points, then normalise them.
The exact method i used was starting with a tetrahedron and then placing a vertex a random distance on the line between two verticies on it.
Because this sorta biases new verticies towards appearing in areas where more vertices have been placed before, I do this in multiple passes, only allowing each pass to place vertices between points on the previous pass, and having a minimum seperation distance between vertices.
We can then join these vertices up into a convex hull, the smallest mesh that surrounds every point without curving inwards at any point.
There’s multiple methods for this but I chose to implement a Beneath-Beyond algorithm. We, again, start with a tetrahedron (taking our first 4 vertices as those are they), then for each vertex delete any triangles it is above.Then we connect the vertices on the edge of the new hole in the mesh to the vertex we’re adding. Ideally for rendering we want the winding angle of each triangle to be the same, and we can ensure this by calculating the clockwise normal of a potential triangle to make sure it is pointing outwards.
If you repeat this for every vertex you get a mesh that contains every vertex and all outside edges between them.
Side notes: First off, Normally we’d want to check if a point we’re adding is inside the existing mesh, and remove it if it is, but since every point is normalised, and thus on the surface of the sphere, we can skip that check as they’re all going to be outside the mesh. Secondly, as you may have guessed we could technically have done this at the same time we were adding the points, but I wanted to be able to reuse the convex hull code for making more graphs so I split them up.
Better Graphics
So again this ends up with a mesh that looks like this. In this literal display of the graph, every vertex is a “tectonic plate”, I’ve used blue, green and brown spheres to represent if each plate is oceanic, continental, or a craton respectively.
Cratons are some of the oldest tectonic plates on earth, so in my rough generation method cratons are rare, and oceans are common, but a plate placed adjacent to a craton can become continental, as can a plate placed next to a continental plate. It’s a good approximation for now but I’d love to elaborate on it later.
Consider this the first example of wave function collapse involved in this method.
However this kinda has some drawbacks. As the mesh is the graph, Each plate is represented by a point, and can only have one interaction with its neighbours. Which is a little more simple than the continental relationships of the plates on earth. Fortunately while I was researching into connecting points on the surface of a sphere, this was one of the articles I dredged up, where the author was discussing different types of convex hulls: https://www.chiark.greenend.org.uk/~sgtatham/polyhedra/. I ultimately didn’t use much from their methods but the idea of taking the dual of a polyhedron to produce a version of it swapping points surrounded by triangles for n-gon faces came from here.
The dual of a polyhedron is that polyhedron if you traded the vertices out for the midpoint of each face. To find the dual around a given plate’s node we take the centre of every triangle around it, normalise it so it sits on the surface of the sphere and sort them clockwise, then connect them together into a mesh.
I don’t have any screenshots of this so… enjoy the image of how duals work.
Having plates not be so simple can be done by welding them together into some sort of Meta-continent object containing several plates. I randomly assign each node a heading representing the direction it would travel if it was experiencing continental drift, and then for every adjacent node with a similar enough heading i weld them into a meta-continent.
Finally I combine the dual of each meta-continent’s plate’s point into one mesh with a shared slightly random colour, again green for continental crust, blue for oceanic.
Because I kept the convex hull algorithm separate I was able to create another convex hull over the centre of each meta-continent and then use their overall headings to define the relationships between them. Here I use Red for convergent boundaries (collisions), blue for divergent (rifts), and green for transform boundaries (fault lines).
OK so, so far we’ve looked into the relationships between networks and graphs and how to use them for generating geometry based around connected features. We’ve defined the nature of the edges connecting them by comparing the attributes of each node, and we’ve done some light use of wave function collapse in terms of assigning oceanic or continental crust to our plates.
But as you may have noticed the name of this series of articles is “Hierarchical Network Collapse” so… I think we need more hierarchy and more wave function collapse. Also I’ve mentioned brushes a lot and yet they haven’t come up yet and also won’t be coming up in the 3rd part of this definitely more than 3 part series, but we will start to experiment with hierarchy as well as
Oh and one final disclaimer and a half before we continue:
As you’ve seen throughout this article most of the method I’m working on is drawing from prior work that’s been out there for years at this point. I do not really consider myself as the grand inventor of an entirely novel method of making planet terrain, I’m sure there’s someone out there doing something similar or identical. The point of this series isn’t to create something wholly new or unique, just to document the process of me working on a system that fits my needs, tickles my fancies, and avoids the problems I’ve had with other systems.
Also when I complain about a lattice method of representing a planet I don’t mean to badmouth the people out there working on similar planet procgen projects that use cubespheres or iso spheres or goldberg polyhedra. Or those using voxels and 3D stuff to represent their planets. A lot of the projects out there I’ve seen or have followed are really cool and have done far more sophisticated work than I have to make their planet surfaces look… well, not shit. I just want to come at it from a different perspective.
A few I’d recommend checking out if you’re curious are the aforementioned Devote and Fractal Philosophy, as well as the ever-present Sebastian Lague both for his procedural planet experiments, and non-procedural but still quite helpful for spherical spaces earth exploration game series. Aria‘s procedural generation planet thing was pretty cool too. As always I’ll recommend checking out the Kerbal Space Program Unite talk from 2013 on their PQS system even if it’s explicitly what I’m trying to move away from, as well as Catlike Coding‘s older tutorials on mesh generation which I also used in my older system that I’m trying to move away from. Oh and I haven’t checked out Incandescent Games‘ Planetsmith project all that much but it looks pretty cool. But that’s barely a fraction of the openly discussed projects out here in this space. Finally I’d like to link to this article on the game Planet by Oskar StÃ¥lberg which I wasn’t aware of while first writing this article but it’s a cool pre-WFC WFC style planet thing. This is quite a fertile field of gamedev so if you’re interested in learning more there’s a lot of stuff to check out and I hope this series is a good stepping stone.
Til next time…
How do I loathe thee? Not much, so feel good about yourself.
-Matt