Wavefunction Collapse Tutorial #1
A downloadable asset pack
In this tutorial, you will learn how to implement a fast and efficient wavefunction collapse algorithm. This algorithm is a technique for generating procedural content that follows a set of rules and constraints. The algorithm starts with a grid of cells that can have multiple possible states, and then collapses each cell to a single state by choosing one that is compatible with its neighbors. This process creates a coherent output that matches the initial patterns and rules.
The main challenge of this algorithm is to avoid contradictions, which are cells that have no compatible states left. Many wavefunction collapse algorithms deal with this problem by backtracking and retrying different choices, but this can be very slow and costly. In this tutorial, you will learn how to use a different approach that avoids backtracking and only processes the grid once. You will use a flood fill algorithm to select a random starting cell and then expand it to all adjacent cells that have the same possible states. You will also use bit masks and Boolean operations to speed up the compatibility checks and the state selection.
By following this tutorial, you will be able to create a wavefunction collapse algorithm that can generate complex and varied content in a fraction of the time and memory that other algorithms require.
Part 1: Setup
Lets start by creating a class to hold the wave function collapse parameters and methods.
function wave_function_class(_rules=-1) constructor{
//----- wave object values ---//
self.rules = [
["Y","L","L","L","L","L","Y"],
["L","C","C","C","C","C","L"],
["L","C","S","S","S","C","L"],
["C","S","S","S","S","C","L"],
["C","C","S","S","S","C","L"],
["L","C","S","S","C","C","L"],
["Y","L","C","C","L","L","Y"]
];
if(is_array(_rules)){
self.rules = _rules;
};
/// list of all letters in rules, and their
/// bit mask values for each direction
self.wave_object = {};
/// index for bit values
self.wave_id = 0;
/// self.rules as a string for easy masking
self.wave_string = "";
/// contains all possible values, used for empty cells
self.mask_max = 0;
//---- world values --------//
/// world size
self.world_width = 40;
self.world_height = 40;
/// world data
self.world_matrix = [];
self.world_flags = [];
/// list of all tiles left to be operated on
self.job_list = [];
/// initialize world data
for(var _i = 0; _i < self.world_width; _i++){
array_push(self.world_matrix, []);
array_push(self.world_flags, []);
for(var _j = 0; _j < self.world_height; _j++){
array_push(self.world_matrix[_i], self.mask_max);
array_push(self.world_flags[_i], 0);
}
}
}
This code defines a Game Maker class called wave_function_class with a constructor function that initializes its properties.
The class has the following properties:
rules: an array of arrays that represents the possible patterns or rules for the wave function. Each inner array corresponds to a row of the pattern, and contains characters that represent the different states or values that a cell in that row can take on. For example, the character "Y" may represent a yellow cell, "L" may represent a blue cell, "C" may represent a green cell, and "S" may represent a white cell.wave_object: an object that contains all the possible values for the wave function, and their bit mask values for each direction.wave_id: an integer that serves as an index for bit values in thewave_object.wave_string: a string for easily picking a weighted tile value to collapse. We can easily remove tiles from the string to change the weighted probability with minimal processing -- speeding up the program significantly.mask_max: an integer that contains the maximum possible value for empty cells.world_widthandworld_height: integers that represent the width and height of the world matrix.world_matrix: a two-dimensional array that contains the current state of the world matrix, with each cell represented by a value corresponding to the rules inself.rules.world_flags: a two-dimensional array that contains flags for each cell inworld_matrix.job_list: an array that contains all the tiles left to be operated on.
The constructor function initializes these properties by assigning values to them. It first sets the rules property to a default pattern, but if an array of rules is passed as an argument to the constructor, it sets the rules property to that array instead.
It then initializes the wave_object property as an empty object, sets wave_id to 0, and initializes wave_string and mask_max to empty strings and 0, respectively.
The constructor also initializes the world_matrix and world_flags properties as two-dimensional arrays of empty cells with a size of world_width by world_height. Finally, it initializes job_list as an empty array.
Lets create a couple more classes to handle operating on individual tiles.
function Tile(_up,_left,_right,_down) constructor {
self.up = _up;
self.down = _down;
self.right = _right;
self.left = _left;
static compare = function(_tile){
var _output = (self.up & _tile.up) ? 1 : 0;
_output += (self.left & _tile.left) ? 1 : 0;
_output += (self.right & _tile.right) ? 1 : 0;
_output += (self.down & _tile.down) ? 1 : 0;
return _output;
};
}
function wave_object_class(_id) constructor{
id = _id;
tiles = [];
}
This code defines two Game Maker classes, Tile and wave_object_class.
The Tile class has a constructor function that takes four arguments, _up, _left, _right, and _down. These arguments represent the possible connections between the tile and its adjacent tiles in each direction.
The constructor function initializes four properties, up, down, left, and right, with the values of _up, _down, _left, and _right, respectively.
The Tile class also has a compare method that takes a _tile argument, representing another tile, and returns an integer that represents how well the two tiles match. This is determined by comparing the connections of each tile in all four directions using bitwise AND operations. The output integer represents the number of matches found.
The wave_object_class has a constructor function that takes an argument _id. It initializes two properties, id and tiles, with the values of _id and an empty array, respectively.
The wave object will store a list of all the Tile objects. There will only be as many tile objects as there are different "letters" defined in the rules array. Since there are 4 letters in the rules array, there will be 4 tile objects. Each of those tile objects will have up, left, down, and right facing tiles that contain all the possible tiles that it can border. It uses the compare function to check how well it matches the adjacent tiles it will be compared with.
When we iterate over all possible tile positions in the world matrix, we will pick a tile at random from the weighted tile string and then test all possible configurations of that tile with the adjacent tiles. If the tile is a match we place it, otherwise we remove that tile from the weighted string, and pick one from the remaining tiles at random and repeat the process. If we fail to find a tile, we just place the one that best matches.
Part 2: Initialization
Before we can operate on the world matrix, we have to generate the rules and bit-masking values. We will place the code below at the bottom of the constructor of the wave_function_class. (We want this to be at the end, after all of the static methods are initiated)
/// initialize wave object
for(var _i = 0; _i < array_length(self.rules); _i++){
for(var _j = 0; _j < array_length(self.rules[0]); _j++){
var _key = self.rules[_i][_j];
self.wave_string += string(_key);
/// check if this key has a struct associated with it yet
if(!object_has_key(self.wave_object, _key)){
var _mask = 1 << self.wave_id;
self.mask_max += _mask;
/// set value in struct
variable_struct_set(self.wave_object, _key,
new wave_object_class(_mask)
);
self.wave_id++;
}
}
};
/// set wave object bitmask
for(var _i = 0; _i < array_length(self.rules); _i++){
for(var _j = 0; _j < array_length(self.rules[0]); _j++){
var _key = self.rules[_i][_j];
var _wave = self.wave_object[$ _key];
/// set up bitmask
/// add to up bitmask
var _up_value = self.get_rule_value(_i-1, _j);
var _down_value = self.get_rule_value(_i+1, _j);
var _left_value = self.get_rule_value(_i, _j-1);
var _right_value = self.get_rule_value(_i, _j+1);
if(array_length(_wave.tiles) == 0){
array_push(_wave.tiles, new Tile(_up_value, _left_value, _right_value, _down_value));
} else {
/// check if tile already exists
for(var _k = 0; _k < array_length(_wave.tiles); _k++){
var _tile = _wave.tiles[_k];
if(_tile.compare(new Tile(_up_value, _left_value, _right_value, _down_value)) == 4){
continue;
}
if(_k == array_length(_wave.tiles) - 1){
array_push(_wave.tiles, new Tile(_up_value, _left_value, _right_value, _down_value));
}
}
}
}
}
This code initializes a wave object that represents a set of possible tile arrangements. It does so by iterating through a set of rules that define the possible values for each position in the arrangement.
The first loop iterates through the rules and adds the corresponding keys to the wave_string. If a key doesn't exist in the wave_object, it creates a new wave_object_class and assigns a bitmask to it based on its position in the array.
The second loop iterates through the rules again and sets the bitmask for each tile in the wave_object. It does this by getting the values of adjacent tiles and creating a new Tile object with those values. If the tile already exists in the wave_object, it skips it; otherwise, it adds the new Tile object to the tiles array for the corresponding wave_object_class.
Part 3: Ready to Collapse?
Now we are going to write up the static methods for collapsing the wavefunctions into tiles.
/// check to see if key has been assigned
static object_has_key = function(_obj, _key){
return variable_struct_exists(_obj, string(_key));
}
/// safely get value from a matrix
static get_matrix_value = function(_matrix, _xto, _yto){
var _w = array_length(_matrix);
var _h = array_length(_matrix[0]);
_xto = clamp(_xto, 0, _w-1);
_yto = clamp(_yto, 0, _h-1);
return _matrix[_xto][_yto];
};
/// use to calculate tiles current fitness value
static get_superposition = function(_wave, _world_local){
var _output = 0;
var _world_tile = new Tile(_world_local.up, _world_local.left, _world_local.right, _world_local.down);
for(var _i = 0; _i < array_length(_wave.tiles); _i++){
var _tile = _wave.tiles[_i];
var _tile_match_value = _tile.compare(_world_tile);
if(_tile_match_value > _output){
_output = _tile_match_value;
}
}
return _output;
}
object_has_key is a function that takes two arguments, _obj and _key, and returns a boolean value indicating whether the object _obj has a property named _key. It uses the variable_struct_exists function to check for the existence of the key.
get_matrix_value is a function that takes three arguments, _matrix, _xto, and _yto. It is used to safely retrieve a value from a two-dimensional array (matrix). It first determines the width and height of the matrix, clamps the x and y values to ensure they are within the bounds of the matrix, and then returns the value at the specified position in the matrix.
get_superposition is a function that takes two arguments, _wave and _world_local, representing a wave object and a tile object respectively. It calculates the fitness value (i.e. the superposition) of the given tile within the given wave object. It compares the given tile to all tiles in the wave object by calling the compare method of the Tile class, and returns the highest matching value. The output value represents how well the given tile fits into the world matrix at the position being checked.
Now we need some static methods for converting the tile letter into the bit masking value.
// used to return the bit value stored in the world matrix
static get_bit_value = function(_key){
if(_key == -1){
return 1;
} else if(!self.object_has_key(self.wave_object, _key)){
return self.mask_max;
}
return self.wave_object[$ _key].id;
};
/// get bitmask value stored in rule position x,y
static get_rule_value = function(_xto, _yto){
var _key = get_matrix_value(self.rules, _xto, _yto);
return get_bit_value(_key);
};
/// get bitmask value stored in the world position, x,y
static get_world_value = function(_xto, _yto){
var _key = get_matrix_value(world_matrix, _xto, _yto);
var _bitmask = get_bit_value(_key);
return _bitmask;
};
- The function `get_bit_value` takes a parameter `_key` which is either a letter or -1. It returns a number that represents the bit value stored in the wave_object.
- If `_key` is -1, it means there is no letter assigned to that position, so it returns 1 as the default bit value.
- If `_key` is a letter that is not found in the `wave_object`, it means that letter is not compatible with any of the possible states, so it returns `mask_max` as the maximum bit value.
- If `_key` is a letter that is found in the `wave_object`, it returns the `id` property of that letter, which is a number that represents its bit value.
- The function `get_rule_value` takes two parameters `_xto` and `_yto` which are the coordinates of a position in the rule matrix. The rule matrix is a data structure that holds information about the constraints between different letters. It returns the bit value stored in that position by calling the `get_bit_value` function with the letter found in the rule matrix at those coordinates.
- The function `get_world_value` takes two parameters `_xto` and `_yto` which are the coordinates of a position in the world matrix. It returns the bit value stored in that position by calling the `get_bit_value` function with the letter found in the world matrix at those coordinates.
Almost there! Now we need to add the methods for clearing the world matrix, picking random keys from the wave_string, and extracting the bitmask value from the neighbor tiles in the world matrix.
/// clear out old data for the world
static clear_world = function(){
for(var _i = 0; _i < self.world_width; _i++){
for(var _j = 0; _j < self.world_height; _j++){
self.world_matrix[_i][_j] = self.mask_max;
self.world_flags[_i][_j] = 0;
}
}
job_list = [];
array_push(job_list, [random_range(0,world_width-1), random_range(0, world_height-1)]);
};
/// pick a character from a string at random
static pick_random_key = function(_test_wave_string){
var _len = string_length(_test_wave_string);
var _char = string_copy(_test_wave_string, irandom(_len-1)+1, 1);
return _char;
};
/// extract the bitmask for up,left,right,down at the specified world position
static extract_neighbor_bitmask = function(_world_pos){
var _up_value = self.get_world_value(_world_pos[0]-1, _world_pos[1]);
var _down_value = self.get_world_value(_world_pos[0]+1, _world_pos[1]);
var _left_value = self.get_world_value(_world_pos[0], _world_pos[1]-1);
var _right_value = self.get_world_value(_world_pos[0], _world_pos[1]+1);
return {up: _up_value, down: _down_value, left: _left_value, right: _right_value};
};
- The function `clear_world` resets the world matrix and the world flags to their initial values. The world matrix is set to `mask_max` which means all possible states are allowed, and the world flags are set to 0 which means no state has been collapsed yet. It also creates a new list of jobs, which are positions in the world matrix that need to be processed. It adds a random position to the job list as the first job.
- The function `pick_random_key` takes a parameter `_test_wave_string` which is a string of letters that represent possible states. It returns a random letter from that string by copying one character at a random index.
- The function `extract_neighbor_bitmask` takes a parameter `_world_pos` which is an array of two numbers that represent the coordinates of a position in the world matrix. It returns an object that contains the bit values of the four neighboring positions: up, down, left and right. It calls the `get_world_value` function to get the bit values from the world matrix.
Part 4: Generate!
Before we can run the method that generates the world matrix values, we need to integrate the super position matching. Lets add the following static method:
/// match the current tile super position to the world tile field
static match = function(_world_obj, _key){
/// wave contains up, left, right, down bitmasks
if(!self.object_has_key(self.wave_object, _key)){
return 0;
}
var _wave = self.wave_object[$ _key];
/// check if the world value matches the wave value
var _score = get_superposition(_wave, _world_obj);
return _score;
};
- The function `match` takes two parameters `_world_obj` and `_key`. The `_world_obj` is an object that contains the bit values of the four neighboring positions of a position in the world matrix. The `_key` is a letter that represents a possible state.
- The function checks if the letter is found in the `wave_object`, which is a data structure that holds information about the possible states and their constraints. If not, it returns 0 as the match score.
- If the letter is found in the `wave_object`, it gets the corresponding object that contains the bit values of the four directions for that letter. It calls the `get_superposition` function to compare the bit values of the letter and the world position and returns the result as the match score.
Finally, we can put all of it together to generate the map!
static run = function(){
/// clear job list, add random position to start
self.clear_world();
var _start = current_time;
var _count = 0;
while(array_length(job_list) > 0){
/// get the first tile
var _world_tile = array_pop(job_list);
/// get copy of wave string
var _wave_test_string = wave_string;
var _key = self.pick_random_key(_wave_test_string);
/// remove used keys
_wave_test_string = string_replace_all(_wave_test_string, _key, "");
var _count_match = 100;
var _save_key = _key;
var _adjacent_tiles = self.extract_neighbor_bitmask(_world_tile);
var _match_score = self.match(_adjacent_tiles, _key);
/// check key for super-position match, exit when no keys are left
while(_match_score < 4){
/// last key tested, break out of loop
if(string_length(_wave_test_string) == 0 || _count_match-- <= 0){
break;
}
_key = self.pick_random_key(_wave_test_string);
_wave_test_string = string_replace_all(_wave_test_string, _key, "");
var _score = self.match(_adjacent_tiles, _key);
if(_score > _match_score){
_match_score = _score;
_save_key = _key;
}
}
/// add the new tiles up, down, right, left to the job list if they are in the world
var _xstart = _world_tile[0];
var _ystart = _world_tile[1];
/// map the key to the world matrix position last tested
self.world_matrix[_xstart][_ystart] = _save_key;
if(_ystart - 1 >= 0){
if(self.world_flags[_xstart][_ystart - 1] == 0){
self.world_flags[_xstart][_ystart-1] = 1;
array_insert(job_list, 0, [_xstart, _ystart - 1]);
}
}
if(_ystart + 1 < self.world_height){
if(self.world_flags[_xstart][_ystart + 1] == 0){
self.world_flags[_xstart][_ystart+1] = 1;
array_insert(job_list, 0, [_xstart, _ystart + 1]);
}
}
if(_xstart - 1 >= 0){
if(self.world_flags[_xstart - 1][_ystart] == 0){
self.world_flags[_xstart - 1][_ystart] = 1;
array_insert(job_list, 0, [_xstart - 1, _ystart]);
}
}
if(_xstart + 1 < self.world_width){
if(self.world_flags[_xstart + 1][_ystart] == 0){
self.world_flags[_xstart + 1][_ystart] = 1;
array_insert(job_list, 0, [_xstart + 1, _ystart]);
}
}
/// emergency exit
_count++;
if(_count > 10000){
break;
}
}
/// add the result to the table
var _end = current_time;
show_debug_message("Time taken: {0}ms", (_end-_start));
};
- The method `run` executes the main algorithm of the wavefunction collapse. It clears the world matrix and the world flags and adds a random position to the job list. It also records the start time and the count of iterations.
- The method loops until the job list is empty. In each iteration, it does the following steps:
- It pops the first position from the job list and assigns it to `_world_tile`.
- It copies the `wave_string` which is a string of all possible letters and assigns it to `_wave_test_string`.
- It picks a random letter from `_wave_test_string` and assigns it to `_key`. It also removes that letter from `_wave_test_string`.
- It sets `_count_match` to 100 and `_save_key` to `_key`. These are variables that keep track of the best match score and the best letter for the current position.
- It extracts the bit values of the four neighboring positions of `_world_tile` and assigns them to `_adjacent_tiles`.
- It calls the `match` function to get the match score between `_adjacent_tiles` and `_key` and assigns it to `_match_score`.
- It enters a while loop that tries to find a better match score by picking different letters from `_wave_test_string`. The loop exits when either:
- The match score is 4, which means a perfect match.
- The `_wave_test_string` is empty, which means no more letters to try.
- The `_count_match` reaches zero, which means a limit on the number of tries.
- In each iteration of the while loop, it does the following steps:
- It picks a random letter from `_wave_test_string` and assigns it to `_key`. It also removes that letter from `_wave_test_string`.
- It calls the `match` function to get the match score between `_adjacent_tiles` and `_key` and assigns it to `_score`.
- If `_score` is greater than `_match_score`, it updates `_match_score` and `_save_key` with the new values.
- After exiting the while loop, it sets the value of the current position in the world matrix to `_save_key`, which is the best letter found.
- t adds the four neighboring positions of the current position to the job list, if they are within the bounds of the world matrix and have not been processed yet. It also marks them as processed in the world flags.
Conclusion:
In this tutorial, you learned how to implement the wavefunction collapse algorithm in code. This algorithm is a powerful technique for generating procedural content that follows a set of rules and constraints. You learned how to use letters, numbers, and bit masks to represent different states and their compatibility. You also learned how to use a world matrix, a rule matrix, and a wave object to store and manipulate the information about the system. You saw how to use a job list and a loop to process each position in the world matrix and collapse it to a single state. You also learned how to use randomization and superposition to create variety and uncertainty in the output.
You can use this algorithm for many creative applications, such as generating maps, textures, patterns, puzzles, stories, and more. You can experiment with different rules and constraints to create different styles and genres. You can also combine this algorithm with other techniques, such as cellular automata, noise functions, or neural networks, to create more complex and realistic content. The possibilities are endless! In the next tutorial I will show you how to auto-tile the world matrix.
Download
Click download now to get access to the following files:
Leave a comment
Log in with itch.io to leave a comment.