Logo
Published on
views・

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

Side-Project
Authors
Table of Contents

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.