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 readingWaveFunctionCollapse (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 readingLock 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
I was browsing the Apache Arrow docs and spotted a term unfamiliar to me. Intrguied, I discovered that Compressed Sparse Fibers are a new technique for representing sparse tensors in memory. After reading up a bit, I thought I’d share with you what I’ve learnt. The technique is so new (well, 2015..) it is not mentioned on Wikipedia, and I found virtually nothing elsewhere. There’s a very limited number of ways to handle sparse data, so it’s always interesting to see a new one.
Don’t worry, I’d also never heard of a sparse tensor before, so I’m going to explain things right from the beginning, assuming you have a basic CS background, and don’t mind me going a little quickly.
Continue reading
A simple guide to constraint solving
Since developing DeBroglie and Tessera, I’ve had a lot of requests to explain what it is, how it works. The generation can often seem quite magical, but actually the rules underlying it are quite simple.
So, what is the Wave Function Collapse algorithm (WFC)? Well, it’s an algorithm developed by Maxim Gumin based on work by Paul Merrell for generating tile based images based off simple configuration or sample images. If you’ve come here hoping to learn about quantum physics, you are going to be disappointed.
WFC is capable of a lot of stuff – just browse Maxim’s examples, or check out #wavefunctioncollapse on twitter, or see my youtube video.
WFC is explained briefly in Maxim’s README, but I felt it needed a fuller explanation from first principals. It is a slight twist on a much more broad concept – constraint programming. So much of this article is going to explain constraint programming, and we’ll get back to WFC at the end.
Continue reading
I’ve been experimenting a lot with constraint-based procedural generation these days. Specifically the Wave Function Collapse algorithm (WFC). I’ve even made my own open source library, and unity asset.
WFC is a very flexible algorithm, particularly with the enhancements I’ve designed, but at the same time, I’ve found it’s quite hard to actually get it to produce practical levels useful for computer games. The key difficulty is WFC doesn’t have any global structure to it, all it does it make the output generation look like the input locally, i.e. when viewing small rectangles of output at a time.
In this article, I share what I’ve learned to take your constraint based generators to the next level.
Continue readingI recently released an addon in the Unity asset store. It’s actually two addons: Tessera Pro is a fully featured copy, with complete source code, and Tessera which has cut down features, and you just get a precompiled .dll.
I quickly discovered a big problem – if you upgrade from Tessera to Tessera Pro, then all your scenes become broken. You get this error, which is likely familiar to veteran Unity developers.
I’ll go into what’s happening in general, and how I dealt with it.
Continue reading