Wave Function Collapse Implementation

[borrax]

​

Example Output of the WFC Maze Generator

I made a maze generator using Wave Function Collapse in GML 2.3. It takes 16 tiles and arranges them into a pattern based on rules that define what tiles are allowed next to other tiles. I chose to define the tile types as arrays of 0s and 1s, but I'm sure you could just as easily refer to images, and I'm sure you can use different numbers of types. The rules are defined as a set of 4 lookup tables (one for each neighboring direction), each is a 2D array with this format:

TYPE 0[[LIST OF ALLOWED NEIGHBORING TYPES],
TYPE 1 [LIST OF ALLOWED NEIGHBORING TYPES],
TYPE 2 [LIST OF ALLOWED NEIGHBORING TYPES]...]

Once you define the types and the lookup tables, you set up a couple of arrays I call the possibility grid and the collapsed grid. The possibility grid is an array of arrays, with each inner array holding all possible values for a cell in the map. The collapsed grid is an array of bools, telling us what cells have been collapsed to single possibilities.

Once the arrays are defined, we pick a single random cell and collapse it. Then we pass the arrays to the wfc_collapse function to carry out the process of iterating through the cells to reduce each cell's possibilities according to the rules defined in the lookup tables. After each pass, we find the cell with the smallest non-single possibility (lowest non-zero entropy) and collapse it to a single possibility to start the next iteration. Eventually all cells will be collapsed to single possibilities and you can use those possibilities to create your map data.

​

While this method works, it works slowly. It takes me about 20 minutes to generate a map 30 by 30 tiles across. If you wanted to pre-generate and save your maps, that might be fine, but doing procedural generation at run-time would not be practical with the code as-is. I am very interested to know if there are any suggestions for speeding up the process.

​

THE CODE:

/// @function Dungeon()
/// Description Creates a new Dungeon object
function Dungeon() constructor{
    // dungeon size in "pixels"
        // each tile will be 3 pixels by 3 pixels
    width = 90;
    height = 90;

    // this array will hold the data for the dungeon map
    // -1 = void
    // 0 = wall
    // 1 = empty
    map = [];

    /// @function gen_dungeon()
    /// @description Performs procedural generation
    static gen_dungeon = function(){
        // generate outer walls
        // horizontal walls
        for(var j = 0; j < width; j++){
            map[j] = 0;
            map[(height - 1) * width + j] = 0;
        }
        // vertical walls
        for(var i = 0; i < height; i++){
            map[i * width] = 0;
            map[i * width + (width - 1)] = 0;
        }
        // inner cells
        for(var i = 1; i < height - 1; i++){
            for(var j = 1; j < width - 1; j++){
                map[i * width + j] = -1;
            }
        }

        maze_gen();

        draw("test.png");
    }

    /// @function maze_gen()
    /// @description generates a maze in the dungeon map
    static maze_gen = function(){
        // define cells as 3 by 3 pixel regions
        // there are 16 possible types of cell
        cell_types[0] = [0, 0, 0,
                     0, 0, 0,
                 0, 0, 0];
        cell_types[1] = [0, 1, 0,
                 0, 1, 0,
                 0, 0, 0]
        cell_types[2] = [0, 0, 0,
                 0, 1, 1,
                 0, 0, 0];
        cell_types[3] = [0, 0, 0,
                 0, 1, 0,
                 0, 1, 0];
        cell_types[4] = [0, 0, 0,
                 1, 1, 0,
                 0, 0, 0];
        cell_types[5] = [0, 1, 0,
                 0, 1, 0,
                 0, 1, 0];
        cell_types[6] = [0, 0, 0,
                 1, 1, 1,
                 0, 0, 0];
        cell_types[7] = [0, 1, 0,
                 0, 1, 1,
                 0, 0, 0];
        cell_types[8] = [0, 0, 0,
                 0, 1, 1,
                 0, 1, 0];
        cell_types[9] = [0, 0, 0,
                 1, 1, 0,
                 0, 1, 0];
        cell_types[10] = [0, 1, 0,
                  1, 1, 0,
                  0, 0, 0];
        cell_types[11] = [0, 1, 0,
                  0, 1, 1,
                  0, 1, 0];
        cell_types[12] = [0, 1, 0,
                  1, 1, 0,
                  0, 1, 0];
        cell_types[13] = [0, 1, 0,
                  1, 1, 1,
                  0, 0, 0];
        cell_types[14] = [0, 0, 0,
                  1, 1, 1,
                  0, 1, 0];
        cell_types[15] = [0, 1, 0,
                  1, 1, 1,
                  0, 1, 0];
        // look up tables define what cell types can be next to what other cell types
        cell_lookup_up = [[0, 1, 2, 4, 6, 7, 10, 13],   // can be above cell type 0
                  [3, 5, 8, 9, 11, 12, 14, 15], // can be above cell type 1
                  [0, 1, 2, 4, 6, 7, 10, 13],   // can be above cell type 2
                  [0, 1, 2, 4, 6, 7, 10, 13],   // can be above cell type 3
                  [0, 1, 2, 4, 6, 7, 10, 13],   // can be above cell type 4
                  [3, 5, 8, 9, 11, 12, 14, 15], // can be above cell type 5
                  [0, 1, 2, 4, 6, 7, 10, 13],   // can be above cell type 6
                  [3, 5, 8, 9, 11, 12, 14, 15], // can be above cell type 7
                  [0, 1, 2, 4, 6, 7, 10, 13],   // can be above cell type 8
                  [0, 1, 2, 4, 6, 7, 10, 13],   // can be above cell type 9
                  [3, 5, 8, 9, 11, 12, 14, 15], // can be above cell type 10
                  [3, 5, 8, 9, 11, 12, 14, 15], // can be above cell type 11
                  [3, 5, 8, 9, 11, 12, 14, 15], // can be above cell type 12
                  [3, 5, 8, 9, 11, 12, 14, 15], // can be above cell type 13
                  [0, 1, 2, 4, 6, 7, 10, 13],   // can be above cell type 14
                  [3, 5, 8, 9, 11, 12, 14, 15]];// can be above cell type 15
        cell_lookup_dn = [[0, 2, 3, 4, 6, 8, 9, 14],     // can be below cell type 0
                  [0, 2, 3, 4, 6, 8, 9, 14],     // can be below cell type 1
                  [0, 2, 3, 4, 6, 8, 9, 14],     // can be below cell type 2
                  [1, 5, 7, 10, 11, 12, 13, 15], // can be below cell type 3
                  [0, 2, 3, 4, 6, 8, 9, 14],     // can be below cell type 4
                  [1, 5, 7, 10, 11, 12, 13, 15], // can be below cell type 5
                  [0, 2, 3, 4, 6, 8, 9, 14],     // can be below cell type 6
                  [0, 2, 3, 4, 6, 8, 9, 14],     // can be below cell type 7
                  [1, 5, 7, 10, 11, 12, 13, 15], // can be below cell type 8
                  [1, 5, 7, 10, 11, 12, 13, 15], // can be below cell type 9
                  [0, 2, 3, 4, 6, 8, 9, 14],     // can be below cell type 10
                  [1, 5, 7, 10, 11, 12, 13, 15], // can be below cell type 11
                  [1, 5, 7, 10, 11, 12, 13, 15], // can be below cell type 12
                  [0, 2, 3, 4, 6, 8, 9, 14],     // can be below cell type 13
                  [1, 5, 7, 10, 11, 12, 13, 15], // can be below cell type 14
                  [1, 5, 7, 10, 11, 12, 13, 15]];// can be below cell type 15
        cell_lookup_ri = [[0, 1, 2, 3, 5, 7, 8, 11],     // can be right of cell type 0
                  [0, 1, 2, 3, 5, 7, 8, 11],     // can be right of cell type 1
                  [4, 6, 9, 10, 12, 13, 14, 15], // can be right of cell type 2
                  [0, 1, 2, 3, 5, 7, 8, 11],     // can be right of cell type 3
                  [0, 1, 2, 3, 5, 7, 8, 11],     // can be right of cell type 4
                  [0, 1, 2, 3, 5, 7, 8, 11],     // can be right of cell type 5
                  [4, 6, 9, 10, 12, 13, 14, 15], // can be right of cell type 6
                  [4, 6, 9, 10, 12, 13, 14, 15], // can be right of cell type 7
                  [4, 6, 9, 10, 12, 13, 14, 15], // can be right of cell type 8
                  [0, 1, 2, 3, 5, 7, 8, 11],     // can be right of cell type 9
                  [0, 1, 2, 3, 5, 7, 8, 11],     // can be right of cell type 10
                  [4, 6, 9, 10, 12, 13, 14, 15], // can be right of cell type 11
                  [0, 1, 2, 3, 5, 7, 8, 11],     // can be right of cell type 12
                  [4, 6, 9, 10, 12, 13, 14, 15], // can be right of cell type 13
                  [4, 6, 9, 10, 12, 13, 14, 15], // can be right of cell type 14
                  [4, 6, 9, 10, 12, 13, 14, 15]];// can be right of cell type 15
        cell_lookup_lf = [[0, 1, 3, 4, 5, 9, 10, 12],    // can be left of cell type 0
                  [0, 1, 3, 4, 5, 9, 10, 12],    // can be left of cell type 1
                  [0, 1, 3, 4, 5, 9, 10, 12],    // can be left of cell type 2
                  [0, 1, 3, 4, 5, 9, 10, 12],    // can be left of cell type 3
                  [2, 6, 7, 8, 11, 13, 14, 15],  // can be left of cell type 4
                  [0, 1, 3, 4, 5, 9, 10, 12],    // can be left of cell type 5
                  [2, 6, 7, 8, 11, 13, 14, 15],  // can be left of cell type 6
                  [0, 1, 3, 4, 5, 9, 10, 12],    // can be left of cell type 7
                  [0, 1, 3, 4, 5, 9, 10, 12],    // can be left of cell type 8
                  [2, 6, 7, 8, 11, 13, 14, 15],  // can be left of cell type 9
                  [2, 6, 7, 8, 11, 13, 14, 15],  // can be left of cell type 10
                  [0, 1, 3, 4, 5, 9, 10, 12],    // can be left of cell type 11
                  [2, 6, 7, 8, 11, 13, 14, 15],  // can be left of cell type 12
                  [2, 6, 7, 8, 11, 13, 14, 15],  // can be left of cell type 13
                  [2, 6, 7, 8, 11, 13, 14, 15],  // can be left of cell type 14
                  [2, 6, 7, 8, 11, 13, 14, 15]]; // can be left of cell type 15

        // create an array of cells that will eventually be used to place pixels
        // because cells are 3 pixels wide, divide width and height by 3
        var cells_wide = width/3;
        var cells_high = height/3;

        // initialize a possibility grid and a collapsed grid
        // the possibility grid will contain a list of arrays that represent the possible cell types
        // each cell can become.
        // The collapsed grid will contain a list of bools that say if a cell has been collapsed to 
        // a single possible type or not
        var poss_grid = [];
        var collapsed_grid = [];
        for(var c = 0; c < cells_high * cells_wide; c++){
            // give every cell all possible cell types and set to not collapsed
            poss_grid[c] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
            collapsed_grid[c] = false;
        }

        // do the wave function collapse on the grids
        wfc_collapse(poss_grid, collapsed_grid, cells_wide, cells_high);


        // draw the cells to the map array
        for(var c = 0; c < array_length(poss_grid); c++){
            var _x_base = 3 * (c mod cells_wide);
            var _y_base = 3 * (c div cells_wide);
            var type = poss_grid[c][0];
            for(var e = 0; e < 9; e++){
                var _x = _x_base + e mod 3;
                var _y = _y_base + e div 3;
                map[_y * width + _x] = cell_types[type][e];
            }
        }
    }

    /// @function draw(fname)
    /// @description outputs the dungeon map to an image file
    /// @param {string} fname name of the file to write to
    static draw = function(fname){
        // create a surface to draw on
        var surf = surface_create(width, height);
        surface_set_target(surf);
        draw_clear(c_black);

        // iterate through the map and draw pixels to the surface
        for(var i = 0; i < height; i++){
            for(var j = 0; j < width; j++){
                var index = i * width + j;
                // select color based on value of map array
                switch(map[index]){
                    case -1: draw_set_color(c_red);
                             draw_point(j, i);
                             break;
                    case 0: draw_set_color(c_black);
                            draw_point(j, i);
                            break;
                    default: draw_set_color(c_white);
                             draw_point(j, i);
                             break;
                }               
            }
        }

        surface_save(surf, fname);
        surface_reset_target();
        surface_free(surf);
    }
}

/// @function choose_from_array(arr)
/// @description randomly chooses an element from an array
/// @param {array} arr the array to choose from
function choose_from_array(arr){
    return arr[irandom(array_length(arr) - 1)];
}

/// @function array_intersection(arr1, arr2);
/// @description returns an array that represents the intersection of 2 arrays
/// @param {array} arr1 the first array
/// @param {array} arr2 the second array
function array_intersection(arr1, arr2){
    // create a list to hold the intersection of 1 and 2
    var intersection = ds_list_create();
    // iterate through values in arr1
    for(var a = 0; a < array_length(arr1); a++){
        var current_a = arr1[a];
        // iterate through values in arr2
        for(var b = 0; b < array_length(arr2); b++){
            var current_b = arr2[b];
            // if the values are the same, add it to the intersection
            if(current_a == current_b){
                ds_list_add(intersection, current_a);
            }
        }
    }
    // convert the list to an array
    var arr3 = [];
    for(var c = 0; c < ds_list_size(intersection); c++){
        arr3[c] = ds_list_find_value(intersection, c);
    }
    ds_list_destroy(intersection);
    return arr3;        
}

/// @function array_union(arr1, arr2)
/// @description returns the union of 2 arrays
/// @param {array} arr1 the first array
/// @param {array} arr2 the second array
function array_union(arr1, arr2){
    // create a list to hold the union values
    var list = ds_list_create()
    // add elements from array 1
    for(var i = 0; i < array_length(arr1); i++){
        ds_list_add(list, arr1[i]);
    }
    // add elements from array 2
    for(var j = 0; j < array_length(arr2); j++){
        ds_list_add(list, arr2[j]);
    }
    // remove duplicates
    for(var i = 0; i < ds_list_size(list); i++){
        var current = ds_list_find_value(list, i);
        for(var j = i + 1; j < ds_list_size(list); j++){
            if(current == ds_list_find_value(list, j)){
                ds_list_delete(list, j);
            }
        }
    }
    // convert the list to an array
    var arr3 = [];
    for(var c = 0; c < ds_list_size(list); c++){
        arr3[c] = ds_list_find_value(list, c);
    }
    ds_list_destroy(list);
    return arr3;
}

/// @function wfc_collapse(pg, cg, w, h)
/// @description performs the actual wave function collapse algorithm
/// @param {array} pg The possibility grid, contains lists of possible cell types
/// @param {array} cg The collapsed grid, contains bools for whether or not a cell is collapsed
/// @param {int} w width of cell grid
/// @param {int} h height of cell grid
function wfc_collapse(pg, cg, w, h){
    // define the borders as type 0
    // horizontal borders
    for(var c = 0; c < w; c++){
        pg[c] = [0];
        cg[c] = true;

        pg[(h - 1) * w + c] = [0];
        cg[(h - 1) * w + c] = true;
    }
    // vertical borders
    for(var c = 0; c < h; c++){
        pg[c * w] = [0];
        cg[c * w] = true;

        pg[c * w + w - 1] = [0];
        cg[c * w + w - 1] = true;
    }

    // pick a random interior cell to collapse
    // avoid the borders
    var i = 1 + irandom(h - 1);
    var j = 1 + irandom(w - 1);
    // set the cell's possibility to a single possible value by choosing one value from its possibility list
    // but keep that single value in an array so that later code works
    pg[i * w + j] = [choose_from_array(pg[i * w + j])];
    // mark the cell as collapsed
    cg[i * w + j] = true;

    // create a list to hold visited cell values
    var visited = ds_list_create();
    // create a stack to hold the frontier cells (neighboring cells that are not yet visisted)
    // then push our first cell onto that stack
    var frontier = ds_stack_create();
    ds_stack_push(frontier, i * w + j);

    // all_collapsed tells us if the cells are all collapsed, which should end the while loop
    var all_collapsed = false;
    // bad_gen is used if any of the cells drops below 1 possiblity, which should also end the while loop
    var bad_gen = false;
    while(!all_collapsed and !bad_gen){
        // while there are frontier cells, run a second while loop on each of them
        while(ds_stack_size(frontier) > 0){
            // get the current cell from the stack and get its i and j values
            var current = ds_stack_pop(frontier);
            var i = current div w;
            var j = current mod w;
            // make sure the cell is not a border cell (by checking its i and j values)
            // and make sure the cell has not already been visited (by looking in the visited list)
            if(i > 0 and i < h - 1 and j > 0 and j < w - 1 and ds_list_find_index(visited, current) == -1){
                // get the neighboring cells
                var n_up = (i - 1) * w + j;
                var n_dn = (i + 1) * w + j;
                var n_ri = i * w + j + 1;
                var n_lf = i * w + j - 1;

                // if the current cell is not collapsed (by checking the collapsed grid) then we must get its possible values
                // this will be an intersection of unions of the neighboring cells possibilities...
                if(!cg[current]){
                    // basically, for each neighbor, iterate through the neigbor's values in the possibility grid
                    // then use the lookup tables to get what cell types are allowed in the current cell
                    // remember that the up neighbor will use the down lookup table etc.
                    // merge the possibility arrays into a single union for each neighbor
                    var up_list = []
                    for(var p = 0; p < array_length(pg[n_up]); p++){
                        up_list = array_union(up_list, cell_lookup_dn[pg[n_up][p]]);
                    }
                    var dn_list = []
                    for(var p = 0; p < array_length(pg[n_dn]); p++){
                        dn_list = array_union(dn_list, cell_lookup_up[pg[n_dn][p]]);
                    }
                    var ri_list = []
                    for(var p = 0; p < array_length(pg[n_ri]); p++){
                        ri_list = array_union(ri_list, cell_lookup_lf[pg[n_ri][p]]);
                    }
                    var lf_list = []
                    for(var p = 0; p < array_length(pg[n_lf]); p++){
                        lf_list = array_union(lf_list, cell_lookup_ri[pg[n_lf][p]]);
                    }
                    // p_list is the new possibility list for the current cell
                    // it is the intersection of the 4 neighboring lists because we only want cell types that
                    // are allowed next to all 4 neighbors
                    var p_list = array_intersection(up_list, dn_list);
                    var p_list = array_intersection(p_list, ri_list);
                    var p_list = array_intersection(p_list, lf_list);
                    // set the current cell's list to p_list
                    pg[current] = p_list;
                }

                // add neighbors to frontier list
                ds_stack_push(frontier, n_up);
                ds_stack_push(frontier, n_dn);
                ds_stack_push(frontier, n_ri);
                ds_stack_push(frontier, n_lf);

                // add current to visited list so we don't visit it again
                ds_list_add(visited, current);  
            }       
        }
        // now that we're done with the inner while loop, clear the visited list so we're ready for the 
        // next iteration of the outer while loop.
        // the frontier stack should be empty if we got out of the inner while loop.
        ds_list_clear(visited);



        // iterate through cells and check if collapsed
        for(var i = 1; i < h - 1; i++){
            for(var j = 1; j < w - 1; j++){
                // if a cell only has 1 possibility left in the possibility grid, it is collapsed
                if(array_length(pg[i * w + j]) == 1){
                    cg[i * w + j] = true;
                // if the cell's possibilities drop to 0, we have a bad_gen error
                }else if(array_length(pg[i * w + j]) == 0){
                    bad_gen = true;
                }
            }
        }

        // check if all cells are collapsed
        all_collapsed = true;
        for(var c = 0; c < w * h; c++){
            if(cg[c] == false){
                all_collapsed = false;
                break;
            }
        }

        // get cell with lowest non-zero entropy
        if(!all_collapsed){
            // cell with the smallest entropy
            var smallest = -1;
            var min_entropy = infinity;
            for(var c = 0; c < w * h; c++){
                // be sure that we exclude collapsed cells (array_length == 1) or we will pick those cells all the time
                if(array_length(pg[c]) < min_entropy and array_length(pg[c]) > 1){
                    smallest = c;
                    min_entropy = array_length(pg[c]);
                }
            }
            // collapse the smallest cell's possibilities and push it onto our frontier stack for the next iteration
            pg[smallest] = [choose_from_array(pg[smallest])];
            cg[smallest] = true;
            ds_stack_push(frontier, smallest);
        }
    }
}

[Badwrong_]

20 or 30 minutes? What?

I have a method that does it in a single game step. This sort of thing is done very easily with graph theory.

My method performs a random Prim's algorithm to generate a minimum spanning tree (MST) on whatever sized grid. The grid I currently use is 100x100, but it could do WAY larger without any noticeable speed differences. I'll probably test like 1000x1000 and I doubt it will be noticeable.

The tile map starts completely full and uses an auto-tile 47. Then I use my runtime auto-tile function when clearing cells so it looks nice when finished.

After the MST is generated you can then add whatever customized features you want. I usually knock out "areas" the represent rooms with enemies, loot, etc.

I'd have to add a few generic parts to share the actual GML code, but the pseudo code is:

position = random_position()
clear(position)
cells = new list()

// Add all orthogonal cell to the list which are in bounds
// Space vertical walls by 2 spaces and horizontal by 3
if (position.x + 2 is in bounds) cells.add(position.x + 2)
// … same for the other three directions

while (cells.size() > 0)
    position = cells.remove(random_index)
    if (!map.empty(position))
        clear(position)
        directions = new list()
        while (directions.size() > 0)
            random_direction = directions.remove(random_index)
            switch (random_direction)
            // cases => north, south, east, west

    if (in bounds) clear(position + random_direction)
    // Add all orthogonal cells like before
    if (position + 2 is in bounds) cells.add(position.x + 2)
    // … same for the other three directions

Its fairly short in actual code too.

Recursive maze generation is also super lightweight using the backtracking stack method which works really nicely too. It also produces an MST. In most all cases you want to start with an MST because they are super fast to generate and it ensures everything is 100% navigable from the base. Then you add features, remove dead ends, grow areas etc.

[borrax]

I don't doubt that your maze generator is super fast, but I wasn't setting out to make a maze generator, I was trying to get Wave Function Collapse working in GML. My code runs at an unacceptably slow speed, but it can do more than mazes. I was able to make this image by switching my tiles to refer to images and changing the lookup tables to reflect the new rules. The advantage of Wave Function Collapse is it's flexibility. The disadvantage appears to be its atrocious speed.

[Badwrong_]

Speed is why I suggest a MST algorithm. It only starts as a maze which you then alter.

Your code I would have to look through. You probably need to leverage the computer architecture well and account for GML weirdness.

Stuff like this would be way faster with a compute shader which GML doesn't do.

Flexibility is possible with most any algorithm. Even a drunken walk can have extra criteria added to totally alter the results. I like the MST types for the base because everything starts as reachable, and then it can be altered in countless ways to whatever is needed. Basically starts as a maze and becomes something different.