Originally published April 14, 2025. Updated October 11, 2026 for clarity and context. This describes an earlier GGG prototype, not a currently released Unity asset.
Every level in the prototype was supposed to feel deliberately designed. There was just one catch: I didn’t want to hand-design every level.
I wanted a generator that could introduce surprise without producing an incoherent pile of rooms. So I started with a combination of Voronoi diagrams, geometry cleanup, and graph traversal. The algorithms did the heavy lifting. I supplied the questionable judgment.
Start with Voronoi regions
A Voronoi diagram divides a space among a set of points, often called sites. Each region contains the positions closer to its site than to any other. Scatter the sites differently and you get a different collection of regions.
One approach to constructing the diagram is Fortune’s algorithm, whose standard theoretical time complexity is O(n log n). That was appealing for a generator that might need to lay out many regions. The complexity bound isn’t a performance benchmark for this particular prototype, though: actual runtime depends on the implementation and the work we do afterward.
The first output wasn’t a level. It was a collection of candidate spaces.
Turn awkward polygons into usable rooms
Voronoi regions are great at dividing territory. They’re less cooperative when you want straight walls, predictable corners, and corridors a player can navigate without constantly catching on geometry.
The prototype converted those irregular boundaries toward rectilinear, grid-aligned room shapes, adjusting edges and filling gaps as needed. The idea was to retain some of the varied layout while producing spaces practical for gameplay.
Imagine asking a geometry problem to build a house. Then explaining that the doors should lead somewhere.
Handle overlaps before they become gameplay features
Transforming the regions introduced another issue: candidate rooms could overlap or leave ugly little slivers.
I used a deliberately simple placement rule. Earlier accepted rooms took priority; later rooms had to fit around them or be rejected. That reduced conflicting geometry, although it also meant the order of placement influenced the final layout.
That tradeoff is worth calling out. A deterministic rule can make generation easier to reason about without necessarily producing the most interesting possible arrangement.
Connect the rooms with a graph
Even beautiful rooms are useless if the player can’t get from one to the next.
Once candidate rooms were in place, the prototype treated them as nodes in a graph and used depth-first search (DFS) to traverse potential connections and establish doorways. Starting from a chosen room, a traversal-based connection plan can produce a reachable layout when every room is represented in a connected candidate graph and the required passages are actually created.
The start room was tagged as the player’s entry point, and the last room visited by the traversal was used as an exit or boss-room candidate.
One correction to the original write-up: the last room visited by DFS isn’t necessarily the farthest room, nor does DFS by itself create a difficulty curve. Progression and pacing would need their own design rules. Graph theory can keep the doors connected; it can’t make the boss fight interesting.
Structure with surprise
The objective wasn’t randomness for its own sake. I wanted variety while still preserving a readable path through the level.
The prototype explored three useful principles:
- Separate shape generation from playability. A mathematically valid polygon isn’t automatically a good room.
- Make overlap resolution predictable. Clear rules help prevent geometry conflicts and simplify debugging.
- Validate connectivity explicitly. A level should be traversable, not merely look connected from above.
These were design goals and experiments, not claims that the algorithm solved every issue. Good procedural generation takes iteration, testing, and often a fair amount of manual judgment.
What this taught me about building systems
Although this experiment predates GGG’s current modular Unity tools, it reinforced a lesson that still shapes the platform: separate responsibilities and define the boundaries between them.
Generate candidate regions. Normalize them into rooms. Resolve conflicts. Establish connectivity. Validate the result. Each stage has a specific job, and each can be improved without rewriting the whole pipeline.
That’s the same kind of thinking behind keeping Inventory independent from Equipment, and connecting them through an optional integration instead of welding the two together.
The procedural-level prototype isn’t one of our currently available Asset Store packages, and it isn’t a promise about the next game. It’s part of the engineering history that got us here.
If we revisit procedural generation, the geometry will probably still find ways to offend me. At least we’ll have a better idea which system to blame.
— Guts Glory Games