Adventures in Wave-Function Collapse 1: Super-Tiles

Recently, I have been spending a lot of time trying to implement the Wave Function Collapse algorithm to generate tilemaps.  I think Robert Heaton does a great job of explaining what the algorithm is, but I still needed to figure out a lot when implementing it with tilemaps.

This post is the first in a set to document for my future self some of what I learned, so I don't fall into the same traps when I inevitably return to it further down the road.

• Tiles in bitmap version → super-tiles in tilemap version  
• An individual tilemap tile is equivalent to a pixel, so super-tiles are collections these tilemap tiles

The significance of the size of the super-tiles wasn't clear to me until I tried out different sizes.  The super-tiles I used were square, but in the discussion here I only consider a single dimension to try and make things clearer.  (I also ignore the fact that when the super-tiles are produced, they are usually allowed to wrap from one edge of the template to the other.)

For example, here is a horizontal line of  4 tiles (a top-left-corner tile, two top-edge tiles and a top-right-corner tile.  (tiles from Buch's public domain tiles on OpenGameArt)

 

If you have this across your input template and choose a super-tile size of 4, you will only ever get top-edges that are 4 tiles long.  This is because the only allowed tiles to the right of the top-left-corner are two top-edges and a top-right corner.

With a super-tile size of 3, you have two super-tiles, but the same problem.  Each top-edge tile must be only 1 or 2 tiles from a top-right-corner tile, because the only two super-tiles you have each have a corner tile in them.

There are two ways I know of to generate any-width rooms: reduce the super-tile size to 2, or widen your template by inserting another top-edge-tile.

 

Method A: Reducing the super-tile size to 2

This produces three super-tiles:

1. Top-left-corner and one top-edge
2. two top-edge tiles
3. Top-right-corner and one top-edge

Now the adjacency rules only dictate that the top-right-corner is next to a top-edge, but nothing beyond that.  Similarly for the top-left-corner.  Most importantly, super-tile 2 removes the requirement that top-edge tiles are anywhere near corner tiles.  This allows you to have rooms with top edges as wide as you like.

This also has a side-effect though.  Any patterns from your template tilemap
that are 3 or more tiles wide are effectively thrown away.  For instance, if you have paths coming out of those rooms, they can now be present with only one tile between them.  This can lead to disconcerting patterns like this (junction tiles have been adapted -poorly- by me from Buch's original):

If patterns like this aren't a problem, then you may have found a solution!  However, having super-tiles only 2 tiles wide can slow down the generation process later.

 

Method B: Widening the template

Making the template one tile wider also cures this problem:

This template is a top-left-corner, three top-edge tiles and a top-right-corner

This also produces three super-tiles:

1. Top-left-corner plus two top-edges
2. Three top-edges
3. Top-right-corner plus two top-edges

Super-tile 2 allows for rooms of any width that is 4 or higher.  It cannot produce a room three tiles across because each corner must have two top-edges next to it.

So to have a 3-tile wide room with a super-tile size of 3, you would need to include both the above template and a template which has a top-left-corner, single top-edge and top-right-corner.

When you factor in the idea that you might want to generate doors as well (which would have to be two top-edges away from a corner unless you include another section to your template), the templates can start to grow pretty large.  My experience of large tilemap templates was that unexpected and unwanted patterns started creeping in because it was increasingly difficult to predict how the template would be analysed.

Plus, large templates make for longer analysis to produce the super-tiles and adjacency rules.  You could hand-code the adjacency rules (which to me seems to defeat the point of WFC in the first place), or you could pre-compute the adjacency rules and just load them at runtime.

Further possible developments:

• Non-wrapping templates
• these might be easier than wrapping ones when it comes to predicting resulting patterns in the map
  
• Combining multiple templates
• Having a simple template that works is great, but adding more to it can break it.  It would be really nice to be able to test multiple small templates to make sure they work individually, then combine them into a giant super-tile/adjacency rule set.  
• It might also give more flexibility with map features.  For example, one level might be normal dungeon, then the next could be dungeon with water features and bridges, a third a normal dungeon but with stairs, a fourth combining all the above, and so on...
• Flexible super-tile sizes
• If there are multiple templates, it should be possible to have some templates analysed with larger super-tiles.  That would create some complexity in the implementation, but might allow for certain large set-piece templates to be included in a wider WFC-generated map.