A cool technique I’ve wanted to write up for a while is “Fractal Coordinates” described in a paper by Peter Mawhorter. Don’t be scared by the name, it’s essentially a variant on quadtrees that covers the entire 2d plane. Fractal coordinates have some interesting properties that are useful for procedural generation.
VoronatorSharp is a C# library that computes Voronoi diagrams. The Voronoi diagram for a collection of points is the polygons that enclose the areas nearest each of those sites.
Voronoi diagrams have applications in a number of areas such as computer graphics.
I’ve usually referred to this technique as “editable WFC“. It’s a combination of autotiling and WFC, and contains the best of both:
Being an autotiler, it allows users to easily and interactively make changes to an existing level.
Being constraint based, it automatically ensures that those changes are consistent with the predefined rules of the constraints, potentially making further changes to the level to make it fit
This is different from most other autotilers, which either require manual configuration of patterns used to enforce good behaviour, hidden layers, or come with more stringent requirements on what tiles are available.
I’m going to share with you a technique I’ve found for doing lazy, reliable, deterministic, constant-time infinite generation of tile based levels using Wave Function Collapse (WFC). But first, let’s cover some background, Modifying in Blocks, and lazy chunk based infinite generation.
Last article, we were comparing WaveFunctionCollapse (WFC), and Model Synthesis (MS). These are both similar procedural generation techniques that work along similar lines. Specifically, they generate a grid of tiles (or pixels), using a set of hard constraints, and some generalized solver technique to find a solution, a set of tiles that satisfies all the constraints provided. Let’s call this overall class of thing constraint-based tile generators.
The techniques have been pretty popular in recent years, and part of that is because it’s actually a very easy concept to experiment with and extend. Many of the more practical examples in the wild include their own extensions, as basic WFC tends to produce levels that look a bit repetitive and structureless.
Today I thought I’d do a review of all the different ways that you can customize this generation technique, showing how WFC and MS are subsets of a greater class. The whole family of such algorithms is much larger and I think there’s a lot of potential still to explore.
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.