Why I use Wave Function Collapse to create levels for my game

wave function collapse maybe you've heard of it maybe you haven't maybe you think it's just a quantum mechanics thing maybe you already know what this video is about well i'm no physicist just a guy making a game about a robot who loves plants so let me explain what quantum mechanics has to do with a silly botanical robot game and why i'll be implementing the wave function collapse algorithm into my game [Music] so since the dawn of gaming randomly generated content has been a mainstay figuratively blowing up when minecraft became popular and this is awesome infinite random generation means infinite content right well not exactly i think as a solo indie dev random legendary content is a quick way to get a lot out of relatively little code and effort there's a catch imminent randomly generated content can also be infinitely boring so you do have to be a little careful with how much you rely on it this is where i think some games have gone a little wrong but that's another conversation anyway back to robot plant game i want randomly generated content for it but at the same time i want to make sure that it's easy to keep it interesting and not too samey throughout all the levels how do we do that well traditionally i would say use some noise algorithm to generate an image and process it down until it looks approximately like a level layout that's a fine approach it's worked for a lot of people but i want to be able to easily change up how levels look and feel with how much effort and be able to give constraints to my level generator easily like this plant needs to be at the center of a large room or water should never border lava and other things like that and that is where wave function collapse comes into the picture an algorithm that takes a source image and can generate infinite random images from that one source image in our case random but similar level layouts so we want to generate levels not using noise but with more control over generation and with restrictions on where specific objects should be wave function collapse is perfect i spend about 30 seconds in drawing out a 2d version of what i want a level look like i feed it to the algorithm and i get back infinite level layouts that look like the one that i drew originally so how does it work well wave function collapse is an algorithm that basically solves a set of constraints extracted from the input image to generate infinite novel outputs what it does is it takes our input image and breaks it up into patterns of a predetermined size these patterns within all the possible values for every pixel in the output image so you could say that each pixel starts as a superposition of all of its possible values this is where the physics terminology comes from the algorithm then proceeds as follows find the pixel with the least entropy that being the one whose color we're most sure of and collapse it into one of its possible values then we propagate this information out to neighboring pixels which is the core of the algorithm see not any pixel can be alongside just any other pixel the patterns that the input image was broken up into also determine how pixels and groups of pixels are allowed to connect with each other and in what amounts in the output image this is the information that we're propagating out if a pixel collapses to a certain value then it's highly likely that some of its neighbors can no longer become certain colors while keeping to the adjacency rules defined by the original image this process observe collapse propagate observe collapse propagate just continues until every pixel is in an observed state or there's a contradiction somewhere in the algorithm fails but don't worry about that and that's basically it and as an aside which isn't really relevant to our level generation the algorithm doesn't even need to work directly with pixels i'll link a demo tool in the description which has a model of wave function collapse that works on tiles made by oscarstorba you can play around with to get a better understanding of how things work [Music] so now that we've got our basic overview of the algorithm let's go out and implement this for real [Music] so the very first thing to do after getting in the header boilerplate and a bunch of utilities headers included is defining the type of our function collapse struct the template parameters here being the backing type of our pixels the number of dimensions since we kind of want to write the code as generically as possible for later reuse the size of the patterns the size of the bit set or really the number of patterns that we're going to use and a vector type [Music] next up we forward declaration structures our pattern which will represent a pattern of course our element which represents a wave element and the wave itself that will be collapsed then we define some useful function types those being the function which selects the next cell to collapse in a way the function which collapses the cell or picks its pattern and then finally a simple callback function this will be used to make visualizations while the wave is being collapsed then we can define the pattern structures give it a unique id the frequency with which it's found in the source data the value or literal pixel value that the pattern has and then the data around the pattern in the source data which is used to compute whether or not a pattern can be adjacent to another pattern and then a bit set of the ids of valid patterns on every other side of this pattern which is just used for speeding up the propagation process with our pattern structure find and some hastily implemented comparison and hash operators we can get to the wfc struct itself or the parameters for the actual wavefunction collapse starting out we have our input data and all possible patterns for each pixel followed by those functions that i mentioned earlier then a bit said representing a mask of the pattern ids actually used a random generator flags for extra parameters and that propagation function that i mentioned earlier we also define for extra generic completeness and reusability the behavior of the input when it reaches a border with this border behavior in them so with that all out of the way let's crack open our constructor and start actually gathering patterns from the input data so the first thing to do with this very convenient and dimensional array 4-h function is to loop over all of the pattern data and try and construct a pattern at every possible location in the source data pretty simple to do that we need to first find this data add function which gathers the data for a pattern at a specified position in the input data but first fixing a quick design mistake and replacing this make pattern function with an actual constructor for the pattern structure like there should have been before i started recording this then we defined the data app function which gathers data of course according to that border behavior parameter [Music] now to make sure that we don't end up spending any more time with this algorithm than we need to be we define a deduplicate function that removes duplicate patterns in the current pattern set and then there's all this stuff which basically adds for every existing pattern that was gathered out of the input data if the flags specify it all the possible permuted rotations and reflections according to the dimension of the wave function collapse that we're performing i would go through a more in-depth explanation of this but this video was going to be kind of long already and this part would take a while so we're just going to really quickly skim over this you can just assume that all the code that i'm running is uh doing what i say it's doing with all of those patterns and you can look at the github if you actually want to see how the multi-dimensional reflections work rotations happen only in two dimensions however at the end though we de-duplicate again because you can imagine that adding reflections and rotations of certain patterns will probably also lead to adding a bunch of duplicates into the pattern set which we don't want to deal with now that we have our pattern set we can actually figure out which patterns in our set can be adjacent to each other on what sides or how they can be neighbors this is just brute forced with a sweet sweet o n squared time complexity for the number of patterns in the set i did bring the total processing time down though if not the time complexity by slapping an openmp parallel floor on top of the for loop which should uh speed things up then we need to do frequency calculations this is some of the more complicated stuff and it's usage in this algorithm so i won't go too in depth with the explanation basically each pattern has associated with it a number representing the number of times that it occurs in the source data this is how we ensure later on in the algorithm when we're selecting which pattern to collapse different wave elements to that we end up with approximately the same ratio of patterns in the output data that we got in the source data all that info and the processing around it is contained within this one frequency number on each pattern [Music] after creating that mask of which patterns are actually going to be used out of our whole bit set we can actually initialize and start to generate and collapse a wave so we started by defining our wave interface which just has a collapse function on it and will tell you if it had a contradiction somewhere where it was collapsing the wave then we can go under to find our wave struct which includes all of the wfc parameters the size of the output wave the vector of elements that will make up the way of what we're collapsing it optional preset data and the total number of elements that have been collapsed [Music] finally we will define our wave element which basically just stores the position that it's at and a bit set representing the superposition of all of the possible values that that wave element or pixel in our case could take on additionally there are some values for calculating the entropy but we're not going to worry about those elements also store their own value once collapsed which makes it easier to convert them back into our output data after defining the initialization routine for each element we go on to write the apply function which is one of the most important functions in this entire algorithm basically takes a list or a bit set in this case of the possible legal patterns left for an element and then merges it with the element's current possible patterns this is basically how the algorithm collapses pixels if we've applied a mask that only leaves one possible pattern remaining then we know that the element has to collapse down to that pattern and after the definition of a few extra functions for collapsing and other housekeeping we have our wave element and finally we can write the bulk of the algorithm which is the wave collapse function [Music] this will start out by initializing the element vector using the element initialization function we wrote earlier this is also an easy candidate for parallelization with openmp after initialization the function will load and pre-collapse any preset wave values if they're specified before moving on to our core loop of observe collapse and propagate the first function to define here being the observe function it's pretty simple all it does is it takes an element according to the next cell function that we gave the wavefunction collapse and then it collapses it using the pattern function that we gave the wavefunction collapse that's what selects which pattern that is going to collapse to if there are multiple options and finally we have last but not least the single most important function in the algorithm the propagation which takes the changed value of a wave element and propagates it throughout the rest of the wave telling each element's neighboring elements how its superposition needs to be updated according to the value of the element being propagated this is done through constructing what i've come to call super patterns which is a superposition of all the possible patterns and their values around each element that an element could still take on according to its superposition and then applying that out to each neighboring element of the wave element whose value is being propagated in the process if there remains only one possible value that an element can take on then it's also collapsed to that value and propagated out accordingly and well that's uh that's basically it we start by propagating the collapsed element we find its neighbors we constructed super patterns then we apply them out to neighboring elements if those element superpositions change then we propagate those elements as well until there's nothing left to change collapsing elements in the process of course the final thing to do though once the wave is collapsed is to take all of the values out of the collapse wave elements and write them back into the output image [Music] add in the pattern selection and next cell selection functions really quickly and then we have our entire wavefunction collapse algorithm ready to go this is obviously not the first time that i wrote this code and this is kind of a carbon copy of what i have existing in my code base so on top of that for the specific purposes of this video and because it looks cool i used sdl to make a really quick visualizer which created those visualizations that you saw earlier in the video this is where that propagation callback from earlier came in handy for those of you wondering so with the whole algorithm implemented and working you're probably wondering how does this actually look in practice as a level generator well i really quickly do this sample level map so let's slap that into our new soupedup level generator including wavefunction collapse and to see how it looks well it looks about like we took one of those images that we generated and then we applied it very roughly to the level generator nothing different than what we expected but this level generator will really shine when there are actually more restrictions that need to be introduced from different gameplay elements and more different types of levels basically a good jumping off point for us with the cool algorithm behind it a different approach to some random levels wave function collapse and level generation implemented it's also been about two months since i last posted a video about the game so let's go through a quick lightning round for everything else that's changed since my last video first change as you saw in the level generation demo is the tiles which are blocking the player are now turn transparent this is just to make sure that the player can always be seen even if they go behind a wall this was easier said than done though the solution involves getting a mask of the player entities bounding box and then casting rays through the world into that box to see which tiles they hit it's still relatively primitive but it works after a lot of trial and error with different strategies and the player can always be seen now at least the second and largest change slash refactor is that i decided to abandon the entity component system architecture in favor of a more traditional object-oriented approach to entities basically as i was trying to implement more entities i found the ecs hurt more than it helped in terms of code complexity so i used a few days to refactor a very large portion of the code base and i haven't really looked back since with the refactor done though this means i could give our robot botanist some new toys to play with and by toys i mean plants of course those being the daisy and sunflower that you can see here i've also started work on a very important gameplay element this glowing shrine here based on the player model more on that in the next video though and for some of the smaller changes specular reflections are now defined according to a texture not a fixed value for each mesh items sparkle now when dropped so they can be seen better grass now has a bunch of 3d extras on top of it rendering beautifully quickly due to an ultra fast mesh and sensor that i wrote in this frame alone they're about a thousand extra meshes with a hundred indices each and the performance impact is negligible [Music] and finally i started experimenting with adding water and well that's about all the changes last time now that the base level generator is in i'm looking forward to making some more gameplay content for the game and getting into real levels but that'll be next time so until then a link to the code for the wave function collapse algorithm is in the description thank you as always for watching and i will see you next time [Music]

Channel: jdh

Views: 266,094

Keywords: c++, programming, coding, opengl, graphics, java, gamedev, gaming, code, minecraft, indie, 3d, unity

Id: TO0Tx3w5abQ

Length: 15min 32sec (932 seconds)

Published: Fri Aug 05 2022