(This isn't a VR game - after Eye of the Temple I'm done with VR for the time being.)
The project is in its early stages. The game will be fully procedurally generated, and so far I've been working on a series of disconnected experiments and proofs of concept that will eventually all be rolled into the game. These include procedurally generation of terrain, gameplay progression, creatures, and music.
Procedural terrain
I first started work on this project in March of 2016 when I cancelled the (also procedural) game I worked on at the time called The Cluster. I created an endless procedural forest terrain and managed to make natural-looking paths go through it with switchbacks etc. by using pathfinding for planning the paths. After adding grass and trees I ended up putting the project on hold to begin working on Eye of the Temple. In September of 2023 (seven years later) I started working on the terrain again. I've been improving the grass and tree coloring, adding water streams to the forest, and added little planks and bridges over the water streams.Gameplay progression
After releasing Eye of the Temple for PC as well as several updates for it, I began thinking about The Big Forest again, and developed some new ideas for what kind of game it could be.In March 2022 I developed a way to procedurally create dependency graphs. A dependency graph is a concept in mathematics and computer science which has been independently "discovered" by lots of game developers because it turns out to be pretty central to designing any non-linear game. Here's a few different articles by others that discuss what they are:
- Puzzle Dependency Charts by Ron Gilbert of Monkey Island fame
- Puzzle Dependency Graph Primer by Joshua Weinberg
- Dependency graph Wikipedia article
- How my Boss Key dungeon graphs work by Mark Brown of Game Maker's Toolkit
Obviously this proof of concept is using a completely different aestetic than the terrain prototype, but that's just because it made it easier to iterate quicker. The plan it to unify it all eventually.
Creatures
I want the mystical forest in my game to be populated by lots of strange creatures, and of course the goal is for these to be procedurally generated too. I haven't come very far on this front, but I did a bit of experimentation both with procedural models and procedural animation. For the animation aspect, I can draw on my experience developing my Locomotion System back in 2009.Music?
I did a little bit of experimentation with procedural music as well. I haven't made a final decision if the game will be using procedural music or not, but it would be neat. Naturally, I'd have to make a lot more progress for the quality of the music to be suitable.Mystery and wonder
Furthermore I have ideas about how to populate the world in a way that's informed by my article from 2021 about designing for a sense of mystery and wonder. Combining all these elements into an actual game is going to be a tall order though.If you'd like to follow the progress, you can see the social links in the sidebar, or old-school add my blog to your rss feed reader.
4 blog posts related to The Big Forest (working title)
Procedural creature progress 2021 - 2024
For my game The Big Forest I want to have creatures that are both procedurally generated and animated, which, as expected, is quite a research challenge.
As mentioned in my 2024 retrospective, I spent the last six months of 2024 working on this — three months on procedural model generation and three months on procedural animation. My work on the creatures actually started earlier though. According to my commit history, I started in 2021 after shipping Eye of the Temple for PCVR, though my work on it prior to 2024 was sporadic.
Though the creatures are still very far from where they need to be, I'll write a bit here about my progress so far.
The goal
I need lots of forest creatures for the gameplay of The Big Forest, some of which will revolve around identifying specific creatures to use for various unique purposes. I prototyped the gameplay using simple sprites for creatures, but the final game requires creatures that are fully 3D and fit well within the game's forest terrain.
I've seen a fair amount of projects with procedural creatures. It's not too hard to create a simple torso with legs, randomizing the configuration, and animating movement by transitioning the feet between footsteps in straight lines or simple arcs.
This works fine for bugs, spiders, lizards and other crawly critters, as well as for aliens and alien-like fantasy creatures. The project Critter Crosser is doing very cool things with this. While it features mammals too, I'm not sure they'd translate well outside the game's intentionally low-res, quirky aesthetic.
If we also consider games where only the animation is procedural, Rain World is another example where this works great for its low-definition but highly dynamic alien-like creatures. Spore is a classic example too, though its creatures often end up looking both alien and goofy.
For The Big Forest though, I want creatures that feel like they truly belong in a forest, with movement and design reminiscent of quadruped mammals like foxes, bears, lynx, squirrels, and deer. The way mammals look and move is far too distinct to simply "wing it" — at least in my game's aesthetic. Achieving realistic mammalian creatures requires thorough study, so although I also plan to include non-mammal creatures, I’m focusing primarily on mammals for now.
Procedural generation of creatures
The basic problem is to generate forest creatures with plausible anatomy with a small set of parameters and ensure that:
- The parameters are meaningful so I can use them to get the results I want.
- Any random values for the parameters will always create valid creatures.
My main challenge is identifying what constitutes meaningful parameters. This is something I have to discover gradually, starting with a large number of low-level parameters based on minimal assumptions and eventually narrowing down to a smaller set of high-level parameters as I refine the logic.
From the beginning, I decided to focus on basic proportions for the foreseeable future, without worrying about more subtle shape details. For this reason I limited the generated meshes to extruded rectangles. I had to start somewhere, and here's the glorious first mesh:
Later I specified the torso, each leg, each foot, the neck, head, jaw, tail, and each ear as multi-segmented extruded rectangles. I found this approach easily sufficient for capturing the likeness of different animals. By the end of 2023, I had produced these three creatures and the ability to interpolate between them:
This was based on very granular parameters, essentially a list of bones with alignment and thickness data. Each bone length, rotation values, and skin distance from the bone in various directions was an input parameter, totaling 503 parameters.
Creating creatures from scratch using these parameters was impractical, so I developed a tool to extract data from skinned meshes. The tool identified which vertices belonged to which bones and derived the thickness values from that. However, it was error-prone, partly due to inconsistent skinning of the reference models. For example, in the cat model, one of the tail bones wasn’t used in the skinning, which confused my script. This is why part of the cat’s tail is missing in the image above.
I tried to implement workarounds for such edge cases, and various ways to manually guide the script towards better results for each creature, but each new reference 3D model seemed to come with new types of quirks to handle. After resuming work in 2024, I had these seven creatures, with their reference 3D models shown below them:
(I lost two of my original reference 3D models — the coyote and bull elk — because they were in Maya format. Since I don’t have Maya installed, when a project reimport was triggered, Unity couldn’t import the models, and they vanished. Since it's not standard practice to commit Unity’s imported data (the Library folder) to source control, I couldn’t recover them.)
Anyway, so far all my efforts had been focused on representing diverse creatures through a uniform structure that can be interpolated, but I hadn't yet made progress on defining higher-level parameters.
Failed attempts at automatic parametrization
Once I shifted my focus to defining higher-level parameters, the first thing I tried out was using Principal Component Analysis (PCA) (Wikipedia) to automatically identify these parameters based on my seven example animals. In technical terms, it worked. The PCA algorithm created a parametrization of seven parameters, and here's a video where I manipulate them one at a time:
As I suspected though, the results weren't useful because each parameter influenced many traits at once, with lots of overlap, making the parameters not meaningful.
Why did it create seven parameters? Well, when you have X examples, it's easy to create a parametrization with X parameters that can represent all of them. You essentially assign parameter 1 to represent 'contribution from example 1', parameter 2 to represent 'contribution from example 2', and so on. This is essentially a weighted average or interpolation. While this isn't exactly what Principal Component Analysis does, for my purposes it was just as unhelpful. Manipulating the parameters still felt more like interpolating between examples than controlling specific traits.
When I talk about "meaningful parameters", I mean parameters I can understand — something I could use in a "character creator" to easily adjust the traits of a creature to achieve the results I want. Say, parameters such as:
- Bulkiness
- Tallness (relative to back spine length)
- Head length (relative to back spine length)
- How pointy the ears are
- Thickness of the tail at the base (relative to torso thickness)
However, PCA doesn’t work that way. Each parameter it produces influences many traits at once, making it impossible to control one trait at a time. I encountered the same issue in the academic research project The SMAL Model. While this project is far more sophisticated than what I could do, and is based on a much larger set of example animals, their PCA-based parametric model (which you can try interactively here) suffers from the same problem. Even though it can represent a wide range of animals, I wouldn't know how to adjust the parameters to create a specific animal without excessive trial and error.
I'm also convinced that throwing modern AI at the problem wouldn't work either. Not only would it require far more example models (which I don't have) and AI training expertise (which I have no interest in acquiring); it still wouldn't address the fundamental issue: An automated process can't understand what correlations and parameters are meaningful to a human.
Another problem with automated parameters is that they don't seem to guarantee valid results. When experimenting with my own PCA setup, or with the SMAL Model I linked to, it's easy to come across parameter combinations that produce deformed glitchy models. Part of finding meaningful parameters is figuring out what constitutes meaningful ranges for them. For example, the parameter "Thickness of the tail at the base" might range from 0 (a minimal tail thickness, like a cow's) to 1 (a tail as thick as the torso, like a crocodile's or sauropod's).
This ensures that the tail thickness can't accidentally exceed the torso’s. It also means that changing the torso thickness may affect the tail thickness too. While this technically involves "affecting multiple things at once", it’s done in a way that’s sensible and meaningful to a human (specifically, me). An automated process can't know which of these "multiple things at once" relationships feel meaningful or arbitrary.
Manual parametrization work
Having concluded there was no way around doing a parametrization manually, I began writing a script with high-level parameters, which would produce the values for the low-level parameters (bone alignments and thicknesses) as output.
I made a copy of all my example creatures, so now I had three rows: The original reference models, the extracted creatures (automatically created based on analyzing the skinned meshes of the references) and the new sculpted creatures that I would try to recreate using high-level parameters.
Initially, the high-level parameters controlled only the torso thickness (both horizontal and vertical) and tapering, while the other features remained as defined by the extracted creatures. Gradually, I expanded the functionality of the high-level parameters, ensuring that the results didn't deviate too much from the extracted models — unless they were closer matches to the reference models.
Why keep the extracted models around at all instead of directly comparing with the original reference models? Well, I was still working with only extruded rectangles, and there's only so much detail that approach can capture compared to the high-definition reference models. The extracted models provided a realistic target to aim for, at least for the time being.
From there, my methodology for moving towards more high-level parameters was, and still is:
- Gradually identify correlations between parameters across the example creatures, and encode those into the generation code. The goal is to reduce the number of parameters by combining multiple lower-level parameters into fewer higher-level ones, all while ensuring that all the example creatures can still be generated using these higher-level parameters.
- As the parameters get fewer and more high-level, it becomes easier to add more example creatures, which provides more data for further study of correlations.
I repeat these steps as long as rolling random parameter values still doesn't produce sensible results.
Here's a messy work in progress:
To help me spot correlations between parameters, I wrote a tool that visualizes the correlation coefficients between all pairs of parameters, and shows the raw data in the corner when hovering the cursor over a specific pair. (In this video, the tool did not yet display all parameter types, so a lot of parameters are missing.)
Focus on joint placement within the body
In 2024, most of my focus on parametrization revolved around the sensible placement of joints within creatures. For instance, in all creatures with knees, the knee joint is positioned closer to the front of the leg than the back. While the knee placement was fairly straightforward, determining the placement of hip, shoulder, and neck joints across creatures with vastly different proportions proved significantly more challenging.
Many of my reference 3D models looked sensible externally, but had questionable and inconsistent rigging (placement of joints) from an anatomical perspective.
Anatomical reference images of bones and joints in various animals were also frequently inconsistent. I could find detailed references from multiple angles for dogs, cats and horses, but not much else. For instance, depictions of crocodile anatomy varied greatly: Some showed the spine in the neck centered, while others placed it near the back of the neck.
All of this uncertainty meant I was constantly second-guessing joint placement — both when contemplating how the procedural generation should work and when adding new example creatures. I wanted to solve this one and for all, so I could stop worrying about it.
Solving the joint placement would also simplify the process of adding additional example creatures, since I could just focus on making them look right "from the outside" without worrying about joints placement. Eventually, I did largely solve it. By this point, I had established 106 high-level parameters that controled all the 503 low-level parameters.
Speeding up creation of additional example creatures
Once joint placement was mostly automated, I come up with the idea of accelerating the creation of example creatures using Gradient Descent (Wikipedia). My goal was to implement a Gradient Descent-based tool that could automatically adjust creature parameters to make the creature match the shape of a reference 3D model.
To my surprise, the approach actually worked. In the video below, the tool I created adjusts the 106 parameters of a creature to align its shape with the silhouettes of a giraffe:
The tool works by capturing silhouettes from multiple angles of the reference model (once) and of the procedural model (at each step of the iterative Gradient Descent process). It calculates how different the procedural silhouettes are from the reference silhouettes, using this difference as the penalty function for the Gradient Descent.
To measure the difference between two silhouettes, the method creates a Signed Distance Field (SDF) from both silhouettes being compared. To speed up the process, I made my SDF-generator of choice Burst-compatible (available here). For each pixel near the silhouette border (pixels with distance values close to zero) the process retrieves the corresponding pixel's distance value from the other SDF to determine how far away the other silhouette border is at that point. The penalty function sums these distances across all tested pixels in all silhouette pairs, yielding the overall penalty.
This explains why, in the video, the legs growing are the first feature to change. Increasing the leg lengths reduces the most distance penalties at once. After that, extending the neck length has the greatest impact.
Notably, the process doesn't get the ears of the giraffe right. The reference model has both ears and horns, while my generator can't create horns yet. So the Gradient Descent process, which aims to match the silhouettes as closely as possible, made the ears large and round so they effectively serve double duty as both ears and horns. I later worked around this by hiding the horns of the reference model.
I also experimented with a standard optimization method called the "Adam" optimizer, but the results were not good. Ultimately, the automated process wasn't perfect, but it complemented my manual tweaks to speed up the creation of example creatures to some extent.
By this point, I had spent three months in 2024 working on procedural creature generation and had developed eleven example creatures covering a variety of shapes. I eventually scrapped the "extracted creatures" because the combination of high-level parametrization and Gradient Descent tooling made them unnecessary as an intermediate step.
However, I was not even close to a sufficient high-level parametrization yet. Feeling the need for a change of pace, I decided to shift my focus to the procedural animation of the creatures.
Intermission
As I was writing this, I realized that while I’m convinced I haven’t yet achieved the goal of ensuring that "any random values for the parameters will always create valid creatures", I hadn’t actually put it to the test. So, I quickly wrote a script to assign random values to all the high-level parameters. These are the results:
While a few of the results look cool, most are not close to meeting my standards, as I expected. Still, this randomizer could prove useful going forward. It might help me identify which aspects of the generation are still insufficient and why, guiding my further refinement of the procedural generation.
Anyway, back to what happened in 2024.
Procedural animation of creatures
When it comes to procedural animation, I have the advantage that I wrote my Master's Thesis in 2009 about Automated Semi-Procedural Animation for Character Locomotion, accompanied by an implementation called the Locomotion System. That was based on modifying hand-crafted animations to adapt to arbitrary paths and uneven terrain.
Even before that, I implemented fully procedural (pre-rendered) animations as far back as in 2002 when I was 18.
In the summer of 2022, I tried to essentially recreate that, but this time in real-time and interactive. As a starting point, I used my 2009 Locomotion System, stripping out the parts related to traditional animation clips. Instead, I programmed the feet to simply move along basic arcs from one footstep position to the next. To test it, I manually created some programmer-art "creatures" with various leg configurations.
In 2024, I resumed this work, now applying it to my procedurally generated creature models.
The result looked somewhat nice but were rather stiff, and the approach only works for taking small steps. As I've touched on before, animating procedural, mammal-like creatures to look natural is a tough challenge:
- Quadruped mammals like cats, dogs, and horses move their limbs in more complex ways. Or at least, we're so familiar with their movements that any inaccuracies makes the movements look weird to us.
- Fast gaits, such as galloping, are more complicated than walking.
- The animation must control not only the legs, but also the spine, tail, neck, etc.
- Since the creatures are generated at runtime, the animation must work out of the box without any manual tweaks for individual creatures.
That's a tall order even with my experience, but hey, I like a good challenge.
My approach to procedural animation is purely kinematic, relying on forward kinematics (FK) and inverse kinematics (IK). This means I write code to directly control the motion of bodies and limbs without considering the forces that drive their movement. In other words, there’s no physics simulation involved and no training or evolutionary algorithms (like this one).
A training-based approach isn't viable for creatures generated at runtime, and frankly, I have no interest in pursuing it. The only way the animation interacts with the game engine’s physics system is by using ray casts to determine where footsteps should be placed on the ground.
Hilarity ensues
As an aside, one of the fun parts of working on procedural animation is that works in progress often look goofy. When I first applied the procedural animation to my procedurally generated creatures, I was impatient and ran it before implementing an interface to specify the timing of the different legs relative to each other. As I wrote on social media, "It might be hard to believe, but this animation is actually 100% procedural."
The system itself already supported leg timing, as it was inherited from the Locomotion System, where timing was automatically set based on analyzing animation clips. However, in the modified fully procedural version, I hadn't yet implemented a way to manually input the timing data. Once I did, things looked a lot more sensible, as shown in the previous video.
Other people's comments about the absurd animations sometimes inspire me to create more silly animations, just for fun. "Somebody commented that the procedural spider and the procedural dog are destined to fight, but actually they are friends, they are best pals and like to go on adventures together."
Around this time, I wanted to better evaluate my procedural animation by directly comparing it to hand-crafted animation. To do this, I applied the procedural animation to 3D models I had purchased from the Asset Store, comparing it to the included animation clips that came with those models.
Continuing the theme of goofiness, my first attempt at this comparison had a bug so hilariously absurd that it became my most viral post ever on Twitter, Bluesky and Mastodon. (The added music adds a lot to this one, so consider playing with sound on!)
People would inevitably suggest, and sometimes even plead, that I bring this absurd silliness into the game I’m making, for fun and profit. While I understand the sentiment, the reality is that my vision for The Big Forest is not that kind of game. There's definitely room for some light-hearted moments, but that’s not the primary focus. For reference, think of a Ghibli movie — there’s a certain kind of silliness that would fit well there, but it would need to align with the overall tone.
Incremental progress and study
I started studying my procedural animation alongside the handcrafted animations to better understand the subtle but important differences. Here's the comparison tool I made again, this time without the hilarious bug.
Even without the bug, it still looks very rough. At higher speeds, it becomes clear that the approach of simply moving the feet from one footstep position to the next doesn't work.
In real life (and in the reference animations), at high speeds like galloping, the feet don't stay in contact with the ground for most of their backward trajectories. They only touch the ground for short durations. My procedural animation didn't account for this yet. Instead, the hips got pulled down to be within distance of the feet, and that's what caused the torsos of the procedurally animated creatures to drag along the ground.
Once I tried to account for this, things improved slightly — at least in that the torsos no longer dragged along the ground.
To better make informed decisions about how far up the feet should lift, how much time they should spend touching the ground, and similar animation aspects, I developed a tool to plot various properties of the reference animations. For example, the plot below shows that as the stride distance (relative to the length of the leg) increases, the proportion of time the foot is in the air also increases. The white dotted curve represents my own equation that I attempted to fit to the data.
Below is another plot that shows the signed horizontal distance between the hip and the foot (actually, the footstep position) along the horizontal axis, and the foot's lift on the vertical axis. In the center, where the foot is directly below the hip, the lift is generally zero. Notably, the plot includes data from gaits at different speeds (walking, trotting, galloping), but the distance at which the foot lifts off the ground is fairly consistent across those speeds. So while higher speeds are associated with longer step lengths, the "distance" (relative to the creature) that a foot is in contact with the ground is not proportional to the step length. Instead, it it's closer to a constant value, relative to the leg length.
I made many plots with this tool, visualizing data from the reference animations in all kinds of ways. Some of the plots revealed clear trends, like the two above. Others resulted in a jumble of unrelated curves or dots that I couldn't use for anything. In this way, my process was (and is) very much a classic research approach: Formulating hypotheses, testing them, discarding those that don't pan out, and building upon the ones that do.
Inverse kinematics overhaul
I had noticed that many animals kind of bend or curl their feet — and sometimes the entire lower part of their front legs — when lifting them. However, my procedural animation didn't capture this behavior at all. I could hack around this by dynamically adjusting the foot rotations over the walk cycle, but it often resulted in unnatural poses.
Eventually, I concluded that I needed to revamp the inverse kinematics (IK) algorithm I was using, with focus on better handling foot roll and bending scenarios. My old Locomotion System employed a two-pass IK approach, where the foot rotation was given as input to the first IK pass. Based on the orientation of the lower leg found by the IK, the foot rotation would be adjusted — rotated around either the heel or toe — to ensure a more natural ankle angle, followed by a second IK pass to make the leg match the new ankle position. This two-pass approach worked all right for the Locomotion System, which was applied on top of hand-crafted animation. However, I found it insufficient for the fully procedural animation I was working on now.
In principle, this two-pass approach could be changed to run iteratively, rather than just twice. However, this would be computationally expensive, since the IK algorithm itself is already iterative. Instead, I implemented a new IK algorithm where the foot rotation is not a static input, but is controlled by the IK itself.
Having the IK handle the foot rotation is a bit tricky, as it must behave quite differently depending on how much weight is on the foot, ranging from none to full weight.
I made significant progress with this approach, although there’s a tricky issue: There are edge cases where multiple solutions can satisfy the given constraints. This makes the leg poses, which are state-less, sometimes snap from one configuration to another based on even tiny changes in the input positions. I have some ideas on how to address this, but I haven't tested them yet.
After incorporating the new IK system and adding logic to make the feet bend when lifted, my results looked like this at the end of 2024:
While it's still a bit glitchy and far from perfect, the bending of the feet and legs is at least a step in the right direction.
And that's how far I got so far
Both the procedural model generation and the procedural animation still have a long way to go, after spending around three months on each, and that can feel a bit demotivating. On the other hand, I've been making steady progress, even if it's slow. Writing this post has actually helped me realize just how much I've accomplished so far after all.
That said, I feel it's time for a break from the creatures. When I return to them later, I'll hopefully do so with renewed energy.
I wish I could have wrapped up this post with a satisfying milestone or a neat conclusion, but there was already so much to cover, and I didn't want to delay this write-up any further. I also think there's value in showing the messiness of creative processes and research. Let's see where I'm at when I write about the procedural creatures next time!
Procedural game progression dependency graphs
In 2022 I came up with some new ideas for what kind of game The Big Forest (working title) could be. During the year, I developed a way to procedurally create dependency graphs and also procedurally create fully playable game levels based on the graphs.
In the video below you can see the prototype I had near the end.
A dependency graph is a concept in mathematics and computer science which has been independently "discovered" by lots of game developers because it turns out to be pretty central to designing any non-linear game.
At its simplest you can think of locks and keys. A locked door has the corresponding key as a dependency to be able to progress through the door. But dependencies can also be abilities in a Metroidvania game, quest objectives in an RPG, or required inventory items for a puzzle in a point-and-click adventure.
Here's a few different articles by others that discuss what they are. Note the lack of standardized terminology. I personally use "game progression dependency graph" since the concept is applicable to all non-linear games, not just puzzles or dungeons.
- Puzzle Dependency Charts by Ron Gilbert of Monkey Island fame
- Puzzle Dependency Graph Primer by Joshua Weinberg
- Dependency graph Wikipedia article
- How my Boss Key dungeon graphs work by Mark Brown of Game Maker's Toolkit
I posted about my game progression dependency graph tech on social media (Mastodon and Twitter) throughout developing it. But when people ask me about it now, it's hard to point to posts scattered across a year of social media posts.
I've copied all those posts (nearly verbatim) into this blog post so it's documented conveniently in one place. For this reason it contains not only the conclusions at a single point in time, but also the questions I asked, my confusion, and my developing understanding of the problem space over time. Each header corresponds to a new thread. Images and videos generally relate to the text above them.
Let's start the journey.
March 30 2022
I'm slowly starting to experiment with novel generated graph structures again, here with an early and rough game progression dependency tree. I'll need to merge certain locations, turning it into a directed acyclic graph, and later generate a spatial graph based on it.
I must say I find it tricky to work out data structures for this. Which concepts should be nodes and which should be edges? And with both different types of nodes and different types of edges, should those types be represented as class types (inheritance) or just with data?
I keep having to revise my thinking about which concepts are represented as nodes in the graph and which as connections...
The graph generation now creates a directed acyclic graph rather than a tree structure. It took a long time to get the layout to be nice, avoiding crossed edges when possible and minimizing wasted space.
In the replies someone mentioned Metazelda. It looked familiar so I might have seen it a long time ago. I also did basic lock+keys for my game Cavex myself back in 2007. (Cavex eventually turned into The Cluster.)
The concept I'm working on now takes place in a bit more of an open world where areas are accessible by default and only certain places locked off. The "tunnel/dungeon carving" mindset feels like it might not be as helpful in this context, but I'm still figuring things out.
April 6 2022
If I have to spend a lot of time looking at these generated game progression dependency graphs, I might as well make them nice to look at.
I revised my thinking on the nodes again and added a "location" requirement to almost all the node types. On the first try, the resulting graph had multiple new neat ways of bending the connections, without me having changed the layout function at all. Robust algorithm I guess. :)
Unfortunately it doesn't seem as robust in avoiding crossed edges anymore.
Hmmmmmmmm
First glimpse of an idea to generate a dependency graph and a spatial graph simultaneously from the same underlying data structure.
Really, no need for distant parts of the spatial graph to repel each other quite so much. This can make the graph more curvy, more interesting looking, and more compact at the same time.
April 10 2022
Left: Game progression dependency graphs.
Right: Spatial graphs that could be the basis of where things are located in the world.
A key for a locked gate is a direct dependency, but can be located far away spatially.
Some people may be reminded of articles on squidi.net about procedural generation, which discuss how you could generate an entire game using these principles. It’s a classic resource, and those articles cover a lot of ground, some of which one will inevitably hit when trying to do procedural progression (as this article on puzzle trees also states). Light on implementation details but great food for thought.
I'm going towards an approach of generating the structures by incrementally injecting new dependencies anywhere rather than a simple recursive top-down approach. And I decided to generate both graphs simultaneously rather than as consecutive passes.
These two things combined should hopefully make it possible to inform new dependency injections both on what would be a good spot dependency-wise and a good spot spatially. That's the next thing I'll focus on.
The game progression dependency graph and spatial graph visualizations now support changing the data structure on the fly. This makes it possible to see the node injections as they happen, and exactly how they modify the graph. Alas the jiggles had to go.
I found out I can create more balanced game progression dependency graphs by switching to an approach I call ... (checks notes)
Exploding The Graph, Then Picking Up The Pieces.
The approach so far is powerful in the theoretical possibility space of graphs it can create, but it tends to only open up one new location at a time, stifling player choice. I'm struggling to find a way for the generation to embody the "just right" shapes described by Gareth Rees.
The problem definitely relates to the branching factor, though whether to focus on in-going or out-going edges or both is unclear. The question is then how to construct a DAG with one start node, one end node and n in-between nodes with a given desired branching factor.
April 18 2022
I guess I'm getting closer to something I might be able to use: Dividing n nodes into m columns and then connecting them. But I'm not entirely happy with how specific/hardcoded/restrictive this approach is. For example, this will never create connections that skip rows.
By the way, the graphs here are at a different abstraction level than the previous graphs I've shown. Here, only location nodes are considered. All the other node types can be injected and connected later in a way that respects the same dependencies.
After sleeping on it I came up with a much better approach that creates more random and organic graphs, and always ensures ingoing and outgoing edges are either 1 or 2. Just looking at these results makes me much happier than the results in the previous video.
The new approach is based on a simple graph rewrite rule I keep applying on random edges until the desired number of nodes is reached.
I may have been inspired by a chapter in Dormans Joris' thesis Engineering Emergence which I read recently after some people mentioned it.
Graph layout rewrite
At this point I took some time improving the graph layout algorithm for the dependency graph, but didn't post on social media about it. The graph layout takes cues from the algorithm explained on the Wikipedia page about Layered Graph Drawing (Sugiyama-style) and I improved my implementation by taking ideas from these papers:
- Scalable Drawing of Nested Directed Acyclic Graphs With Gates and Ports
- Simple and Efficient Bilayer Cross Counting
- A Fast Layout Algorithm for k-Level Graphs
After the layout improvements I took a six month break from the game progression dependency graph research and focused on other things for a while, before taking it up again in November.
November 13 2022
Top: Game progression dependency graphs.
Bottom: Spatial graphs that show where things are in the world.
A key for a locked gate is a direct dependency, but can be located far away spatially. Next step is making gameplay objects from the spatial graph nodes.
The graph rendering used to be based on IMGUI with ugly matrix hacks but I spent today changing it to be based on Shapes by Freya Holmer so it supports perspective and is just much nicer. It's an awesome library and the switch was very easy.
November 19 2022
"I'll just add some icons to my game progression dependency graph," I thought. Haha, except, what do the icons really represent? The obstacle or the reward? Both? One week later, I've ended up with this schematic representation.
Here's two quite similar graphs before and after the iconographic makeover. Icons inside a node represent the obstacle/medium of that node, while icons shown at the top edge of a node represent the reward/outcome.
November 24 2022
With the dual game progression dependency graph and spatial graph, I can now begin to construct a world to explore. Right now it's still looking rather abstract. ??
November 28 2022
Whee, I now have actual "gameplay" created from my game progression dependency graph and spatial graph (starting from 16s in the video). Only a few node types for now, but it's a cool milestone! ????????
The game will be focused on exploration, paying attention to the environment and finding clues in it about how to progress.
A note on the spatial graph. The spatial positions of elements are laid out based on a node relaxing / repulsion algorithm, and then Voronoi cells are created at each position and walls created between cells that don’t belong to the same location.
November 30 2022
Every gate, key, creature etc. now has a unique generated pattern to identify it by, so I could get rid of all the letters. One step closer to a world full of visually depicted clues.
Adding some trees. Trees make everything 1000% better.
December 3 2022
Generating a strange walled garden full of secret clues, based on a game progression dependency graph.
Someone noted in the replies that the "kitty keys" are an unusual concept, and that they couldn't think of an example where you need item A to lure creature B to point C to unlock gate D. I don’t know of that exact constellation elsewhere either. In some animes (and also The Fifth Element) a human is a key. And in the game Rime there’s some robots that serve as keys. I thought animals could be a fun variation on this already strange theme.
December 19 2022
Why did I implement this mechanic!? It'll just reveal I'm terrible at remembering things! Anyway, just a few new mechanics implemented for my strange walled garden that's procedurally generated based on a game progression dependency graph.
December 23 2022
Playing an instrument and finding songs with curious powers in this strange garden. (The game progression dependency graph it's procedurally generated from is shown at the end.)
End of prototype
At this point I stopped working on this prototype. As a proof of concept it had succeeded with the successful generation of fully playable little levels with a variety of gameplay mechanics and clue types.
The limiting factor was no longer the dependency graphs themselves.
One limiting factor now is the iconographic gameplay. Different creatures are all little cat head icons only differentiated by different colored patterns. For things to be more evocative, immersive, and easy to remember, I need to actually generate 3D animals of a wide variety. So that's the next thing I started working on, though out of scope for this blog post.
Another limiting factor is that I envision exploration to play an important rule in making the game satisfying to play, but the aesthetic of the prototype does not make exploration interesting at all. Luckily, another aspect of the game I've been working on is beautiful terrain generation. So eventually I need to integrate the procedural progression gameplay into those generated landscapes. But again, I need to first put work into creating procedural 3D models of the various gameplay elements before it can all be meaningfully integrated.
I hope you enjoyed this chronology! If you have any questions, let me know in the comments. And if you want to follow the ongoing development of The Big Forest, check out the social media links in the menu, or copy-paste my blog URL into your RSS reader.
The Big Forest
I made a video of it here. Enjoy! If you want to learn more about it, have a look at this thread on the procedural generation subreddit.
Creating natural paths on terrains using pathfinding
While working on path creation for a procedural terrain, I had the problem that the generated paths would keep having too steep sections, like this:
It was too steep and also didn’t look natural at all. I kept increasing the cost multiplier for slopes, but it didn’t help.
Then it hit me: My function just penalized the vertical distance, but it didn’t make any difference if this vertical distance came gradually or all at once.
So in fact, my cost function wasn’t trying to avoid steepness - rather it was trying to make a path where the altitude changes monotonically. It would do everything it could to avoid the path first going up and then down again.But I didn’t care if the path went a little up and down, as long as it wasn’t too steep at any point. To achieve this behavior, I needed to penalize steep slopes more than linearly, for example by squaring it.
This has the effect of penalizing abrupt changes in altitude and reward gradual changes.
And sure enough, after the change the generated paths avoided steepness and looked much more like what humans would create.
Tweaking pathfinding cost functions is one of those odd little things that I really enjoy. Seeing a little change in a formula imbue a generated creation with what could be mistaken for human design is really fascinating and fun!
Further notes
The observation-turned-blog-post in its original form ended there, but I've compiled some further notes for those who want to dig into the details.Pathfinding method
Let me tell about the method I use for the pathfinding, since I was asked about this. I won't do an introduction to pathfinding in general here but assume understanding of the principles of performing pathfinding using an algorithm like A* or similar on a graph of nodes connected by edges.Such a graph can be represented in many ways. Sometimes it's a data structure with explicit data representing all the nodes and edges and how they're connected. Other times it can just be a grid (like a 2D array) and each cell is implicitly connected to the neighboring cells - maybe the 4 or 8 neighbors, depending on whether diagonal connections are used.
It doesn't really matter, and a pathfinding algorithm can typically easily be modified to work with one or the other. Apart from giving it a start node and goal node, the important part is that you can tell the algorithm:
- Which other nodes are a node connected to?
- What is the real or estimated cost of getting from one node to another?
For the terrain pathfinding I do the latter. In fact, there is neither an explicit graph, nor any 2D array. There is no data structure at all for the pathfinding to happen inside. Instead, it's all implicit, based solely on coordinates. I tell the pathfinder what the start and end coordinates are, and there's a function for getting "neighbor coordinates" to a given coordinate. There's also a function for getting the cost of getting from one coordinate to another, as you saw earlier.
This may sound completely free-form and magical at first, but there still is a structure that must be adhered to. You must imagine a grid structure and ensure the coordinates always fall within this grid. In my case it's a plain quadratic cell grid where each cell has a size of 5. So the start coordinate, goal coordinate, and every provided neighbor coordinate must always have x and y values that are multiples of 5. You also shouldn't use floating-point numbers for this, since they can produce floating point precision errors, and even the slightest imprecision can cause the pathfinding to completely fail.
I wanted my paths to be able to have a natural, non-jagged look, so I wanted edges to come in 16 directions instead of the basic 8. The 8 additional directions are achieved by going two cells out and one to the side. This provided me with an interesting choice of whether the 8 other directions should also go two cells out, or just one.
In theory the second option can be weird, since if you need to move just one cell the path have to first side-step by two cells. But in practice both seems to work fine. The first images in this post were made with the first option but I later decided to use the second to avoid the path having very small-scale zig-zags.
Effects of different parameter values
I got asked on the proceduralgeneration sub-reddit:How rapidly does the path change as you increase the power from 1.0 to 2.0? What happens if you go past 2.0? Does the path eventually have to spiral around the mountain or something?I had actually been content just using the values I had found which seemed to work well enough, but now that I'd been asked, of course I wanted to find the answers too! I tried doing the pathfinding with the power values 1.5, 2.0 and 3.0 and with the multiplier values 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, and 25. I had moved the multiplier inside the power function since the original version of the code, so those multipliers are multiplied onto the steepness before the resulting value is raised to the given power. Here's a table of the results.
Some notes on the result.Overall the common theme is that the results range from straight and boring to wildly tortuous. At the extreme end, the path begins to create loops - something that should be impossible with path-finding. However, the edges I use in the path-finding can cross each other. This means that they can appear to loop even though they never pass through the same points from the perspective of the path-finding. They only begin to do this once the path-finding is so extremely sensitive to tiny changes in altitude that the small difference in altitude between one of two crossing edges is enough for it to exploit it to loop around. I should say that I only sample the altitude at the end-points of each edge, which appears to be fully sufficient except in the extreme cases like this.
Note that there are very similar occurrences across the different power values. For example, multiplier 10 at power 1.5 looks just like multiplier 6 at power 3.0, and multiplier 7 at power 2.0 looks just like multiplier 5 at power 3.0. Does this mean that any result you can get with one power value, you can also get with another? That there exists a transformation that means they're mathematically equivalent? No, I don't believe so. It feels like there's subtle differences. For example, the progression of paths with power value 3 begins to do loops before it begins to take a major detour, while for power value 2, the loops only start happening after it has begun doing a large detour. The differences are very subtle though and hard to put the finger on exactly.
One thing that's tempting to look for is qualitative differences, such as some paths doing many small zig-zags and others doing larger swoops. However, I think that's a red herring. The algorithms doesn't measure sharpness of turns or frequency of turns in any way and shouldn't be able to tell one from the other. I think that the seeming qualitative differences are thus up to unpredictable aspects of how the path-finding interacts with the terrain height function that sometimes just happen to produce one result or the other. To answer it in terms of the original question: If the terrain was perfectly conical, a path from the base to the top might equally well form a spiral, a zig-zag pattern, or any other combination of left-winding and right-winding sections.
My own pragmatic takeaway from this is that sticking with just a power value of 2 seems fine and I'd then use multiplier values between 3 and 15 depending on how straight or tortuous I want the path to be.