# Tessera: A Practical System for Extended WaveFunctionCollapse

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.

Paper

# Using Unity’s TextGenerator.verts

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;
}

# Junkbot Arena

I entered the GMTK Jam again. This year, I was in a larger team, working together on the theme Joined Together.

You can play it on itch.io.

# Driven WaveFunctionCollapse

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

# Triangle Grids

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

# Dungeon Generation in Unexplored

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.

Continue reading

# PhantomGrammar and Ludoscope

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

# Graph Rewriting for Procedural Level Generation

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.

Continue reading

# Lock and Key Dungeons

Lock and key dungeons are, well, video game levels with locks preventing progress, and collectable keys that let you proceed.

The concept is a lot broader than it sounds. Locks/keys aren’t necessary physical objects, but anything that works in a similar way, which can often be quite abstract.

Once you are familiar with the pattern, you begin spotting it everywhere. It’s most prominent in puzzle games and metroidvanias, but it’s applicable to any game which has an authored progression path.

In this article, we’ll look at lock and key dungeons, then how to analyse and design them.

Continue reading