Adaptable Procedural Generation by tweaking the WaveFunctionCollapse algorithm with a Bayesian prior
What is procedural generation?
Procedural generation comprises different generative algorithms which operate under the principle of creating data algorithmically instead of manually: instead of hand-crafting whatever we want to create (a map, music, terrain…), we code an algorithm which can succesfully create different examples without the extra work of going through all the process again. This is especially useful in videogames, where the whole map or level layout can be generated randomly (for example, the maps in Minecraft, Terraria or Factorio or the level layouts in most roguelikes).
The WaveFunctionCollapse algorithm and applications
Here, we will explore the WaveFunctionCollapse (WFC) algorithm, proposed by Maxim Gumin (check his Twitter for a collection of amazing content by other developers using the algorithm!) as a way to procedurally generate images or terrain by creating images which are locally similar to an input image in terms of a predefined grid size.
The main idea behind the algorithm is to create the final image step by step and keep track of which tiles “match” the already partially constructed image. For a detailed explanation of the algorithm, we refer the reader to the original WFC Github repo and Section 4 of the article “WaveFunctionCollapse is Constraint Solving in the Wild”.
Apart from creating similar images, another use of the WFC algorithm is tilemap generation. Tilemap generation will be the main focus of this post since it is easier to use to visualize our ideas. Instead of a sample image, one can only store the tiles and the pairs of tiles which can be connected to each other and the orientations in which they can be connected. Then, the algorithm can be used to create images such as the one below.
The problem and our solution
We focus on a tilemap generation problem based on the board game Carcassonne, in which the board is “manually” generated by players as the game progesses provided that the tiles align with each other (see the timelapse below).
Surprisingly, this is conceptually very similar to how the WFC algorithm operates to create arbitrary tilemaps by adding new pieces to a partial solution in progress. And since WaveFunctionCollapse can be used as a tilemap generator, it can be used to generate Carcassone boards too!
However, in the original game there are far too many different tiles, and coding all the relationships between them was far out of scope for a 24-hour hackathon. Therefore, we decided to play with avery simplified version of Carcassonne with no castles or rivers, and only roads, grass and monasteries. This leaves 6 possible tiles and their rotations and symmetries. Even with this, the result is visually appealing and similar to how Carcassonne games play out!
The image on the left contains an example of the input rules added to the algorithm. However, we still would like to be able to control certain aspects about how the board will look. Should it create “streets” of roads full of monasteries and look like a city, or should it have mainly grass with scattered villages here and there? Under the original algorithm, there is no way to control which one of those (or any other) should be favored, but there is an easy tweak to be able to control that.
Bayesian priors
As mentioned, at each step the algorithm adds a new piece to the board in a way that matches the already placed pieces, but we have not discussed what happens if different pieces can all be placed in the selected spot (nor how to select the spot in the first place, but we won’t focus on that here!). Under the original algorithm, you choose any suitable tile uniformously at random. However, we might want to favour specific tiles, such as grass, and make them appear more often in the solution. This is done by creating a non-uniform “probability prior” on the tiles which favors grass over roads in case both of them are possible options, reminiscent of Bayesian techniques. In the simplified case where the only two options are grass and roads, we can decide to add grass with probability p > 0.5 instead of the usual 0.5 uniform probability. This is easy generalized by assigning a “priority value” to each tile and using it to assign the probability as the value divided by the sum of values of all possible tiles. In the image below you can see two suitable solutions with dramatically different values for the coefficients to give a sense on how sensitive the algorithm can do.
Another example: conditional probabilities and grouping
There is still another possible tweak that can be done using the aforementioned idea, but to better illustrate it, we will generate 2-D Minecraft Ore tilemaps instead of Carcassone boards. Ores in minecraft mostly appear in chunks, so apart from the different rarity of each ore, we make the probabilities depend on the already placed neighbors to create this effect. Even if iron next to coal is not anything “forbidden” and can happen, coal should be favored to go next to another already placed coal.
Although it isn’t the case in this image, in the game the probabilties also depend on the altitude of the tiles, so the position in the image can also be a factor that condition the probability distribution of the factible tiles.
Conclusion
Procedural generation is a powerful skill to have in your toolbelt. In particular, WFC has been used extensively in world generation, and realizing that the distribution over unseen tiles doesn’t have to be uniform and can consider other effects such as which neighbors are already placed, which tiles are about to be placed and the position in the image to create interesting effects and should definitely be considered. This was just a very simple application, but the possibilities are endless!
