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.
Continue reading
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.
Continue readingI’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.
TextGenerator.verts is meant to give the position information of every character in a given string. This is useful in Unity if you need to align something with exactly where some particular text is occuring, if for some reason you are not already using TextMeshPro.
Older Unity versions created 4 verts for every character, which made life easy. But now many non-rendering characters don’t have verts generated for them, and the relationship between verts and characters is undocumented. I’ve reverse engineered it, as best as I can tell:
int? GetVertForPosition(int position, string text, TextGenerator textGenerator)
{
var c = 0;
var vert = 0;
for (var i = 0; i < position; i++)
{
if (textGenerator.characters.Count <= c)
return null;
if (!char.IsWhiteSpace(text[i]) && textGenerator.characters[c].charWidth > 0)
vert += 4;
if (text[i] != '\n')
c++;
}
return vert;
}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.
Continue reading
Following my article on triangle grids, I’ve been doing a lot more thinking about periodic grids. Here’s three neat things.
Continue reading
Ah, the triangle grid. Square grids are virtually ubiquitous, laying out out everything from the pixels in an image to houses in a city block. The hex grid has a decent showing too, particularly in board games. But triangle grids – regular tilings of the 2d plane with equilateral triangles – just don’t seem popular. I’ve seen claims they are useless, or that the maths is hard. But I’m here to prove both of these are wrong: the maths is actually easier than working with hexes, and triangles have all sorts of neat advantages.
I’ve worked out all the maths in my reference code on github, but it’s worth explaining why and how to use these grids.
Continue reading
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.
Continue reading
