Procedural Generation with Prefabs: Wave Function Collapse

A couple of weeks ago, I came across a procedural generation algorithm for taking a small sample image to generate a large image with the same characteristics. Maxim Gumin has created what seems to be the main repository that others use when explaining this system. I decided to make an attempt at it using Unity and prefabs to generate an environment. This and the next articles will be going over this as I develop the code for it and expand on the idea.

One thing to note before getting started, this algorithm as written is not guaranteed to produce ‘perfect’ mazes, where any point can reach any other point. I’ve written about another algorithm that can do that here. If you are looking to remove any disconnected sections, you will need some thing to make a second pass of the result. I will look at exploring that later.

To start, I created a Scriptable Object to allow for ease of creation of new tile types as well as give the algorithm something to handle other than a prefab directly.

This Object will consist of a Prefab (could be an array for more variety among the tile types), an array of Ints that describe what each edge can match with, and a Bool to see if it gets re-randomized. The Bool is there to assign to dead-end tiles so that the user can reduce the chance of it being placed without changing the odds of the others.

The next part is the Grid Module, or Tile Module, and is the representative game object for each gird point in the pattern. Let’s take a look at the variables that it uses.

_validTiles is a list of all the current valid tiles. And when a tile is no longer valid, it is moved to _invalidTiles so the Scriptable Objects are not lost between generations. The Module’s assigned location is stored in _gridLocation dynamically so it can move the prefab into position once the generation is complete. _gridSize store the X/Y size of area being generated and is used to help define Modules that are along the edge of the area. _neighbors is an Array of the neighbor Modules used for cascading the information of Valid Tiles. _isCollapsed marks the Module as complete and ready to instantiate it’s chosen Tile. The ‘Edge’ Hashsets contain the values of the edge types for each valid tile and are updated with each collapse of a neighbor.

Once we have the Module Setup by the FloorManager (which we will explore later), we have a few key methods to take a Module from having multiple Valid Tiles to just one.

PopulateEdgeList() fills the ‘Edge’ Hashsets with the edge values for each edge of each Valid Tile for the assigned Module. The use of hashsets here eliminates any excess from duplicates and speeds up the checks later.

CheckForInvalidTiles() uses one of the ‘Edge’ Hashsets to check the opposite edge of a neighboring Module. If the edge of any tile doesn’t match a value in the hashset, it is added to the Invalid Tiles list. Once every Valid Tile is checked, each Invalid Tile is removed from the Valid Tiles list. Then we Refresh the EdgeList for this Module with the new list of Valid Tiles.

CheckNeighborsForInvalids() is called as an Event when a Module has been collapsed to a Tile. This is used to start the previous method in each Module that is neighboring the collapsed tile. *This is a big area for optimization that I want to revisit as I further develop this algorithm*

CollapseModuleToTile() is the big trigger for the rest of the methods. The Floor Module calls this method when the Module is picked to be collapsed. This does not always happen when there is only one valid tile, so it has to randomly pick from the available tiles. Here we make a single check if the Reroll bool was checked. Line 8 is used when we want the effect seen in the gif at the beginning of this article. Normally, the tile prefab is instantiated at the end of the algorithm. Then we do some clean up by moving and removing all the Valid Tiles to the InvalidTiles list. The chosen tile is returned to the ValidTiles list for later reference if needed. We refresh the ‘Edge’ hashsets based on the single tile. We mark this Module as complete before Calling the Event to Check the neighboring tiles.

In the next article, we will explore the Floor Manager and how it dynamically sets up the modules.