Implementing Wave Function Collapse & Binary Space Partitioning for Procedural Dungeon Generation

Introduction

In 2021, for Computer Science Studio 1, I wrote and published three papers. Exploring, evaluating, and finally implementing wave function collapse in video games, with the ultimate purpose to generate a robust algorithm capable of procedurally generating a world. This blog post is an amalgamation of all three papers and my personal experiences with procedural world generation.

I'll start with some basics. What is a procedural generation? In short, it is the creation of data through algorithmic means, rather than manually creating it. For example, when you create a new world in Minecraft, the game procedurally generates the terrain, ores, trees, and buildings. The game doesn't manually place each block, it uses an algorithm to generate the world.

Why procedural generation? There are many reasons, but the two main ones are time and variety. It would take a human years, if not decades, to generate a world as large and varied as what can be generated procedurally. And with procedural generation, you can create an infinite number of worlds, each with its own unique features.

Wave function collapse is a procedural generation algorithm that I explored in my first paper. The algorithm is based on cellular automata, and it operates by creating a wave function that encodes all possible states of a system. The wave function is then collapsed into a single state, which is the starting point for the next iteration of the algorithm.

The first paper was a survey of previous work in procedural world generation. I looked at a variety of different algorithms, and evaluated their strengths and weaknesses. I also looked at how these algorithms could be applied to video games.

The second paper was a proposal for an algorithm to generate worlds using wave function collapse. Wave function collapse is a technique for reducing the complexity of a system while still maintaining all of the important features. I proposed using wave function collapse to generate the terrain, ores, and trees for a world.

The third paper discussed the results of my implementation. I implemented the algorithm from the second paper, and used it to generate a world. The world was generated successfully, and all of the important features were maintained. The world was also generated in a fraction of the time it would have taken to generate the world manually.

Overall, I was successful in my goal of generating a world using wave function collapse. The algorithm I created is robust and efficient, and can be used to generate a variety of different worlds, the final implementation of the algorithm was implemented in Minecraft,

Paper 1 - A Survey of Programmatic Procedural Content Generation Using Wave Collapse Functions for Game Development

Abstract

In this paper, we will survey the Wave Collapse Function (WFC) Algorithm for Procedural Content Generation (PCG) and its historical uses. Through this paper, we will track multiple methods of PCG in the indie & professional game development community as well as depict the evolution of such methods over time.

Introduction

With the emergence of Artificial Intelligence (Ai) & Finite State Machines (FSM) in video games. Games have become more and more immersive over time. In addition to this, with the expectation of publishers to be constantly improving the quality of their games, these games have also been increasing in both complexities as well as immersion & length. Better graphics, as well as overall better games, have not just become an expectation, they have become a necessity

As a result, many developers have opted to create or utilize tools that can speed up development, or automate it entirely. Here lies the world of procedural content generation. Procedural World Generation whilst not a new field, existing for decades has had issues of it being very demanding in both time & space complexity. This requirement of requiring high-end commercial hardware to run in real-time or optimization constraints has prevented PWG from being used as frequently in the past. PCGs however exist in different forms and iterations and have evolved over time. In basis a PCG just converts an input with given constraints into an output, typically up-scaled in some sort. The outputs / inputs, however, can vary, historically PCG has been used for; Poem generation, image generation, audio/sound generation & finally game map generation as well as asset generation.

History Of Wave Form Collapse In Procedural Content Generation

In 2016 Maxim Gunmin's Wave Function Collapse (WFC) Algorithm gathered the attention of multiple indie & professional game developers alike online. Gunmins WFC algorithm allowed developers to procedurally generate both images as well as maps in a realistic, humanized way, being unique and different to the algorithms preceding it. Gunmin's WFC algorithm whilst highly effective in terms of resultant images did not sacrifice in speed either, being faster than many algorithms comparative algorithms utilizing back-tracking instead. Gumins WFC also further deviates from this by using a greedy-search method that avoids blending of textures to create a similar result, popularized by PCG through Texture Synthesis.

WaveFunctionCollapse (WFC) like many other PCG algorithms are based on the foundations of several other algorithms and are improved/tweaked to better suit it's specified use-case. In the case of WFC it is inspired off three distinctive but functionally similar algorithms& concepts; Texture Synthesis (Specifically Discrete Synthesis), Markov Chains & Quantum Mechanics. WFC was also additionally inspired by convolution neural network style transfer (CNN Style Transfer), obtaining strong similarities however this differs from the previous three as whilst Gumin's intent was to capture the rules of how source images was made, neural networks did not solve this use case acting more of a "black box" of inputs & outputs.

Through the implementation of these three algorithms WFC has managed to create a highly flexible & versatile algorithm able to work in all aspects of media generation, whether it be; Audio, media, or text. This versatility as well as a methodological human-like approach to content generation & incrementation through generation has led to even Gumin himself writing:

I noticed that when humans draw something
they often follow the minimal entropy heuristic themselves. That’s
why the algorithm is so enjoyable to watch - Maxim Gumin

WFC at release however wasn't instantly popular. Wave Form Collapse at release was limited in scope, functionality & accessibility. Whilst it was an incredibly innovative piece of software disrupting the PCG scene as a whole in practical implementations with popular game engines such as unity it was lacking & complicated to implement. WFC however through the open source movement has now thrived and has been used in a wide range of games, being used in both indie & commercial games alike. A notable mention of WFC being used in a commercial game is in the game, "Caves of Qud". Caves of Qud uses a modified version of the WFC function, utilizing multiple layers of the WFC successively to combine and merge multiple layers together with a greater variation.

WFC in recent times has also been improved to work independent of a grid system, now being flexible enough to work on graph based systems. Whilst Maxim Gumin's original WFC system was based on a grid-based system, this through community-based updates and forks has been expanded to work on graphs, the super-type of grids. The implementation of this, this has allowed a greater range of flexibility of WFC algorithms and has allowed greater flexibility and utilization in the game-development community as a whole, specifically for 3D development. A popular example of WFC being used in a 3D game, and arguably one of the first implementations of WFC in 3D is in the game ProcSkater, created by Joseph Parker.

Wave Function Collapse Algorithm Explained

The WFC function released by Maxim Gumin is a grid-based PCG function. It works by taking inputs or "tiles" and then breaking them up into small chunks which are then rearranged to create new images, art or levels. Images generated through WFC consists of overlapped or non-overlapped chunks which are transformed being either flipped or rotated based on the constraints given.

This algorithm, unlike similar PCG algorithms does not require back-tracking which greatly improves speed without sacrificing accuracy or quality. WFC algorithm instead mimics concepts of quantum mechanics, specifically entropy to develop its tile sets, starting from a "master tile" and expanding outwards.

In WFC, similar to a Sudoku game, each tile is based on a set of rules. In Sudoku the goal is to fill each grid with a number between 1 to 9 where each distinct row and column can only have each number between 1 to 9 displayed once. Additionally, in every 3x3 grid the numbers 1 to 9 this restriction of the number being displayed only once still applies. When initially generating a Sudoku map if a blank map is given, there is an undetermined number of solutions where each box can simultaneously contain all 9 possible values simultaneously, as a result there is no distinctive solution solving this question.  However, once we keep adding more preset values or tiles to the Sudoku map, the number of available solutions decrease so and so until enough constraints are added that there is only 1 distinctive unique solution to the question.

Similarly to Sudoku, in WFC we start from a starting node and add more and more constraints until there is one distinctive answer or possible generated image. In WFC each tile-map or node has its own set of associated adjacency rules.

For example, as seen in the image above. A tile may only accept a specific set of tiles above it, below it, to the left & to the right of it.

In WFC we start with a cell with the lowest entropy (or biggest restraints), target it, and continue adding restraints until the possible total tiles for that node collapses into a single tile. We then go on a process of repeating this to all the neighbors of the tile, evaluating the possible combinatorics for available for each node and repeating this step until all possible options are exhausted. We then repeat this until all tiles are invalidated by the collapse and the initial cell is removed from the list. We will then repeat the loop finding the next tile with the lowest entropy and repeat the same steps above traversing to all neighbor nodes until they collapse once more.

Constraints in WFC have then been defined through either two approaches; a heuristic approach where an example map is drawn up and the algorithm analyses which tile-sets are valid & which ones aren't. (This works well for tile map inputs). Alternatively, another way is via sockets.
The more common, and arguably more flexible approach of sockets is a system where each side (Top, Bottom, Left & Right) are defined explicitly with metadata containing lists of each object allowed to be placed adjacent to it. This is also further extended and refined by adding variance for symmetrical and asymmetrical objects, having different restrictions based if the object can be reflected or not.

Conclusion & Future Work

In this paper, we have presented a summary of the Wave Function Collapse Algorithm as well as the history, the progression & modifications of the function as well as finally the explanation of the algorithm itself and its related use cases. WFC is a highly flexible and modifiable function capable of media generation in a humanistic form in multiple different mediums. Through Wave Collapse Functions procedural content generation for games can be vastly accelerated, simplifying the game development process or even automating it, allowing a unique and different experience through each play-through or alternatively an infinite and constantly new experience as you play on.

For future work, we intend to modify the heuristics and implementation of the WFC algorithm as a whole, optimizing the processing speed, emphasizing multi-threading & parallelization as well as modifying and implementing a more complex constraint algorithm for adjacent neighbors based on WFC. Through a more heuristic-based approach, we intend to better procedurally generate outputs via WFC in 3 dimensions emphasizing realism. We are hopeful from a more realistic and optimized WFC function designed for 3-dimensional applications WFC can be expanded upon from rogue-like games to the entire game genre as a whole, leading to a more immersive & unique gaming experience for users.

Paper 2 - Programmatic Procedural Map Generation Using Wave Collapse Functions (WFC) For Game Development In Top-Down Games

Abstract

In this paper, we will explore the issue of programmatic procedural map generation for video games in the 2D top-down rogue-like genre. Through this paper, we will cover multiple forms of procedural content generation (PCG) in the indie & professional game development community as well as propose & lay out our plans for such a system using the Wave Form Collapse (WFC) function.

Introduction

Procedural map generation has been a staple for rouge-like games since the early conceptions of the video game genre in the 1980s. Rouge-likes can take take variety of different forms, aesthetics and game-play mechanics, however, they all share the goal of trying to transverse a dungeon or an arena to the next level. Early on in the genre’s conception, game-play designers played close attention to the hardware limitations consumers pcs contained. In this time every byte counted on computers as storage was limited. Game designers thus chose to use procedural map generation in their games, making it more compact & increasing it's playability.

In modern times Procedural world generation (PWG) has become an increasingly popular trend, making the game significantly more playable, allowing new features such as dynamic difficulty as well as giving the user a unique and varied experience through every playthrough. Whilst these early Procedural World Generators (PWGs) were often crude & basic, often containing unnatural or machine-like terrain with little to no consistency and even fewer regards to good level design rules & guidelines, progress in this field has been slowly made to improve the performance and results of these algorithms.

Many new algorithms have come along to try to correct and improve on the pitfalls that these early algorithms contained. Most of these are slow in performance and require significant processing power to compute terrain in real-time. In addition to this many of the fast alternatives to these algorithms also suffer from failing to adequately create playable maps in regards to design rules as well as occasionally failing to create completable maps. Whilst many of these algorithms have come along to implement more humanistic map design criteria, many of these implementations have failed or provide marginal benefits to previously used PWG methods. As a result, development of such algorithms of PWG has been stagnant.

In this paper, we intend to explore such algorithms used in PWG and analyse what has been done well, evaluate each given method and through this propose and develop our own flexible programmatic procedural map generation function, intended to contain both variation, humanization as well as customizability, allowing developers to create better looking & overall more playable procedurally generated maps.

Current Solutions To Procedural World Generation (PWG) In Top-down Games

There have been numerous implementations of Procedural World Generation (PWG) functions in both the indie & professional game developer communities. Whilst most are adapted to their specific game engine & required application, the logic of such algorithms generally stays the same, being agnostic of languages and use cases. A generalized outline of some of the most popular PWG algorithms is listed below.

Markov Chains

Markov chains are one of the oldest yet most effective methods of Procedural world generation (PWG). This method has been widely used over the years and has had multiple different variations implemented in many multi-dimensional models.

Markov chains work through a statistical decision tree process. Through this, a state space is constructed with transitional properties between states such that the next state for each iteration is dependent on the current state. With terrain generation, the process expands outwards from a starting point and is evaluated by comparing the possible states of its neighbours.

Markov chains are one of the oldest yet most effective methods of Procedural world generation (PWG). This method has been widely used over the years and has had multiple different variations implemented in many multi-dimensional models.

Markov chains work through a statistical decision tree process. Through this, a state space is constructed with transitional properties between states such that the next state for each iteration is dependent on the current state. With terrain generation, the process expands outwards from a starting point and is evaluated by comparing the possible states of its neighbours.

As a result of this function, Markov chains due to their simplicity have been used in many popular 2D platform games, such as Angry Birds & Super Mario Run. \cite{AngryBirds} \cite{SuperMarioRun} People who have observed terrain generated by these chains have said that they cause aesthetically pleasing and consistent levels, however, this does not correlate with playability as Markov chains also suffer from the inability to distinguish map design rules and if a generated map is playable without a secondary backtracking or pathfinding algorithm. \cite{SamSnodgrassEatl:TBD}

Cellular Automata

Cellular Automata is a discrete mathematics-based model of computation based on finite states. The program functions by containing a grid with a list of cells each with its finite states, additionally, restrictions on such states can be programmatically added. The program once run, then executes iterations of the program based on the conditions of its adjacent neighbour cell based on the set of rules. Whilst this is primarily a model used in games for modeling environmental systems, like heat, rain & fluid flow. It has also been used in limited cases in PWG. Whilst this model isn't primarily intended or designed for PWG there has been a varying degree of success in using this model to create realistic albeit random-looking generated caves through this model.
\cite{TForsyth:2002, PSweetser:2005}

Binary Space Partitioning (BSP)

Binary Space Partitioning (BSP) is a highly popular & utilized mapping technique used in multiple prominent games, like Counter-Strike: Global Offensive. BSP through a system of recursively dividing space, generates an object with the data structure of a BSP tree. Through these BSP mappers can create some of the simplest yet most prominent rouge-like dungeons - rectangular dungeon maps.

Through binary space partitioning, it allows the algorithm to split a space up into several randomly sized rectangles of where a pre-assembled room component will be placed. Through this dungeons can be formed. These separate dungeon rooms are then linked through a secondary backtracking algorithm that checks & ensures all associated dungeons rooms are linked together. From this, a highly detailed, randomized yet consistent & solvable dungeon can be generated.

Machine Learning

Machine learning, unlike the algorithms mentioned previously, offers a unique approach to procedural world generation. Similar to Markov chains they are also heavily reliant on statistical modeling, however, differ as the procedurally generated output is based or transferred from the data-set it is trained on, giving it weighted biases. With Machine learning models such as Generative Adversarial Networks (GANs), the neural network is trained by being given a set of hand-generated maps which are then fed to the network capturing high-level features. From this, the model is further trained in 'learning' these high-level rules and interpolating them into a set of weights which allows it to generate its maps.

Whilst GANs also don't offer guaranteed playability in their maps and occasionally require back-tracking or pathfinding to fix/evaluate, these properties are often initiated by the data it is trained on, as such one of the rooms, it was trained on also contained this unsolvable feature. GANs additionally whilst following the high-level rules of map design and having great success in image generation, often fail to capture the nuisance structural features and details rooms created by mappers contain required for a well-defined level. This paired with the network requiring tens if not hundreds of pre-generated maps for training before the network can function as well as overall having lower success rates, being more complicated, less editable, being unpredictable & performance intensive compared to other functions have made machine learning models not a popular method of PWG in game development.

As a result, this approach isn't ideal for game developers generating new levels for their games, but rather for pre-existing games with community support. This allows the machine learning model to have a greater data set to base maps off and overall lowers the unpredictability of the model, with the increase of data proportionally increasing playability.

This approach, however, alternatively may be useful for other processes in procedural world generation such as in the difficulty evaluation & size evaluation sections. This as an additional tool to back-tracking & pathfinding may allow developers to more accurately determine & evaluate the difficulty of automatically generated maps without requiring to play them themselves. This in turn can minimize quality control issues as well as reduce the overall unplayability of maps from some of the other algorithms previously mentioned.

Comparative Benchmark Between Algorithms

Proposed Solution Using Wave Form Collapse (WFC) Functions

The proposed solution to the problem of creating realistic & detailed procedural worlds for top-down 2D games through programmatic procedural content generation is listed below.

Proposed Implementation Of WFC

Through the implementation of a relatively newly created algorithm, the Wave Form Collapse (WFC) function as well as adding elements of Machine Learning & Binary Space Partitioning we can create a robust, automatic algorithm capable of being highly flexible and modifiable to the developer.

Through utilizing the Wave Form Collapse function which works similar to Markov chains however also emulating entropy through its pseudo-quantum-mechanics inspired randomness it allows us to create seemingly random but humanized and aesthetically pleasing terrain maps.

This conjoined with Binary Space Partitioning, separating the square grid into sections where an individual WFC will run independently of one another, being later linked through backtracking and a machine model evaluating the finalized solution checking its difficulty & size, should create a highly unique but also highly structured procedural map for the users to traverse.

Benefits Of The Proposed Solution

Through this proposed algorithm we increase the overall success rates for the generated map to be playable without the need for backtracking or user intervention, in addition to us containing the distinct block structure Binary Space Partitioned maps have whilst including the humanistic, however, quasi-randomness the Wave Form Collapse provides.

As a result of this, our maps should contain distinctive & separated arenas for players to battle in whilst also having each room being uniquely generated & different, unlike most BSP based dungeons which use a sample set of pre-assembled dungeon rooms.

These maps are then evaluated, checked and given a ranking in both; difficulty, size, playability & aesthetics based on a machine learning neural network. Through this, we can ensure the generated map is of high quality and is proficient for a user to play, without being required to check the map beforehand. This ensures & allows the game developer to be positive that the resultant map is of quality for the user to play and assists in minimizing the pitfalls other algorithms such as Markov chains & Cellular Automata contain when developing maps.

Challenges Involved

The proposed algorithm above is quite a complex & quite intensive algorithm requiring heavy domain knowledge both on statistics & machine learning. Additionally to this, optimization and integration of these multiple systems may cause an issue and will require extensive Data Structures & Algorithms (DSA) knowledge.

A list of potential issues in this proposed algorithm is as listed below:

• Incompatibility / heavy dependencies on multiple programming languages. E.g. Python for machine learning, C# for WFC & BSP
• Issues with over-training / introducing biased or incorrect data into the machine learning model
• Balancing the reward functions & sensitivities for the weight functions
• Issues with creating a consistent map & debugging this due to it's randomized and procedural nature
• Allowing this code to be intuitive and flexible for other researchers & game developers to use
• Ensuring speed, accuracy & fidelity to the proposed algorithm as this requires multiple separate but highly connected systems
• Issues with logic/domain knowledge outside of the reach of the researcher, which may require consultancy from experts / the research supervisor

Conclusion

In this paper, we have explored the problem of creating realistic & varied programmatically procedurally generated maps using procedural world generation (PWG) in-depth for 2-dimensional top-down games. We have explored previously used solutions in the procedural world generation (PWG) field such as; BSP Trees, Cellular Automata & Machine learning. We have evaluated such methods and have proposed a new modified system emphasizing and collecting the advantages of all methods whilst trying to minimize the overall flaws these algorithms create such as occasionally creating unsolvable maps or undetailed and seemingly random unintuitive maps. From this paper, we are hopeful we can utilize the Wave Form Collapse (WFC) function to assist in making a more immersive & unique gaming experience in the future for users.

Paper 3 - Implementing Procedural Dungeon Generation In Top-Down Games Using Wave Function Collapse (WFC) & Binary Space Partitioning (BSP)

Abstract

In this paper, we will introduce & explore a solution to creating humanized realistic dungeons or maps in the 2D top-down rogue-like genre. This paper will explore a proposed solution, combining both the strengths of Binary Space Partitioning and Wave Function Collapse to create a highly flexible yet robust algorithm capable of autonomous procedural world generation with minimal errors.

Introduction

Procedural map generation in rogue-like games has been a staple since the conception of the genre in the 1980s. While rogue-likes can take a range of different forms, aesthetics & game-play mechanics, they all share the common goal of trying to transverse a dungeon to the next level. Early on in the genre's conception, game-play designers paid close attention to the hardware limitations consumer PCs contained as every byte counted, with hardware space being limited. Game designers, as a result, opted to use & discovered the world of procedural content generation to increase both replayability and customizability.

While in the genre's early conception, procedural content generation (PCG) was necessary due to hardware constraints. The link between procedural world generation (PWG) and rogue-likes has been closely linked ever since and has become an iconic key aspect of the genre's allure. Through constant iterations and innovation in procedural content generation methods, this field has slowly but steadily improved on the pitfalls these early algorithms contained, increasing both overall accuracy & performance. However, these modern algorithms are still incredibly performance heavy and require significant processing power to generate and evaluate playable maps unsupervised in real-time.

In this paper, we intend to implement & evaluate our own programmatic procedural world generation function capable of both variation, customization, and aesthetics based on Wave Function Collapse (WFC) Functions & Binary Space Partitioning (BSP).

Identifying The Problem

Multiple procedural world-generation techniques have been used over the decades, such as Markov chains, cellular automata, BSP trees, texture synthesis, machine learning & many many more. These, in one way or another, have been lacking in either customizability, accuracy, or speed. While each of these proposed listed models has its associated benefits and weaknesses, a well-rounded algorithm addressing all three factors has not been achieved. Whilst some have strived for great performance many of them as a result have sacrificed uniqueness and/or playability and vice-versa. Listed in the table below is a detailed breakdown of such historic algorithms with their associated strengths, weaknesses & features.

This research paper aims to explore & attempt to solve the issue of creating aesthetically pleasing yet optimized dungeon maps through autonomous means using Procedural World Generation (PWG) methods.

Settings For Experiment

Setup & Tools

The tools required for this experiment are minimal. For this application to run we require:

• Minecraft (Version 1.6.4) Installed
• .NET Framework
• Visual Studio 2019 Community / Enterprise Edition
• Benchmarking Software (E.g. A Timer & Visual Studio)

Proposed Solution

The algorithm proposed to create unique aesthetically pleasing maps and have a substantial degree of conformity, adhering to high-level map design rules, and consistency and division between levels consists of two algorithms—the Wave Function Collapse (WFC) Function as well as Binary Space Partitioning (BSP).

Through WFC and BSP, we can, as a result, leverage the benefits of both algorithms while also increasing performance.
Through the recursive nature of Wave Function collapse, parallelization or optimization of the algorithm alone is not feasible. It uses an exorbitant amount of memory and processing power to compute exponentially increasing as the size of the grid increases.

However, we can divide the map into several blocks or dungeon sets through binary space partitioning, which all contain unique instances of Wave Function collapse. Through this, we can contain the rigid structure of binary space partitioning, having its iconic rectangular dungeon designs in addition to having its easy back-tracking algorithm to combine levels and with the strengths of Wave Function collapse, making each dungeon room unique and distinct from the rest, while still being playable.

Through the separation of the map into several Wave Function collapse chunks instead of one large field, we also allow the possibility of parallelization where we can run multiple instances of Wave Function collapse concurrently, increasing overall performance as well as reducing the overall time & space complexity required to run this algorithm.

Through this proposed solution, we also eliminate the downfalls of binary space partitioning, where variation is typically limited and allows continuous / non-rectangular maps to be implemented if desired. Wave Function collapse, in addition, allows us to create unique, distinctive maps with a pseudo-human aesthetic, being aesthetically familiar to hand-designed levels.

This, paired with the customizability, with outputs being dependent on the conditional restrictions placed on neighboring nodes as well as the associated weights allows our algorithm to be significantly more flexible than other conventional map generation methods, such as machine learning, while also containing significantly better performance & playability metrics compared to other methods, such as; Machine learning, cellular automata, Markov chains & texture synthesis when used on their own.

Implementation

The proposed implementation of the algorithm is a hybrid design, implementing both Wave Function Collapse (WFC) and Binary Search Trees (BSP). The map is uniquely sectioned into several areas or rooms through a quick run of the BSP algorithm on map initialization. These rooms are then traversed through and generated through Wave Function Collapse. The flowchart for the proposed algorithm is given below.

Alternatively, the pseudocode implementation of the algorithm is also provided, available below:

After this pseudocode was designed, the code was then implemented in Minecraft using C#. This platform was chosen as it is straightforward to use, debug & quickly prototype and edit input values for the WFC algorithm with minimal effort. It, in addition, is also a platform the scientists in this paper are deeply familiar with.

Result

The figure below shows the input given to the Wave Function Collapse section of the algorithm. The white represents walls, chests represent treasures, TNT represents hazards & water represents water. The algorithm takes this 25 x 25 grid and divides them into 5x5 kernels or sections, which then can be rotated, transposed, and combined with other kernels within each given binary space partition block or 'room.' The selected kernel is chosen based on quasi-randomness emulating entropy with each block recursively comparing itself to its neighbors until the kernels state converges.

The algorithm then takes the given Wave Function Collapse input and the given output size, in this case, 50x50, and firstly partitions the map into several binary space partitions, signified in green, in figure 4. Once these binary space partitions are initialized, each one is then propagated and initialized through the input given by the wave function collapse algorithm in the figure shown above, figure 3.

In the figure shown below, figure 4, we can see the output of the resultant algorithm 50% completed. This shows both the raw binary space partitioning as well as the detailed & converged wave function collapse rooms respectively.

Discussion

The resultant of the proposed combined algorithm utilizing both Wave Function Collapse and Binary Space Partitioning is shown below. The implementation of This algorithm due to time constraints and the game engine used resulted in the very slow implementation of the proposed algorithm, not containing parallelization to run more efficiently. This, however, benchmarked compared to non-binary space partitioned algorithms led to exciting results. While WFC on its own led to impressive results, creating humanistic & aesthetically pleasing levels. The time taken for the algorithm to determine the value of each node or 'block' increased exponentially as the size of the input and output increased. This is most likely due to the recursive nature of Wave Function Collapse, and by reducing the size of n, the algorithm significantly increases in speed.

This implemented algorithm also had issues with it being buggy & inconsistent for increasing complex designs with its back-tracking algorithm spiraling into infinite loops occasionally exiting due to luck from the pseudo-entropy randomness given. This is most likely a result of the short time frame given for the implementation of the wave function collapse algorithm and is not likely caused due to the simultaneous use of binary space partitioning & wave function collapse.

The use of binary space partitioning also allowed these rooms to continue to keep the traditional rectangular dungeon room design standard from BSP while also allowing these rooms to remain unique and not be provided by a list of pre-assembled rooms, increasing variation while also maintaining playability.

An additional implementation/modification of the back-tracking algorithm for adding corridors may be needed, whereas it also adds or seals dungeon rooms in case of WFC failure. This issue can be highlighted in the figure given below circled in yellow, where the WFC algorithm fails to properly seal the room.

The Future

Whilst this solution did have it's pitfalls, specifically with speed, due to the lack of optimization. This solution is definitely sound and has the opportunity to scale into a highly successful and robust algorithm in the future. Further proposed work in this algorithm in the future include:

• Parallelization, allows the algorithm to perform significantly faster and asynchronously from each other, allowing each binary space partition to wave function collapse simultaneously instead of contiguously
• Further data structure & time-complexity optimization, utilizing divide & conquer algorithms and optimizing the overall time complexity
• Hardware multi-threading utilizing CUDA Cores or FPGAs as dedicated hardware
• The addition of a convolutional neural network model to evaluate the size & difficulty of maps for the unsupervised creation of maps with consistent playability for users

Conclusion

To conclude, this experiment was an overall success; the combination of Wave Function Collapse & Binary State Partitioning resulted in a highly flexible & robust algorithm capable of significant parallelization, accuracy, aesthetics, uniformity & uniqueness while maintaining both high levels map design rules as well as containing intricate details. The algorithm, however, had shortfalls, specifically with speed & its recursive back-tracking algorithm where it occasionally fails and spirals into an infinite loop; however, with adjustments & better data structure optimization, and further implementation of advanced algorithmic designs such as divide & conquer techniques, this algorithm can significantly improve.