Wave Function Collapse is a procedural generation algorithm that generates maps out of tiles. This algorithm mimics the Wave Function Collapse from quantum mechanics, by observing a tile it then is able to reasonably solve what the rest of the tiles should be through propagation. This therefore collapses the wave of tiles giving us the determined tiles. With this we are able to use it to create unique game level that follow constraints in order to make coherent levels.
Introduction
Introduction
Most video games take place in a level of some sort that have been designed in a coherent way. You need to make sure that the map makes sense, you can't simply have walls existing in the middle of an ocean or a tree in a wall. The Wave Function Collapse algorithm is a procedural generating algorithm that is able to generate a map that follows a set of constraints. This is useful for when you need a level created without manually placing each tile by yourself and for roguelike games where you need new and random maps generated very often. Games such as Bad North and Townscaper both use this algorithm to generate their levels.
Simple Random Wave Function Collapse
Simple Random Wave Function Collapse
In order to create the simple random wave function collapse I used a simple method where I just look for contradictions around recently observed cells and it observes the cells that have the least possible options. This method as inspired by The Coding Train's .
2
method
Setting up Variables
Setting up
Variables
The following is setting the wave which is the grid. tileWidtha and tileHeight are the height and width of the resultant image in the units of tiles. We'll be using and the tiles with L representing the Land, B representing the Beach and W representing the water. grid is the grid that contains all the information about all the tiles with whether they've collapsed, meaning if it's decided on a tile to become, the tiles it could be and its index.
In[]:=
tileWidth = 20;tileHeight = 20;tiles = {"L", "B", "W"};grid = Table[<|"collapsed" -> False, "options" -> tiles, "index" -> i|>, {i, tileWidth*tileHeight}];startingIndex=(RandomInteger[tileWidth]+1)*(RandomInteger[tileHeight]+1);grid[[startingIndex]] = <|"collapsed"->True, "options"->RandomChoice[tiles],i->startingIndex|>;
We can now set up the constraints for each tile, with the association having the tile as the key and the tiles allowed around it in a 2D list with each element being the tile types allowed up, right, down left respectively.
In[]:=
rules=<|"L"->{{"L","B"},{"L","B"},{"L","B"},{"L","B"}},"B"->{{"L","B","W"},{"L","B","W"},{"L","B","W"},{"L","B","W"}},"W"->{{"B","W"},{"B","W"},{"B","W"},{"B","W"}}|>;
Observation
Observation
We can now do observation which is to collapse one of tiles with the lowest entropy. We now rank each tile based on how many possible tiles they could be with the amount they have being considered as their entropy and taking the items with the lowest entropy and choosing a random one and collapsing it, solidifying what the possible tile will be for it.
In[]:=
sortedGrid = SortBy[Select[grid, #collapsed == False &], Length[#options] &];stopLength = Length[sortedGrid[[1]][["options"]]];stopIndex = First FirstPosition sortedGrid, SelectFirst[sortedGrid, Length[#[["options"]]] > stopLength &] ;collapseIndex = RandomChoice[Take[sortedGrid, stopIndex - 1]][["index"]];grid[[collapseIndex]][["collapsed"]] = True;grid[[collapseIndex]][["options"]] = RandomChoice[grid[[collapseIndex]]["options"]];
Propagation
Propagation
We can now perform propagation on the wave which tries to solve what the other possible tiles could be. This goes through the tiles with listChangeable around the collapsed tiles and it checks for the contradictions between the possible tiles the tile could be and the possible tiles that could be around the collapsed tile which will help eliminate the possible tiles allowing it to be observed next.
In[]:=
setOptions[collapsed_,index_,type_]:=grid[[index]][["options"]]=Which collapsed==index-tileWidth, Intersection[grid[[index]][["options"]],rules[[type]][[1]]], collapsed==index+1, Intersection[grid[[index]][["options"]],rules[[type]][[2]]], collapsed==index+tileWidth, Intersection[grid[[index]][["options"]],rules[[type]][[3]]], collapsed==index-1, Intersection[grid[[index]][["options"]],rules[[type]][[4]]], True, grid[[index]][["options"]]listChangeable[index_]:=Module{changeable=<||>}, Ifgrid[[index-1]][["collapsed"]], Nothing, If Between[index-1,{1,tileHeight*tileWidth}], changeable[["left"]]=index-1, Nothing ; ; Ifgrid[[index+1]][["collapsed"]], Nothing, If Between[index+1,{1,tileHeight*tileWidth}], changeable[["right"]]=index+1, Nothing ; ; Ifgrid[[index-tileWidth]][["collapsed"]], Nothing, If Between[index-tileWidth,{1,tileHeight*tileWidth}], changeable[["up"]]=index-tileWidth,Nothing ; ; Ifgrid[[index+tileWidth]][["collapsed"]], Nothing, IfBetween[index+tileWidth,{1,tileHeight*tileWidth}], changeable[["up"]]=index+tileWidth, Nothing ; ; changeableTable If grid[[i]][["collapsed"]]==True, Table setOptions[i,j,grid[[i]][["options"]]], {j,listChangeable[i]} ; ,{i,tileWidth*tileHeight};
The Whole Model
The Whole Model
Now if we put it all together we get a cycle where we observe and then propagate which will eventually collapse the whole state into one wave.
In[]:=
tileWidth = 20;tileHeight = 20;tiles = {"L", "B", "W"};rules=<|"L"->{{"L","B"},{"L","B"},{"L","B"},{"L","B"}},"B"->{{"L","B","W"},{"L","B","W"},{"L","B","W"},{"L","B","W"}},"W"->{{"B","W"},{"B","W"},{"B","W"},{"B","W"}}|>;grid = Table[<|"collapsed" -> False, "options" -> tiles, "index" -> i|>, {i, tileWidth*tileHeight}];startingIndex=(RandomInteger[tileWidth]+1)*(RandomInteger[tileHeight]+1);grid[[startingIndex]] = <|"collapsed"->True, "options"->RandomChoice[tiles],i->startingIndex|>;While Length[Select[grid,#collapsed==False&]]>0, sortedGrid=SortBy[Select[grid,#collapsed==False&],Length[#options]&]; stopLength = Length[sortedGrid[[1]][["options"]]]; stopIndex =First[FirstPosition[sortedGrid,SelectFirst[sortedGrid,Length[#[["options"]]]>stopLength&]]]; If AllTrue[sortedGrid,Length[#options]==Length[sortedGrid[[1]][["options"]]]&], stopIndex=Length[sortedGrid]+1, Nothing ; collapseIndex=RandomChoice[Take[sortedGrid,stopIndex-1]][["index"]]; grid[[collapseIndex]][["collapsed"]]=True; grid[[collapseIndex]][["options"]]=RandomChoice[grid[[collapseIndex]]["options"]]; Table Ifgrid[[i]][["collapsed"]]==True, Table[setOptions[i,j,grid[[i]][["options"]]],{j,listChangeable[i]}]; ,{i,tileWidth*tileHeight} ; If Length[Select[grid,#collapsed==False&]]==1, grid[[First[Select[grid,#collapsed==False&]][["index"]]]][["options"]]=RandomChoice[First[Select[grid,#collapsed==False&]][["options"]]]; grid[[First[Select[grid,#collapsed==False&]][["index"]]]][["collapsed"]]=True
We can now represent it as an image:
The following image follows all the rules declared.
Generator Output
Generator Output
Tiled Wave Function Collapse
Tiled Wave Function Collapse
The Tiles
The Tiles
This Wave Function Collapse uses tiles which follows certain sets of symmetries. The letter after the name of the tile represents the have of the tile, for example if the tile has an L symmetry it's considered a corner piece meaning there should be four variations of it as the corners can rotate 90º. There are also weights associated with each title to represent how common they should appear.
We also need to dictate the rules for these tiles too and since the tile system is more complicated there will be more rules. Each rule only needs left and right as we'll be creating functions to make the rotations so they all work.
The Propagator
The Propagator
Since we don't have a rule defined for each variation we need to create a propagator that we can reference to later. The following functions helps assign all variations of the tile, for example the corner with four variations, to the correct neighbours.
The following code will go through each tile and create a reference of tiles, list of weights, and a list of how to rotate each neighbour for each tile.
This is a temporary propagator that helps assign the neighbour for each cell
This will check whether all the tiles have valid neighbours and finalise the propagator.
The model
The model
This initialises all the variables needed to insitialise the wave
Weights used in this model is slightly more complicated through calculating the logs of the weights to give a more accurate weighting especially for larger levels.
Now we can code to run the wave function collapse. The following function takes a node and removes one of the possible cells it could be and recalculates all the weights afterwards
The following will use the weights to select the node that should be collapsed.
The following function is the observe function which takes in the node from the previous function and then collapses it leaving with its certain state.
The following function calculates all the contradictions using the propagator we setup originally.
The Whole Model
The Whole Model
We can now run the whole model. But first I need to make a reset function.
We now import the images of all the tiles. The extra blurred image is just to show the uncertainty of that tile.
Now we can collapse the wave using the same loop of observation and propagation.
We can also see how the wave was collapsed to generate the image.
3D Wave Function Collapse
3D Wave Function Collapse
We can interlace the 2D wave function collapse in order to create a 3D level.
Functions
Functions
For the function we'll be using similar functions only changing the tileset and the neighbours.
Then we need to re-set up the propagator
And we can use the reset function to initialise the wave
Now we have some extra functions to force an observation across a level. ForceObserve forces one tile to become a certain tile and ForceRemoveStairs removes stairs from the rest of the level apart from a certain tile.
Setting up the 3D
Setting up the 3D
We will be using ArrayPlot3D to create the 3D image. The ApplyEmptySpace function puts space above the floor and the voxelRef is how the tile corresponds to the
Creating 1 floor
Creating 1 floor
We can create the floor through running the same loop as we have previously
Now we can visualise it using the Wolfram colours.
Creating multiple floors
Creating multiple floors
This one's a bit more complicated as we need to keep track of where the stairs start in order to make sure they're connected.
Very Long Code Here
Very Long Code Here
Output
Output
Final Building
Final Building
We can now just run this multiple times in order to create what I call the "Wolfram Tower"
Output
Output
The menacing Wolfram Tower!
Conclusion & Future Work
Conclusion & Future Work
We can now use the wave function collapse to generate video game maps.
Future work could be to do the overlapping and do tiles with 6 neighbours like with hexagons or with cubes making 3D neighbours.
Future work could be to do the overlapping and do tiles with 6 neighbours like with hexagons or with cubes making 3D neighbours.
Acknowledgements
Acknowledgements
Thanks to Jack my mentor
Citations
Citations
1
.Mxgmn. (n.d.). GitHub - mxgmn/WaveFunctionCollapse: Bitmap & tilemap generation from a single example with the help of ideas from quantum mechanics. GitHub. https://github.com/mxgmn/WaveFunctionCollapse
2
.CodingTrain. (n.d.). GitHub - Codingtrain/wave-function-collapse. GitHub. https://github.com/CodingTrain/Wave-Function-Collapse
3
.Kchapelier. (n.d.). GitHub - kchapelier/wavefunctioncollapse: Javascript port of https://github.com/mxgmn/WaveFunctionCollapse. GitHub. https://github.com/kchapelier/wavefunctioncollapse
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Generating game levels using Wave Function Collapse
by Samion Suwito
Wolfram Community, STAFF PICKS, July 13, 2023
https://community.wolfram.com/groups/-/m/t/2965318
by Samion Suwito
Wolfram Community, STAFF PICKS, July 13, 2023
https://community.wolfram.com/groups/-/m/t/2965318