Procedural Generation with Wave Function Collapse and Model Synthesis | Unity Devlog

hi everyone in this video I'm going to discuss the technical details of the wave function collapse algorithm and the very closely related model synthesis I'll also discuss what features of these algorithms I'm looking for in my projects in my last video I gave an overview of wave function collapse and my interest in using it to generate procedural Terrain it might be helpful to watch that one first both wave function collapse and model synthesis are about constraint satisfaction they're used to generate some solution for a texture or a model given known constraints about how pieces fit together constraints come up quite a bit in games especially puzzle games Sudoku makes a game out of constraint satisfaction each row and column contain the numbers 1 through 9 with each number appearing only once additionally all the smaller grids also contain the numbers 1 to 9. you're given some initially collapsed cells the domains of the remaining cells contain all possible numbers your job is then to collapse these cells in a way that satisfies all constraints a good first step is to reduce each cell's domain using the information you currently have this took me a little while until I realized there's actually a button right here that does it for me from there you can start collapsing cells and use that information to further reduce domains I'm uh I'm not going to solve this whole thing on this channel we don't do constraint solving we make programs to do constraint solving there's another one Minesweeper is another game that involves constraints you're given a grid of cells that may contain mines initially you only know how many minds are present but not where they are clicking on a hopefully empty cell or reveal its contents and will also reveal all connected empty cells the cells with numbers show a constraint this number indicates how many minds are found in adjacent cells with this information you can start to determine which cells contain mines I'm pretty sure this top cell doesn't contain a mine and maybe this one doesn't either oh if you're like me when I was a kid I used to play this on Ultra easy mode on a big grid with just a few mines so one click and hey I'm so good at this some of you know what I'm talking about and of course Wordle also involves constraints after a guess you get information on correct and incorrect letters as well as correct and incorrect positions personally I like the constraint solving part of Wordle and its Big Brother cordial but not the word part itself words for me not so good so constraint programming can be used to deliberately make constraint based puzzle games or to solve problems that just happen to involve constraints any problem that can be conceptualized in terms of constraints might be a good fit for a constraint programming solution here's my current real life constraint problem I have too many turtles they're part of a behavior research project and while they're very cute they can also be a lot of work these sliders get along well in their babies as long as other requirements are met however as they get older they have more and more housing constraints they're really best housed individually or in very small groups since there are major constraints on cohabitation some are too aggressive to live with others all turtles in a group also need to be the same size even temperament can be an issue bold and shy individuals don't mix well the more outgoing turtles will have better access to food and basking sites while I'm not intending to program a constraint solver to help me plan new enclosures I do find myself thinking about this problem and others in terms of constraints of course in this case the best solution is more ponds [Music] let's talk about some more realistic applications of constraint solving I found several papers using constraint programming to plan work schedules that makes me think about Colony management games like rimworld this one is on how cognitive dissonance a psychological phenomena can be modeled by a constraint satisfaction neural network I really like the intersection of these topics so I'm gonna have to read more into this one also check out this dissonant sign I found near my hometown please keep your pets on leash in designated areas but also don't have them this paper discusses a constraint-based system to design novel benzonoid chemicals this paper talks about a procedural poetry generator here's one of the poems they generated music Wells acts and practices traditionalism hymns her devoted racing spent in her court and then vivaciously directly a Universe She disappears and Adam in the seasons of record and finally this was one of my favorite papers the author wanted to use constraint programming to find new musical scales there's actually some science and math behind music so I really appreciated this attempt to leverage the technical side of music to create something new of course this has to be heard to be appreciated this samples from a 19 note chromatic scale our standard octave is 12 notes foreign [Music] it's interesting different but not altogether Ben okay I suppose it's time to get back on topic there are links to papers and things in the description wave function collapse and model synthesis also fall under constraint programming unlike many puzzle games where the goal is often to find the one correct solution with wave function collapse and model synthesis the goal is to create any solution that satisfies the constraints both wave function collapse and model synthesis also draw inspiration from the texture synthesis family of algorithms [Music] the classic methods were based on deliberately crafted algorithms the animation here shows one technique called image quilting more recent methods take a neural network approach they can produce some amazing results but are a little out of scope for this video and for the moment my skill set wave function collapse and model synthesis build upon both constraint programming and the earlier texture synthesis methods Paul Merrell's model synthesis was the first the two algorithms it was Paul's PhD dissertation project and was published in 2007 with a few more papers released in the following years texture synthesis works really well except when it doesn't one of Paul's goals was to improve on some of these areas at the time Paul was developing model synthesis some of the early taxosynthesis algorithms had issues with rigid structures they were also not well suited for 3D generation Paul recognized that many natural and artificial objects consist of similar self-repeating components and perhaps by breaking down objects into these components instead of just thinking about pixels we can use these components to procedurally generate new objects in 2D or 3D here are a few more examples from Paul's dissertation can you tell how things are built from components check out Paul's website for more here's the basic workflow of model synthesis first unique components and knowledge of how they fit together in other words modules and constraints they can be derived from an input or created manually second select a cell to collapse third assign the cell a random module from its current domain the modules can be given weights to make some more likely to be selected fourth use the constraints of the newly assigned module to reduce the domains of adjacent cells and propagate these constraints as far as they will reach now just repeat steps 2 3 and 4 until all cells have been assigned if you watched my last video you might recognize this is the method used by wave function collapse that is not a mistake at this level they're the same algorithm [Music] wave function collapse was released in 2016. it's heavily influenced by model synthesis the name takes some inspiration from quantum mechanics I realize this is controversial so I'm staying out of it feel free to have more epic debates in the comments All of You are winners to me you might notice model synthesis focused more on 3D while wave function collapse focus more on 2D both methods can be applied to graphs of any dimensions that means both support all sorts of grids in 2D or 3D square and Cube grids are common but irregular grids like in townscaper are fine too if you have a 4D application I'd love to hear about it synthesis and wave function collapse differ isn't how they implement the steps I mentioned earlier let's start by discussing how the modules and constraints are created the original method described by Paul is called discrete model synthesis no not this discrete this discrete here a model is broken down into discrete pieces I follow this General method except that I create my discrete modules by hand in blender by the way for the rest of the video I'm using a simplified version of kanos Chen's tile set for demonstrations see the description for a link to their assets all also created another method called continuous model synthesis I'll be honest this is some fancy code magic and not a path I'm prepared to go down the basic idea is to place vertices edges and faces in continuous space instead of placing fixed modules in a discrete grid Paul does some impressive stuff with it but also notes limitations I don't think I've seen this implemented outside his dissertation check out some of his materials for more details for now we will consider this a separate algorithm wave function collapse uses a method very similar to discrete model synthesis called the simple tiled method however it's better known for the overlapping method which is one of the novel additions with discrete model synthesis and simple tiled wave function collapse it's possible to create matches for each module manually which is currently my preferred technique however the overlapping method requires a sample to analyze let's start with this simple sample note the arrangement of grasses and bushes from the sample we can determine which tiles fit together and how frequently each tile occurs if we only consider what tile is adjacent to other tiles we are essentially doing discrete model synthesis or simple tiled wave function collapse the results look similar to the input but don't share the specific tile Arrangements the bush patterns from the sample may not appear in the result now let's expand the sample analysis to consider each two by two square of tiles we're changing from the simple tiled to overlapping method the output now contains various two by two patterns observed in the input though in this case it doesn't seem enough for a good resemblance when using a three by three analysis the patterns are much more apparent and with a 4x4 the input is copied perhaps two directly let's increase the input complexity by adding a second sample [Music] here we have the discrete simple tiled method it has the right tiles but not the right patterns [Music] now a 2x2 overlap I think this is good for capturing the feel of the original but leaving variety and finally a three by three overlap overlapping wave function collapse can also work with pixels instead of tiles as you can see in Moxie's original demonstrations it's the overlapping method that ensures a likeness to the original image images with simple colors are easier to work with remember the modules should represent some repeating component of the original for complex images you might want to consider other texture synthesis methods 3D overlapping wave function collapse is possible but more complicated than its 2D counterpart most 3D implementations use the simple tile method these voxel buildings from oxim's GitHub are some of the only 3D overlapping examples I could verify after module and constrain creation the next step is to consider how cells are picked before being collapsed and assigned a module model synthesis iterates over cells in a linear scanline order that means it collapses the first cell then moves to the next cell as you can see here a 2d or 3D grid can be flattened into a one-dimensional array which is sometimes a useful optimization anyway and then the algorithm just iterates through those cells in order of course there are multiple ways to flatten an array so you can iterate in a different direction that may be important to consider if you use this approach unfortunately this method can introduce directional artifacts this drove me crazy for a little bit because I thought it might just be my implementation here Maxim's observations of the linear scanline artifacts do you see them depending on what you're doing this may not be an issue but if it is wave function collapse provides a nice alternative wave function collapse picks the cell with the lowest entropy entropy can be interpreted as a measure of uncertainty higher entropy means higher uncertainty about what outcomes will occur an entropy is zero means you know exactly what will happen consider these two cells cell a has two options Cell B has three you might think the cell with the lowest entropy is the one with the least options or the smallest domain that's a useful approach but we can go farther than that entropy not only considers how many modules are in each cell's domain but also How likely each of these modules are to be selected let's add weight to the modules these can also be converted to relative probabilities if all the modules are equally likely to be selected then the cell with the lowest entropy will be the one with the smallest domain however what if we're in a ruins biome where the old tile pathway is very common and the bushes and flowers are very rare let's give the pathway a weight of 9 and give both bushes and flowers a weight of one cell a has two equally likely modules there are only two options but it'll be hard to know which will be selected Cell B has three options but the pathway is much more likely to be selected this cell has more choices but actually has lower entropy so this is the cell that should be collapsed first while it takes a little longer to calculate entropy than it does to calculate domain size in my experience lowest entropy is still pretty fast the lowest entropy approach is also fun to watch for me this is a big part of the charm of wave function collapse while we're talking about weights both model synthesis and wave function collapse can use a weighted random selection method to pick a module from a cell [Music] I really like that adjusting the weights can give such a different feel to generation for this tile set a few adjustments can shift generation from forests and grassland to ancient ruins [Music] for the propagation step which is the slowest step both model synthesis and wave function collapse use a standard constraint satisfaction approach called Arc consistency to be brief this involves removing modules from a cell's domain if it does not match with one of the possible modules in an adjacent cells domain you may recall that we already discussed the constraint propagation step since there are no major differences in how model synthesis and wave function collapse handle propagation I'm going to skip ahead to talking about generation failures if you want to learn more I've included some links in the description I highly recommend Boris the Braves explanation of Arc consistency let's talk about failure yes it can happen as you can see here failure to generate something that satisfies all constraints is a possibility for both model synthesis and wave function collapse it's possible for the propagation step to remove all modules from a cell's domain this is what happened in the last generation failure becomes more likely when using large complex module sets as you can see in this graph from Paul's dissertation the top Castle set is much easier to generate than the bottom escheresque set especially as the generation size becomes large failure is actually a known challenge for constraint-based problem solving as this is an established issue they're also established Solutions like simply restarting generation completely or backtracking to an earlier state of generation and trying a different option than before backtracking is what you see here wave function collapse leads you to implement your own method to deal with failures but model synthesis also includes a novel solution called modifying in blocks or modifying in parts in this approach we start with some simple solution like filling the entire grid with all grass styles now we can start generation one block at a time instead of generating the entire map we divide generation into smaller more manageable blocks first let's initialize this block now we regenerate it if generation fails we can start over with that block without needing to restart the whole map when we clear the next block you might notice we cleared some of what we just generated the blocks do overlap they overlap so that cells On the Border get constraint information from neighboring blocks and the overlapping cells can also be regenerated we continue in this manner until each block has been regenerated the sides of the blocks and how much they overlap may affect generation there are a few considerations to make Paul talks about this in his dissertation I believe the modifying and blocks approach also reduces or eliminates the directional artifacts that can be produced by linear cell iteration hear or mock themes comparisons between the two iteration methods now here are some of Paul's comparisons the top image in each set is model synthesis and the bottom is wave function collapse the artifacts here are much harder to notice possibly because Paul used the modifying and blocks method with the right adjustments modifying in blocks becomes a good solution this clip is from Boris the Brave's excellent article on modifying in blocks as you can see he was successful at solving the very tricky esteresque set this might be the only way to consistently generate large 3D objects from complex module sets like this one check out boris's article for more information Marion kleinberg used a somewhat similar chunk-based approach to generate infinite worlds it's not quite the same but I think this demonstrates the potential of this overall idea see the description for a link to the write-up and don't forget to check out Marion's Twitter for updates [Music] while I'm doing plugs Rob Lang also shows a similar infinite generation approach in his Clopper devlog I really like this series and I found myself pleasantly distracted watching a few of his videos just trying to find a clip to show you check it out both model synthesis and wave function collapse are great algorithms and both Paul and Maxime deserve credit for their contributions many developers actually borrow aspects from both of these algorithms while adding a few features of Their Own as for my projects I have a hard time deciding between 2D and 3D generation so I've made sure my code can handle both I think I'll stick with the discrete simple tiled workflow it seems to work well enough for me and the overlapping method while really interesting adds another level of complexity that I'm not sure I need so far I like the lowest entropy cell selection technique I don't have to worry about directional artifacts and it seems fast enough I'm hoping to refine my propagation code a little more and I do need some error handling so I might try the modifying and blocks approach later it seems really promising but I'm gonna wait until I have a few other things worked out in the next video I'll give a walkthrough of my Approach and I'll post my code online some of this will be Unity specific though the concepts are translatable to other engines and languages I might add new features later but first I'm hoping to provide a stable implementation everyone can play with and hopefully some of you can make some fun new things too one more thing before I go I just want to give a huge thank you to everyone that watched my last video I was pleasantly surprised and honestly a little overwhelmed by how great the response was it was just incredible there were also a lot of really thoughtful comments make sure you check them out I do read all of them and I keep notes on the various things that come up like I know I need to show you how to address the patchy distributions of water in the next video and thanks for sticking around for the delay between videos too I know it was a little while I'll just say job Shenanigans some of it was accidentally self-inflicted and some of it was out of my hands but I think that'll all be rectified soon anyway I'm looking forward to hearing your thoughts and I'm really looking forward to getting to know some of the regulars make sure you do all the YouTube things again to feed the beast you know it gets hungry like subscribe hit the Bell say hello to your father and don't forget only you can prevent forest fires and I'll see you next time [Music]

Channel: DV Gen

Views: 85,915

Keywords: unity, unity 2d, unity 3d, unity dots, unity ecs, unity tutorial, gamedev, game dev, indie game, indie game development, game development, unity dev, devlog, unity devlog, procedural generation, procedural terrain, voxel, marching cubes, wave function collapse, voxel terrain

Id: zIRTOgfsjl0

Length: 25min 21sec (1521 seconds)

Published: Sun Apr 16 2023

Reddit Comments

[u/radarsat1]

Out of curiosity, are you aware of any references discussing these algorithms in a Bayesian sense? In particular I'm curious about their relationship with conditional random fields or markov fields.

[u/DV-Gen]

Hi everyone. This video discusses technical details of Wave Function Collapse and its closely related predecessor, Model Synthesis. My aim is for this to be an informative reference. I hope you enjoy it. I'm happy to chat about it here or on YouTube. I'll have to save the implementation for video three. The current video involved a lot of research, but the next one will be a little easier to put together. I will just need to clean up my code for you a little and then I can start putting it together.

For those of you that might have seen my last video... oh a while ago... Well, life has kept me busy. Work has been challenging, but I'm about to move across the country for a new job. I think its going to be a good transition for me.

[u/blakerabbit]

The model generation at the end of the video is really impressive!

[u/xotonic]

So it seems by utilising “chunks” it is possible to generate infinite world as camera moves. I wonder if it is possible to use octree for 3d world or quadtree for 2d to first generate bigger high level zones like biomes or town districts. Then by going down the tree to focus on details like houses or landscape layout.

[u/MonkeyMcBandwagon]

Great video, thank you!

I've got a project that involves procedural terrain generation and seeing so many WFC demos posted here over the last couple years it has perked my interest, but no example I saw of WFC fit my requirements so I have not tried to implement it.

It looks like Model Synthesis is a lot closer to what I need, which is a sort of "ideological symmetry without geometric symmetry" For example, generating a map for an RTS, the landforms and coastlines should be diverse and unique, but each "Town Hall" location should have exactly 2 nearby gold mines, 4 stone quarries, a similar amount of forest and plains, each land mass needs two or three potential port sites, and "islands" satisfying those conditions should be connected by a land bridge with two choke points, and so on. Essentially an arbitrary list of top-down broad, structural constraints.

It looks like Paul's original paper addresses this sort of thing, and I need to read it. :)