WaveFunctionCollapse as simply as possible

WaveFunctionCollapse¹ (WFC) is a procedural generation algorithm based on maintaining local similarity. This means that in small regions, its outputs look similar to its inputs, but we can still generate unique global arrangements.

WFC can be used in game development, to generate random 2d maps from a tileset, or occasionally even in 3d. However, here we’re going to attack it as simply as possible, and go through the main ideas of WFC that hold up in 1d.

At the end we’ll be able to generate lines of text that look like these examples:

[--][--]    [--][-][---][----][-] [----] [-]  [-----]
[---------]  [---][----][-]  [-] [-] [-]  [-][---] [--][-]
[---][-] [----] [-] [----][--][-][---]    [--][-][--]
[-][--]  [---] [------]  [-----]  [--][-]  [---]  [-]
[--][-][--][-][-][--] [--] [----]   [---][--][---][--]
[-]   [----]    [-]  [------][--][---][-][-][-][-]  [-]
[--]     [--][-] [-][---------][-][---][-][--]  [-][---][-]
[-]  [--]   [--] [-]   [---][--] [--][-]  [--] [--][-]
[----]       [-][--][-] [---][-------][-][----] [-]
[-]     [---][-][-]    [----][--] [--]  [-][--][---]

Superposition

The name “WaveFunctionCollapse” is inspired by quantum mechanics, but the algorithm doesn’t really have all that much to do with it. We can imagine that at the start, our final generation exists in a “superposition” of all possible states. As the algorithm works, we “collapse” regions of the generation into certainty (i.e. we know which tiles we’ve already placed), and then use the information from certain regions to tell us what possibilities remain for the unknown regions.

For an example, let’s build up a one-dimensional list of characters (a string). Our building procedure is recursive: we take what we’ve built so far (the “known” regions) and use it to build up more.

The type of build will be:

build :: String -> IO String

Our main function then, can just take the results of a build and print that line. Our first rule for how characters fit together is embedded here: we always have a ] as the rightmost character of a line. We could have instead picked randomly, or started at a random spot in the line, but let’s keep things simple.

main :: IO ()
main = putStrLn =<< build "]"

Shannon Entropy

Another principle of WFC is that we collapse regions with low Shannon entropy first. Basically, this means we want to start with the regions where we currently have the most information (or the most constraints) about what they can look like.

In one dimension, this is a little bit trivial. Since we’re building our list from right to left, the region where we have the most information will always be on the rightmost edge of the unknown area, where it touches the known area. So this low-entropy frontier simply moves from right to left as we build up the list character by character. In two or more dimensions, you would have to do a bit more searching.

Given the partially-generated line below, with ? representing the unknown region, it becomes obvious we want to work from the ?- towards the left.

??????????????????????---][--][-][---]    [--][-][--]

Sockets

There are several ways to define the allowed “connections” between nearby tiles (in our case, nearby characters). My favorite is to think of them as sockets. Following these socket rules is where the bulk of the local similarity comes from. The “inputs” to our version of the algorithm, rather than being a sample bitmap, will be the list of possible character pairs embedded in these socket rules.

For example, if we’re working next to a - character, we know that there are only two possibilities. We can either extend the line of - with another -, or we can end it with a [.

Similar rules apply to every tile, and essentially arbitrary complexity is possible. In a more complex WFC example, tiles might depend on other tiles two or more spaces away, extending the notion of “local” similarity to a broader region.

Also note that not every tile has the same number of sockets. A ] can only ever have a - to the left of it. So, if we see a ?], we can immediately collapse to a -].

We define these rules in code via a mapping from current tiles to the allowed set of next choices.

connections :: Char -> [Char]
connections ' ' = [' ', ']']
connections '[' = [' ', ']']
connections '-' = ['-', '[']
connections ']' = ['-']

Random Collapse

When we run out of information to use, we need some way to proceed. WFC does this through randomness—by randomly selecting a choice from the allowed choices.

Once again, more complex variations are possible. A common example is to use weighted randomness rather than selecting with equal probability among all choices. This can push generated output to more strongly reflect certain subsets of the tiles.

randomElement :: [a] -> IO a
randomElement l = (l !!) <$> randomRIO (0, length l - 1)

Generation

Given the pieces above, we can now build our character list from right to left, selecting randomly among possible connections for each character, and ending up with a nice rule-obeying string generator.

To prevent the output from being infinitely long, we include a rule that if the line is over length 50, we stop generation. In this case, rather than a fixed line length, I opted to have lines always begin with a [ character, which is another fairly simple rule to express.

build :: String -> IO String
build l@(x:_)
  | length l > 50 && x == '[' = pure l
  | otherwise = do
      c <- randomElement $ connections x
      build (c:l)

Final Result

The full code is under 25 lines:

module WaveFunctionCollapse where

import System.Random (randomRIO)

main :: IO ()
main = putStrLn =<< build "]"

connections :: Char -> [Char]
connections ' ' = [' ', ']']
connections '[' = [' ', ']']
connections '-' = ['-', '[']
connections ']' = ['-']

randomElement :: [a] -> IO a
randomElement l = (l !!) <$> randomRIO (0, length l - 1)

build :: String -> IO String
build l@(x:_)
  | length l > 50 && x == '[' = pure l
  | otherwise = do
      c <- randomElement $ connections x
      build (c:l)

[----] [--][--][--][-] [--][-][--] [-][-][-]  [-][-]
[-] [-][---][-][-][--][--]    [-]  [-][-][-----] [--]
[--][-][-----]       [-]      [--]       [-][-][--]
[---][-][-]   [-] [--][-] [----][---][-][-][-] [--]
[----][-] [--]   [---][-][----]     [--][-][--][-----]
[--][----]  [--]     [-]   [-----][--] [-]  [-] [-]
[-]   [--][---] [--][--]  [-][--] [-][--][--][----][---]
[----][-][-][-]   [--][-] [--]  [-]    [-][--][---][--]
[--] [-]      [-][-][-][-][-][-] [-] [--][--][-][-]
[--][------][-]  [-]  [---][--][-][---][-][--][-][---]