Waveform Collapse Part 1

Here’s a picture from a project I’ve been tinkering with for a few weeks. 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 as¹

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:

• The rendering still looks a bit off. It’s a rough pass at PBR but I’m pretty sure there are some bugs in there.
• It would help if there were a ground in the scene. Adding a ground plane and an environment map would help to sell the image a bit more.
• Because you see the castle build up piece by piece, it is pretty obvious that it is hollow. It would be great to compute the entire waveform collapse at once before rendering the castle to keep the illusion of solidity.
• Everything is too square and pointy. Adding bevels (real or otherwise) can help loosen that up a bit.
• No variety. One of the great things about WFC is that you can substitute a large number of chunks as long as they match up on the seams.
  It should be easy then to have walls with windows or doors, pieces of rock that stick out and all kinds of small variations that could sell the scene a bit better.

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…