I’m always looking for more practical uses for the techniques I talk about here. Not that there’s anything wrong with using them for games, but I want to broaden my horizons beyond that (and maybe bring you along for the ride).
So when I came across these articles by Jer Thorp, a software artist, they immediately caught my attention: here’s a practical, sobering use of generative design. Jer used an iterative, algorithmic process to design the layout for the names on the 9/11 memorial in NYC.
If you’ve ever been involved in designing a memorial or a tomb you might have some
insight into the weight of the responsibility. This is how we record our memories of those we’ve lost. Getting it right means a lot to the people who are still here.
There were numerous constraints on the design process: from requests from the families to the shape of the type used on the memorial. Solving them by hand would have been impossible, so a set of tools was developed that modeled the problem as a complete system and let the designers adjust the parameters until they found a design that satisfied all of the constraints–including the artistic constraints that the humans were better at designing than the machine.
In addition to the practical design use, I want to highlight the role that the constraints played: Jer contends that by considering more of the constraints and thinking of the entire system they were able to achieve a better result.
I would be remiss if I didn’t inform you that the Procedural Generation in Game Design book, organized and edited by Tanya X. Short and Tarn Adams, is out.
It’s very dense.
Each chapter covers a lot of ground.
There’s chapters on level design, expressive range, meaning, puzzles, rules, narrative, audio–just a ton of topics. By a lot of experts: It’s even got a small sidebar that I contributed.
I’d love to go more in depth
on everything it covers, but I’m still working my way through it!
Like I said, there’s a lot of stuff in here. I could do a whole post on just the first chapter, where Darren Grey lays out why you might want to use procedural generation–and just as importantly, reasons why you might not.
I rather like the concept behind this series of videos by Paul Soulos. They use image style transfer, but instead of using a photo as the content target, they use Conway’s Game of Life to drive it.
Paul Soulos has written a blog post about it. I like the discussion of using constraints as part of the design process–I think that thinking about constraints is an important part of learning to use generative methods.
A lot of artistic training is about learning what the constraints of a medium are, how to work with them, and how to overcome them. With generative tools we take that one step further: these magic paintbrushes can themselves be modified. Now we get to explore a meta-space, a space of all the images that could be produced with all the different kinds of paintbrushes. This meta-space has constraints of its own–and, on top of that, successful generative design often requires even further constraints, but this time constraints that harmonize with the goals of the generator.
You’re perhaps familiar with negative space–the empty void around an image, often just as important to the composition as the image itself.
Generators have a kind of mathematical, virtual negative space of their own, the possibility space that lies outside what it can output. This negative space often speaks loudly about what the generator is–what it could produce but chooses not to.
One of the points of the Library of Babel is that generation without constraints is infinitely everything and nothing. Each book contains every other book, if you only knew the correct cipher to translate it. Generation without constraints is endless, formless babble. You need negative space to give it structure and order.
There’s a ton of procedural generation research going on out there, and I’ve only been able to post a small fraction of it. For example, Interrupt 4: A Digital Language Conference is a two-day conference that’s going on right now and has talks by Kate Compton, Darius Kazemi, everest pipkin, Ramsey Nasser, and more.
Kate Compton’s talk above is just one of them. I do like the discussion of how constraints and limited possibility space make a safe space for interacting with the bots.
Her larger point, about the poetics of bots, touches on something I’m intensely interested in: what can we do with these generative things? We have all these amazing generative things, but I feel like we’ve only scratched the surface of how we can can use them to convey meaning and evoke feelings.
In many cases we don’t need new generative technology; a better understanding of the poetics of generativity will open up whole new spaces.
I’ve been playing Factorio lately. At first I wasn’t planning on talking about it here because I wasn’t looking for procedural generation in it. I was playing because of the emergent system. At it’s heart it’s about building an immense Rube Goldberg supply chain, so the focus is on the emergence of the interacting mechanics. But it does have procedural-generated maps. And then I read one of the developers’ recent blog posts about it, and it crystallized something I’ve been thinking about lately.
While the maps in Factorio are generated, they’re currently pretty homogeneous: zoom out a bit and they start looking pretty samey. This is a problem shared by all noise-based generators–I’ve talked about it in relation to scale and biomes–and in Factorio it means that after a certain point the terrain mostly doesn’t matter. You stop treating the map like a place with possibilities and more like a liquid with some resources floating in it.
It helps that the way I’ve framed it fits in with my existing views: that games are constructed out of gaps and clues (aporia) that you unfold with epiphanies. Chess and Go, in this view, are about ferreting out the secret implications that emerge from the rules interacting.
Factorio is similar to Chess in this regard: the long-term engagement loop is figuring out the secret configurations that invoke the magic. But along the way there is the technology research acting as a progression system, the creatures on the map fighting back, and the resources running out–which upsets your careful equilibrium.
I’ve come to see all this interactive stuff and a continuous space that shares the same design problems: the complicity Alex Kennedy describes when talking about Sunless Sea is the same kind of problem
Sidney Icarus is describing in tabletop roleplaying,
or that occurs when reading a CYOA novel, researching a tech tree, or in exploring a map.
As such, your procedural map generator has to solve the same classes of problems as you might encounter when designing a Twine game. Sometimes you’ll want a Visual Novel that just moves from moment to moment, or a map generator that fades into the background so it supports other content: that’s a valid design choice. Other times you’ll want more consequence, which calls for more context.
What you definitely don’t want is a left-or-right choice with no sign-posts and no context.
Factorio’s current map is perfectly serviceable: it’s not interesting, above a certain scale, but the rest of the systems are fine picking up the slack. Your emergent constructions help by adding player-designed texture–though after a certain point you’ll also be automating that.
However, as the developers’ discuss in their post, adding landmarks, more biomes, and adding larger-scale structure to the map generator can help give different parts of the map their own unique character.
There are many different ways they could do this: a unique resource that acts as a reward, a goal or quest to fulfill, or a difficult terrain that adds new constraints on the way to somewhere else, or just a memorable landmark that makes that spot a bit different.
But the thing I keep coming back to is that this design problem in a map generator is the same one in designing a tech tree or writing an interactive story: our games need secrets to discover. They could be hidden in the mechanical emergence, slotted in as progression content, or even be embedded with literary techniques that need interpretation to tease out. But the purpose of gameplay is to hide secrets.
If you wanted an excuse to work on some procedural generation projects, there’s a game jam going on right now that’s focused on procedural content generation for levels. Organized by Allan Rowntree, it’s just getting started, so you have time to join in now.
I’ll be interested to see what the results are when it’s done.
Amit Patel has recently been writing again: this time its about terrain generation that starts with river placement on the coast and works out the rest of the landscape from there. Because he’s working through the project publicly, his weekly posts have both the triumphs and the backtracking. It’s a useful look at some of the practical travails of building a generator.
It’s also a good reminder that there’s more than one way to do things: Amit was inspired by a research paper that sculpted terrain via hydrology. By structuring the data in a new way they could introduce user control in new places.
Janelle Shane is continuing her experiments with neural nets naming things. She’s even found a practical use for them: naming guinea pigs. It turns out that naming things with a neural net is a good way to drum up attention for animal rescue adoptions.
Generative methods are pretty useful for coming up with names. While it’s not a daily need for most of us, there are a number of practical uses for a name generator: picking project code names, creating test data, coming up with an original but pronounceable name for a drug, and–in this case–naming rescued animals.
Janelle’s posts typically have quite a lot of details about how they arrived at the output. I found the discussion of the paint colors particularly interesting, since she goes over the changes she made to try to find paint names that matched the color swatches better. If you’re familiar with neural nets some of the concepts–like temperature and using better data-sets–won’t be surprising. But it’s useful to see how they’re applied to move the output in a particular direction.
But people are still having trouble understanding how it works. While you can use one of the existing implementations and get perfectly good results, if you want to extend the algorithm or apply it to new contexts it’s been hard going. That’s one reason I co-wrote this research paper on how WFC works.
Section 4 is a walk-through of the algorithm. Starting from one 4x4 pixel image, you can see the steps it goes through. The image is broken down into patterns, cataloging each unique sub-image:
We build a catalog of the different ways these patterns can overlap. With a 2x2 pattern size, there are nine ways that can happen:
Here’s what that index catalog looks like for the first pattern, the one with three white pixel and one black pixel in the lower right corner:
At (0,0) in the center are all the patterns that exactly overlap with this one. There’s only one, of course: itself. If we instead look at the patterns that only overlap with the two pixels on the right, shown at (+1, 0), there are two patterns that fit: one with two black pixels in the bottom row, and one with a black pixel in the lower left.
With pattern sizes larger than 2x2 things quickly get more complicated:
3x3 has 25 ways to overlap, 4x4 has 36 ways to overlap, and so on.
Because we only care about unique patterns this takes less space to store than it might seem, but it still gets hard to visualize.
Note, also, the structure that this imposes on the output: a red pixel can never be next to a white pixel, because there are no pattern overlaps that allow that. This is how things like the Flower WFC example work: the flower must be at the top of a green stem and surrounded by blue sky, because those are the only valid matches for the yellow petals.
Moreover, since the 3x3 Flower patterns only have blue sky above them, the top two rows of the output will always be blue, even though the WFC code has no explicit constraints for the top rows.
With the index catalog in hand, the algorithm looks at the current output and finds the point that has the lowest entropy–that is, the point where there are the fewest possible patterns that fit. This is called the Observation step. If there’s more than one possibility there, it picks one of them at random. That’s the only place where randomness comes into the algorithm.
After Observation comes Propagation: WFC checks how many patterns are still valid for other cells in the output. The effect of one cell being fixed affects the surrounding possibilities, and often a large area will suddenly cohere into the only remaining valid configuration.
That’s the basics of how it works. There’s more details in the paper itself, of course. If you’d like to know more I encourage you to read it and let me know if you found it helpful. Or if you have questions about it.
The paper isn’t just about how the algorithm works, of course. The paper covers the history of WFC, its relationship to other similar algorithms, and–perhaps most importantly for future research–a look at how WaveFunctionCollapse can be treated as a subset of constraint solving.
By implementing a surrogate for WFC in answer set programming, we can see that we can use the WFC propagator as the constraint and turn the problem into a logic program that can be solved with an automatic solver. (Clingo, in this case.)
This lets us do things like compare different heuristics and demonstrate the importance of the constraint propagation. The experiments show that the constraint propagation means that it can work without backtracking, and only the occasional global restart. Or without constraint propagation but with lots of backtracking.
It also makes it easy to introduce new constraints on top of the basic WFC constraints. The example we used in the paper is that all the patterns in the input must be present in the output, but that’s just one possibility among many. Perhaps we want all the red pixels to be connected in a single graph by a network of blue pixels. Or, for a more concrete example, if we want to generate a dungeon level, but have a constraint that you must be able to find a path from the entrance to the exit.
