Project Description

This project was a culmination of learning and interest in procedural generation algorithms. The focused algorithm here is Wave Function Collapse.

Wave Function Collapse

Wave Function Collapse works by using pseudo-random choices on a set of predetermined options. For each choice there is a potentially limited number of options often decided by its neighbors.

In the case of Sudoku, each tile has a set of possibilities it can be at that given moment. The count of these possibilities is its entropy number and on a blank board all tiles have an entropy of 9 as each tile can be any number 1-9. Now go ahead and try choosing a tile and possibility, if you have entropy toggled on you will see that all squares contained in the column, row, and sub-square will have their entropy updated to one less. Per rules of the puzzle, these tiles can no longer contain your choice and as such their entropy is updated.

This is essentially how Wave Function Collapse works. Depending on where it is used a developer will set up constraints of each choice to be applied to neighbors upon a decision. At which point states are randomly picked from the entropy set for each tile, updating the entropy set for those related, and then repeating the process on the next tile.

A good example is the Solve Singulars function. In easier Sudoku puzzles some choices are freely given by using related neighbors to reduce your options, or rather entropy, to one. This function will find all tiles with a entropy of one, "solve" that tile and update all its neighbors with its new knowledge. If this update reduces any other entropies to one it will repeat the same actions on that tile as well. Eventually resulting in either a solution or a requirement for more clever methods/random chance.

Image Generation

Another example can be in randomized image generation. Say a game developer wants to build a randomized backdrop to a sewer level in their 2D game. For this case we decide on a set of 5 small square images. One base wall square, a straight pipe square, a corner pipe square, a T-pipe square, and finally a mossy wall square. To transform these into a full image we then add some constraints. Lets say a T-pipe needs to have either a straight pipe or a corner pipe connected on its open sides. We'll do the same for the corner and straight pipes. However on these we also add constraints for the non-pipe faces allowing for the neighboring of other non-pipe faces and tiles. The base tile being base can simply neighbor any non-open pipe face tile but lets say we want to do something special for the mossy version. We want our backdrop to have large mossy patches so we decide to give a higher chance that a mossy patch will neighbor another. Lets say a moss tile gives an extra 50% probability that a neighbor is another moss tile (if possible) with the other 50% being something else.

Now that we have our constraints we can divide our image bed into a grid of squares like in our Sudoku board, each with full entropy. We can then choose a square on the board and randomly assign one of the 5 options. This now triggers a reduction in future possibilities for all 4 surrounding sides. If this process continues with one of the tiles neighbors eventually a fully deceivable image will be displayed for use in our game complete with large mossy patches and long pipe chains spanning the image.

Granted there are some more technical parts I left out but I believe this is a good simplification of the task at hand.

Documentation

Board

The board displays the current state and accepts input from the user through clicking on an unsolved tile. If a tile is selected the user can then choose an option from the left column of available possibilities which will be filled in on the puzzle board.

Subsequently when a user hovers their mouse over a tile, a display to the right of the board is updated showing greater information and behind the scenes about that specific tile.

Generate From JSON and Generate New

These options are pretty self explanatory. The Generate New function builds a new random board on the spot starting with a solution and working backwards to give something solvable. Generate From JSON takes from a collection of 1000 pregenerated boards for increased speed on loading new boards.

Solve Singulars

This function scans the board for any tiles with an entropy of one and confirms its solution while updating the entropy of all neighboring tiles being those in the same column, row, and subsquare. While updating if any squares are reduced to one the process is repeated starting from that square.

Eventually this scans the entire board resulting in there being no tiles left with a single possibility.

Solve Pairs

The name of this function is a little deceiving as it does not actually get a solution to a pair of items. Rather this function uses an interesting trick in that if two tiles in the same column, row, or subsquare have the same possibilities and an entropy of two, all other tiles in that column, row, or subsquare cannot be either of those possibilities.

Other than that this function works similarly to Solve Singulars in that it scans the board looking for these pairs and then updating neighbors if a pair is found, calling Solve Pairs or Solve Singulars if any new pairs or single entropy tiles are produced.

Solve

This function runs the previous two then if the puzzle is still not solved a choice is made on the lowest entropy option left followed by updating neighbors as such and doing the same for any singulars. If an error is found it reverts to where the choice was made and tries again with a different choice, also known a recursion.

Originally I wanted to do this project without using recursion though after some time in the project and research I realized that that would be infeasible. The functions required to solve without using recursion would likely take as long if not longer than just using recursion.

If this function is used and squares are listed red or the Check Conflicts option returns red, a solution is not possible from the position in which the solve was initiated and the board needs to be cleared. At some point I plan to add an undo function to user choice but for now any choices made are permanent until fully cleared.

Toggle Entropy

Toggle Entropy toggles a red number the displaying the entropy of each non-solved tile. ie. If a tile can be 1, 4, 5, and 7 then the entropy number will display 4 signifying the tile has 4 possibilities at this moment.

Check Conflicts

This is mostly a test function that scans the board for any incorrect tiles. If any are found the conflicting tiles are highlighted in red.