I’ve written a lot about Wave Function Collapse. Developed in 2016 by Maxim Gumin, it’s an algorithm for generating tilemaps and pixel textures based on the constraint solving with extra randomization . But did you know most of the key ideas come from a paper written a full decade earlier? Today, we’ll be looking into Model Synthesis, the 2007 PhD dissertation of Paul Merrell, and some of the elaborations he’s designed, particularly Modifying in Blocks.
Autotiling is a system for automatically picking which tile to place on the map, based on user input. It’s a fast way to design levels without having to fiddle with every tile indivually to ensure they are all consistent. Autotiling becoming increasingly well supported by game engines.
While there’s not a great deal of standardization at the moment, I’d say that 90% of systems at the moment are based on marching squares, which chooses between 16 tiles based on user input at each corner, or blob, which chooses between 47 tiles based on user input on each tile. For example, Godot’s Autotiling system or Tiled’s Terrain brush. I’ve written about these and other schemes before.
These approaches do work quite well for quickly whipping up a level, after the initial slog of creating the tiles, but when you start getting into more complex cases, a major shortcoming appears: combinatorial explosion.
Basically, as autotilers chose one tile for each situation, there needs to be a tile ready for any given combination. It’s bad enough creating 47 tiles needed for the blob pattern, but that only handles transitions between two different terrains. If you add a third, you need hundreds of tiles. And even simpler patterns quickly blow up with a few terrains.
Previously we considered the Arc Consistency 3 and Arc Consistency 4 algorithms, which are an essential component of many constraint solvers. I’ve been using AC-4 myself for some time, and I naturally got curious as to what other improvements can be made.
Diving it, I discovered there is a huge amount of papers with new innovations are refinements on these two fundamental techniques. I’m going to attempt to summarize them there, and maybe later experiment with them in my own software, but I’m afraid this article is going to be pretty niche.
I’ve been doing a lot of experiments with WaveFunctionCollapse, which as we’ve covered before, is essentially a constraint solver turned into a procedural generator.
The underlying solver WaveFunctionCollapse came with is called Arc Consistency 3, or AC-3 for short. But AC-3 is actually one of a whole family of Arc Consistency algorithms. Today, my solver and most others uses AC-4, a more advanced algorithm. Let’s talk a bit about how those both work.
You are probably familiar with Recursive Subdivision – also known as Binary Space Partitioning – as a procedural generation technique. Like all the best proc gen, it’s a simple idea, that produces complex output. I’m here to discuss some variants that others have used to produce interesting results.
I’ve been working a lot on Tessera. I presented a paper at the most recent PCG Workshop of FDG, where I explain how Tessera makes WaveFunctionCollapse somewhat less daunting, and go into some of the details of its features.
That may not be news for users of the software, but here I explain how things work, and what parts work well / I’m especially proud of.
WaveFunctionCollapse (WFC) is a procedural generation technique for creating images and tile-based levels. I’ve discussed it many times before.
As a technique, it has some pros and cons. Pro: it’s almost uncannilly good at stitching together tilesets into interesting arrangements, and is pretty good at copying the style in a supplied sample image. Cons: it becomes bland and repetitive at large scales.
In my software Tessera, I’ve been working on various ways of customizating the generation to work around that con. But I’ve seen another way that turns WFC on its head. Instead of using WFC as a full level generator, we want to decide the overall structure of a level some other way, and then use WFC just for the details.
It’s rare that you see a game that gives top billing in its marketing to the quality of its procedurally generated levels. Normally PCG is sprinkled in a game to add a bit of variety, or to make up for the lack of actual level design. But, for 2017’s Unexplored, the rest of the game is there to justify the stellar levels.
Unexplored presents itself as a fairly standard roguelite – enter a randomly generated dungeon, descend 20 levels and retrive the amulet of Yendor. The gameplay features a realtime combat based around timing and aiming your swings, but otherwise plays things by the book.
But it doesn’t take long realize why they much such a big deal out of the procedural generation. Unexplored level design takes more after 2D Zelda games than it does Rogue. Instead of just wandering at random, you quickly find that the path forward is blocked, forcing you to solve puzzles, find items and keys, defeat enemies to continue. There’s a huge variety of structure, all randomly generated, but nearly every level is a tightly packed, interesting space.
Last time, I took inspiration from a game called Unexplored, and wrote about about a system of rule evaluation called Graph Rewriting.
In developing Unexplored and earlier games and academic papers, developer Joris Dormans has over the years developed an entire software library centered around graph rewriting. It’s called PhantomGrammar, and it comes with an accompanying UI called Ludoscope (sadly, neither is publically available currently).
I think it’s worth discussing how it works, as it turns the previous theoretical ideas into something pratical to work with.
I’ve been doing this series on how games do level generation for some time, and I have a complete beauty for you.
I’ve spent a lot of time deconstructing Unexplored, a 2017 indie game by Joris Dormans. It just nails procedurally generated zelda-like dungeons, and I had to know for myself how the magic happens. Fortunately, most of the generation logic is written in a custom language, PhantomGrammar, so between that and some help from the developers, I think I’ve got a pretty good idea how it works.
The ideas of Unexplored are so interesting that I felt they deserved an article in it’s own right. The game is centered around a concept called Graph Rewriting, which, while well understood academically, is rarely used in games. I’m going to spend this article talking about that technique alone, then how PhantomGrammar specifically uses and extends it. Finally I will talk about how these techniques are put together in Unexplored to make such sophisticated levels.
