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.