#procgen research

Space-filling tangent field

Sometimes, someone comes up with a technique that seems so obvious in retrospect that you wonder why you haven’t seen it before.

It’s not new (this ACM 2008 paper describes the technique) but if I’ve seen it before I didn’t remember it. Or maybe I just connected to the context in the right way this time.

So, what the heck is a tangent field and how can you use it to generate a city? A vector field is a field of vectors--that is, for each point in the space there is an arrow pointing in a direction, which can be shorter or longer. This should be fairly easy to understand if you’re already familiar with vectors: it’s just a bunch of vectors that each have a position in space. They can be useful for a lot of things, such as wind simulation, pathfinding, and crowd simulation.

A tangent field is a vector field on a surface, where the vectors are in tangent space--for a flat plane they’re lying flat on the ground. The city generator Stijn Raaijmakers made works by taking the weighted average angle (with the weight as 1/(r*r) where r is the distance to each tangent attractor) and generating a building there either along the tangent angle or perpendicular to it. This creates a densely packed space to sample from to give a degree of order to the placed buildings.

Packing problems come up quite a bit in procedural generation, especially where you’re trying to fill a space with content and don’t want any unsightly gaps. (There’s non-spatial applications of packing problems too, but we’ll leave that for another day.) Stijn’s generator reminded me that there’s a lot of useful research to draw on out there.

WaveFunctionCollapse is Constraint Solving in the Wild

WaveFunctionCollapse has continued to be one of the more interesting new procedural generation algorithms. People have been finding all kinds of things to use it for: minigolf courses, 3D maze buildings, poetry, and animations.

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.

Again, there are many more details in the paper itself. The paper will be presented by Adam M. Smith, my co-author, and myself at the 2017 Procedural Generation Workshop this August.

Procedural Generation in Game Design

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.

Phase-Functioned Neural Networks for Character Control

For most games with animated 3D characters, a lot of time is spent linking the animations with the character’s motion, often using complex state machines that create webs of animation transitions.

This research, by Daniel Holden, Taku Komura, and Jun Saito, instead used a neural network to act as the character controller. The neural network is trained on a large dataset of animations and terrain data, taking gigabytes of data and combining it into a function that runs quickly and uses only a few megabytes of memory.

There’s been some past research in this area, but based on the video of their results their phase-functioned approach is very, very effective.

This is the exact kind of generative tool that can empower artists. It still needs the artistic input (that animation data has to come from somewhere) but it takes care of the very tedious work of combining all of those animations, freeing the artists to produce even more art. (And the technical artist can go improve some other tool.)

And, since the training is offline, rather than while the game is running, the risks of training a neural net can be supervised, so the game can ship with just the resulting locked-in function.

Priorities in Generation & Generalizing from Examples

I finally got around to playing Invisible Inc this week (you don’t want to see the length of my to-be-played list) which prompted some thoughts about your goals while designing a generator.

The levels in Invisible Inc don’t even try to be realistic. They’re assembled from rooms and corridors in a videogame fashion: here’s the goal, there’s the exit, sprinkle in some guards and gated paths in between. It’s not simple: it knows to place rewards in dead ends, plan out guard patrol paths, and hide cameras in clever places.

The downside is that the logic of the levels isn’t obvious. There’s no real-world visible justification for the layout: any door can hide a prison cell or a teleporter exit. Your anticipation of what’s in the next room is limited to what you can survey, not on your learned expectations.

With the limitations of production, this was probably the right call. After all, this is part of the problem that brought down Introversion’s canceled Subversion: Subversion had some brilliant, realistic looking procedural building interior tech, but they never managed to crack the problem of making the gameplay fun.

Invisible Inc, on the other hand, knows exactly what it’s about, which let them radically rethink the stealth game. The buildings it generates might not be realistic, but they work for the gameplay.

I’d still like to see a deeper, more meaningful logic that can make more aesthetic layouts. But it has to be balanced against the primary goal of the level generator: to make playable levels.

Good underlying meaning can make better, more playable levels. But the trick is that it needs to work. Fortunately, different projects have different goals, and the cutting-edge research into procedural generation can exploit those different goals to triangulate new places to experiment.

Working from Examples

I’ll probably have more to say about Invisible Inc itself once I see more of it. My current reaction is based on a handful of generated levels, which points to another issue I continually confront: it can be hard to generalize from a handful of examples.

When I’m playing a game it takes a while for me to be sure that I’ve seen enough variation to say that I can feel the contours of the generator. Or, in some cases, that there’s generation going on at all. The same is true when I’m building a generator: since I can read the code, I can guess at the outcome, but I can’t know how much variation Virgil’s journey actually has without extensive experimentation.

GameSpace

Speaking of machine learning and mapping multidimensional space into something more comprehensible, this research by James Owen Ryan and Eric Kaltman uses machine learning to place games into 3D space, clustered near other, similar games.

You can try it out yourself (make the window wider and refresh if it asks you to reorient your device).

The project uses GameNet, a database of the links between 12,000 games, with the links learned from feeding the Wikipedia pages into a machine learning algorithm called latent semantic analysis. GameSpace maps that data into 3D space, forming a galaxy of games where nearness corresponds to similarity.

Here, for example, is the cluster of Zelda games. Note Elliot Quest down in the corner: I’d never heard of it before, but the algorithm puts it closer to Zelda II than Majora’s Mask 3D (which is further down, outside of this image and closer to the Mario games).

Not too far away, you can find the cluster of Mario games, which are a bit looser. Presumably because the Zelda games are more similar than, say, Super Mario Brothers 2 and Dance Dance Revolution: Mario Mix.

Zooming even further out, thousands of games are visible. The Infocom text adventure cluster is a little ways away, while that bright spot I highlighted on the far side of the galaxy is a tight cluster that contains Far Cry, Borderlands (including Tales of the Borderlands), the Dead to Rights games, and Peter Jackson’s King Kong, among other games.

Of note is that this constellation isn’t directly based on the games themselves, but instead is constructed from how we talk about them. (I’d like to see some  game review archives mapped like this. Or some indie game review sites, plus TIGDB. Or the Ludum Dare archives.)

I’d suggest a couple of aesthetic changes to make it a little easier to navigate if they want people to use it as a tool (the ability to orbit, to show labels at a distance, etc.), but even in its current state it’s quite informative.

You can try it out here:

An Analog History of Procedural Content Generation

Procedural generation didn’t start with computers. While computational algorithms have played a big part in today’s wide range of generative forms, many techniques can and have used analog means to generate their results.

In this paper, Gillian Smith looks at some historical examples, such as the modularity of dungeon geomorphs used by D&D, the way that sounds were designed to work in arbitrary orderings in the Milton Bradley-published Simon game, and use of algorithmic assembly in D&D encounter tables. Modularity and directed randomness are themes that cross many different generative forms. 

Gillian discusses some of the motivations take prompted people to explore procedural generation in the first place: replay value, creative assistance, and exploring a new expressive medium. These are still common goals today, but the paper points out that there is room for new goals, and that there’s room to find new purposes for using procedural generation.

She also mentions some motivations that have fallen by the wayside: having the computer as an unbiased agent, and replacing humans. These have been pretty prominent in the rhetoric of past procedural generation, but I agree that they are somewhat misguided: as Ian Bogost argues, algorithms can be, and often are, biased, and require a lot of design work. The designer is now operating at a higher level of abstraction, but it still requires the human input to shape the meaning. 

Procedural generation doesn’t replace the painter. It’s more like giving the painter a paint gun.

StyleNet

This is apparently the year for neural networks in algorithmic art. A week or so ago, Leon Gatys, Alexander Ecker, and Matthias Bethge posted a research paper entitled 'A Neural Algorithm of Artistic Style'.

Alex J. Champandard used the technique to produce the video above. He has also set up a twitter bot that will take your photos and translate them into the style of famous paintings. There is, of course, also a twitter #StyleNet hashtag for other people’s experiments.

There are already multiple implementations with source code available on Github, by JC Johnson, Brandon Amos (crossed with DeepDream), Kai Sheng Tai, Anders Boesen Lindbo Larsen, and Eben Olson.

At this point, the exploration of the artistic applications of StyleNet are still in the very early days. Some of the painting transformations are astonishingly effective, while others are less so. But they’re conceptually centered around relatively straightforward uses for the algorithm. There’s a lot of space for software artists to take this as a starting point and springboard into some totally unexpected applications.