When coming up the initial idea of the game we quickly decided on the style of game that we wanted but I then needed to find a way of incorporating a specialism into the game. The initial ideas I had for my specialism in this project was either the topic and implementation or Artificial Intelligence or use of Procedural Content Generation (PCG) more specifically in the form of Wave Function Collapse (WFC).
As we discussed the game more and begun fleshing out our ideas we realised that the wanted to include a type or overworld and underworld, and in this underworld there would dungeons. This all but made my choice for me to make my specialism PCG related. As mentioned before the consideration for the use of WFC was in my mind from before starting the course so this makes a create opportunity to try to implement WFC.
My first course of action was to begin researching more into the academic side of WFC. I already had base knowledge of the WFC thanks to this YouTube video →
https://www.youtube.com/watch?v=2SuvO4Gi7uY&ab_channel=MartinDonald
This video helped me to understand the basics of WFC by explaining in terms of Sudoku. In the game of Sudoku there are 9, 3x3 grids, in these 3x3 grids you need to have the numbers 1-9 but on top of this each row and column in the grid can only have one of the numbers between 1-9 in each row and column.
Example of a uncompleted sudoku grid
Example of a completed sudoku grid
The reason I bring up Sudoku is because you can think of the blank squares in sudoku as being in a superposition of all the numbers but once you start to fill in the numbers in the grid the possible positions of the number decreases based on the last number to be filled in. This is similar to the WFC as it performs the same type of algorithm but using a tile set where each tile can only be placed based on the their relationship to other tiles. After each tile is placed this then limits the tiles neighbours to a certain type of tile as well and this process is performed until a valid solution is found.
Once it was decided that we would be having dungeons in the project I began researching WFC in more detail, the first paper that I read was ‘Automatic Generation of Game Levels Based on Controllable Wave Function Collapse Algorithm’ by Darui Cheng, Honglei Han and Guangzheng Fei. In this paper, an improved version of the WFC algorithm was proposed where the use of global constraints allow for a tile to appear a maximum number of times or a minimum number of times. This allows maps to be created that can only have a certain number of tiles such as the example below:
There can be as many water tiles There can only be 20 water tiles which create more land
Notes made on the paper
The next paper that I read was ‘Automatic Generation of Game Content using a Graph-based Wave Function Collapse Algorithm’ by Hwanhee Kim, Seongtaek Lee, Hyundong Lee, Teasung Hahn and Shinjin Kang. This paper purposed that the use of graphs could be used in WFC which extends the use of a standard WFC system witch is purely grid-based. The fundamentals are the same between the two but the graph-based system allows for the use of obtuse shapes as shown in the image below.
Basic representation of a graph-based WFC
A graph-based system that has more connects between nodes.
As seen in the example above, because nodes ‘A’, ‘B’ and ‘C’ can only link to the parent node of ‘A’ this means that the respective tile can only be connected to ‘A’ resulting in tiles ‘B’ and ‘C’ always being surrounded by ‘A’ tiles but ‘A’ can connect to all tiles.
Notes made on the paper