Waveform Collapse Part 1

Here’s a picture from a project I’ve been tinkering with for a few weeks. A screenshot of a castle Scroll to the bottom for a moving version.

An Introduction to the Algorithm

The idea of this algorithm is to use Wave Function Collapse to construct a natural feeling castle shape in 3D. I’ve tinkered with WFC a few times in the past but this is my first attempt at implementing it on a 3D grid (as opposed to a 2D image).

At its heart, WFC is a constraints solver. You divide your object into chunks and describe how they can fit together. In our case, chunks pieces are bits of castle wall such as “a corner” or “a wall with crenelations”. Our restrictions are statements like “a wall with crenelations can only be placed over a vertical wall”, or “corners must be continued by other corners or walls”.

There are a lot of these statements (you also have to consider what can’t be placed in certain spots in relation to other chunks) — 2116 for our castle. Describing them becomes slightly easier when you realise that everything has a rotational symmetry (walls can face East, South, West or North). Even so, it is very easy to run into contradictions when you are building the rulebook. The code I wrote to describe the castle is almost 500 lines long and consists of such cryptic statements as1

set_to_y_plus(&mut adj  , corners     , corners_internal     , true);
set_to_x_minus(&mut adj , corners     , corners_internal     , true);
set_to_y_plus(&mut adj  , corners_top , corners_internal_top , true);
set_to_x_minus(&mut adj , corners_top , corners_internal_top , true);

Its not neat and I hope never to have to tinker with it again, but it works.

The Base Shape

One of the problems I had was that the castle ended up almost entirely square. While it is certainly true that a quick search of the term “castle” gives some pretty square buildings, that isn’t really what I was going for. The solution to this is a fun little trick I saw a while ago that generates interesting random 2D caves. The idea is to set up a random grid of “alive” and “dead” cells and then to run a few rounds of a game similar to Conway’s Game of Life. The rule is that a cell is born if it has more than five living neighbours and dies if it has fewer than three. Take a look here for a more clear explanation and some good animations.

In our case we get a ground plan that looks like this:

oooooooooooooooooooo
oo......ooo........o
o........o.........o
o.....o............o
o.....oo...........o
oo....o...........oo
o..........o......oo
o..........oo...oo.o
o...............o..o
o..................o
o..................o
o..................o
o..................o
o..............o...o
o.......oo.....oo..o
o.......ooo........o
oo.................o
o..................o
o....o..o.....o...oo
oooooooooooooooooooo

A cell is full if we may not build on it (such as the borders) and empty if a wall can be placed there. You can see how the very long straight edges of the area are broken by occasional bumps that force the castle to be irregularly shaped.

The Pretty Pictures

Here’s a progress demonstration:

Things to work on

The above is still very rough and there are some quick rendering gains that I am looking to get:

However, a lot of work has gone in to getting this far, and I wanted to drop a progress marker here. Its always good to have a “before” image…


  1. This code describes how external corners and internal corners of walls may join together, as well as the same for their crenelated cousins. The functions actually encode four constraints each, since the four rotations of the statement are true. ↩︎