Just for the record, a physicist would just call this monte carlo sampling rather than wavefunction collapse. We use similar algorithms all the time for solving lattice models in statistical mechanics for example (see the Ising and six vertex models for examples). There are ways to make this kind of process much faster if you have some kind of scaling behaviour as well. That class of algorithms is referred to as renormalization group methods by physicists, where you start with lower resolution sampling and then gradually increase the resolution. An example of that is that if you want to generate terrain with 100 different height levels for example and heights of adjacent tiles would be within 1 height level of each other, then you can simulate 10x10 blocks first and sample them randomly with the constraint that their average height has to be within 10 height levels of each other. This is a hundred times cheaper to do. Once that is done you fill in the inner squares using that information, but since the average heights per block are already constrained, in each block each square has only 10 possible values to pick from instead of 100, and long range constraints have already been taken care of by the earlier lower res pass. Of course, not every system can be handled in that way, but many can. And you can also decide to have different rules at each resolution scale if you want to model richer behaviour. For example, for procedural terrain generation you can use the lower res for picking biomes, and then do increasing resolution to get transitions between biomes, and then increase resolution to do the actual terrain.
Of course, just to qualify the obvious physics perspective that this comment is contradicting: It's wave function collapse because you're considering a probability space (and I wish weights were mentioned) that reduces in dimensionality as individual values are enforced stochastically (the Monte Carlo part). It is somewhat similar to the corresponding concept in quantum mechanics if you were to measure a bulk sample randomly. Each measurement makes the possibilities of future measurements collapse into certainties. It's a cute analog to me.
I can really see major utility in combining this with my existing procedurally generated island system to help me navigate designing and placing village prefabs in a natural way. Thanks a lot for sharing
@@Nevir202 I get that, it seems like a very early iteration and I think more robust path generation rules are definitely possible. Thinking about Minecraft when I say that even that billion dollar game can't seem to manage decent path generation. Villages have the craziest paths.
@@CSpottsGaming Ya, you would just have to layer other rules atop the system, like first randomly generating certain points of interest, then running something like standard pathfinding to decide where to lay in the paths, then generate the terrain afterwards. Or generate the terrain, then then points, and then a more complex pathfinding script that would take terrain into account by weighting things properly. EG: humans will almost always walk a little extra, to avoid an elevation change. This generates random terrain well, the issue is, paths and things humans and animals make, aren't random.
Immediately I notice that the algorithm can be applied to a partially filled grid, which makes me think that one really cool application of this would be to combine it with manual placement. The idea is that a level designer could place tiles of interest to shape the "general feel" of an area, and then run the algorithm on that initial state to fill in the rest. This could also be done in chunks - suppose the designer is able to select a region of cells in the grid to apply WFC to, some of which can be partially filled to start with. This feels promising enough that I might try to make a tool for it in my engine of choice sometime in the next month or so. I could see this being SO useful for speeding up the creation of areas which feel at the same time both hand-crafted and "naturally generated".
I've had a lot of these thoughts too. I think procedural generation as a tool for a level designer is a great way to go. It is one of the things I'm considering implementing much later.
I think sometimes with some intricate and huge system of rules you can get topological defects if you propagate the generation from different spots (manually placed ones)
@@egoreremeev9969 Yeah, I can see that being a possible issue. One way to fix this would be that if there are ever uncollapsed cells which cannot take on any cell in the rules, the algorithm should mark that cell as "uncollapseable" and have a designer come in and fix the cell / the area around it manually after the algorithm finishes. You'd hope that these would be rare, and an alternative to manually fixing it would be to run the algorithm again and hope one doesn't show up. Another way to fix this, on the manual input side of things, would be to avoid placing topologically restrictive cells (i.e. those with few allowable neighbours) too close to one another. I'd guess that following this principle would, in many rulesets, ensure that the algorithm doesn't run into problems very often. I think in this context where there is partially manual input and partially procedural generation, the right way to think about WFC is as a tool. It is useful for designing content, but there is also an element of skill involved - as you use it more, I would expect that you'd get a feel for how to get the most potential out of it. I'm planning to make a Godot plugin for this in the next month that would integrate with Tilesets/Tilemaps. It would be cool to integrate this as yet another tool for level design.
@@egoreremeev9969 Not too much of an issue if you have error handling. I was thinking of that while watching. Basically make a tile which gets plugged in anywhere that there is a failure to assign a tile given the normal ruleset. A crater, a structure, anything that would be okay next to any tile, and set its base color to a gradient between the colors of its four sides.
4:40 thats actually a part of procedural generation that I love; I really like spending ages finding a way to have my artistic vision generated programatically, rather than setting it in stone myself. I think I enjoy the difficulties of trying to figure out how to define my imagination
Programming (logic) is on the opposite spectrum of art (creativity), they can meet but it's complicated (and takes a lot of work). Example, a computer has no perception of what makes a flower pretty, all it knows is how to categorize them through an input you give it. In this case him spending years trying to force the program to understand what looks nice was his mistake which he admits. What he really should have done (what he showcases later) is forced the logic to allow him to implement His own art, his own creative vision, it's is much better approach imo. Computers are dumb.
@@publicalias8172 I have to say I disagree with you. Computers are dumb yes, but they don't write the code, do they? Humans do. Does it matter whether someone uses code or a pencil to create art? Your comment kinda reminds me of traditional artists saying digital art isn't "real art". Just because it's different doesn't mean it's not art. I mean, what would you call technical artists? Their job (well, a part of their job) is literally to create art... from code, aka creating shaders. Saying programming and art are opposites of a spectrum is definitely not true. Sure programming doesn't necessarily need to be art, just as drawing something on a paper doesn't necessarily need to be art. But I can tell you from personal experience, graphics programmers in the industry put A LOT of work into making things look good, they gather references, both from the real world as well as from other games, just like a regular artist would do. I think they would find it pretty offensive if you reduced their job to just "writing some logic" :P
@@publicalias8172 I disagree, It's the math which can be the art form, combining different noise functions, tuning your algorithems just right to create the thing you are looking for, but mainly combining noise functions is what really creates the terrain.
@@publicalias8172 You're confusing medium with art. Programming is a medium, art is a form of expression that uses it. They are interconnected just like engineering, science, and technology have always been connected to art. You can't make new breakthroughs without creativity.
I'm a new programmer and I've always wondered about how world generation was implemented in games. This video is AMAZING and answered every question of mine. The production quality, too- just wonderful. Thank you.
Funnily enough, the WFC algorithm for procedural generation actually _is_ based on the wave function collapse in quantum mechanics. Like the whole thing is basically setting each cell to a superposition of all states, then collapsing nearby cells by adjusting their probability distributions by adjusting the possible eigenstates. So it goes from a mixed system to a classical one.
@@lawrencedoliveiro9104 Any tile which could be one of multiple possibilities is functionally in a superposition of all of those states until it's "measured."
@@jakegearhart In quantum theory, a “superposition of states” means a weighted sum of the wave functions for all those different states. Since wave functions are complex-valued, this can lead to well-known wave-interference effects, as in the classic double-slit experiment. There are no such phenomena going on here. There is no equivalent to the wave function; it’s just simple conditional probabilities, nothing more. No Bell’s Theorem, no causality violation or hidden variables.
This algorithm feels like a huge advancement in procedurally generated maps! Thank you for sharing it Of course it won’t be right for every situation, but it has so many possibilities. For a first person game, I wonder if it would make sense to combine Wave Function Collapse with the 3D noise underlying marching cubes? Something like at the start, you’d restrict which tiles are placable at each location based on the noise value there. I’ll have to play around with this!
That is a great thought, for a game of any style! It is actually on my to-do list. I have some code working now that can restrict the floors to solid tiles, the ceiling to empty air, and the sides to empty air as well. Ultimately, my goal is to have the wave function collapse algorithm read from a height map, but give it some room to do its own thing too.
@@ThylineTheGay : You'd probably want an iterative approach to that- generate an initial landscape, maybe run it through a convolution step to make sure the entire thing makes sense (e.g. joining near but not quite adjacent tiles to form rivers), then run it through another convolution to add biomes to the landscape.
@@ThylineTheGay Sure. If you want to think in terms of biome adjacency, this could work for giving you patches of biomes with transitions. I'm thinking something like transitioning from an extreme desert, to a moderate desert, to a scrub land, to a grass land, to a temperate forest. You could use wave function collapse to put things together, then use some other method to generate the tiles inside the biomes, maybe even with another layer of wave function collapse. @Jared Maddox makes good points too. I would probably want to factor in things like elevation and temperature. But adjacency alone might work too, depending on what you want.
It's actually 6 years old by now, it's cool that people have started using it more and more recently. Ultimately it's a simple version of constraint programming, it'd be cool to see if super-performant algorithms from that will start seeing usage in game development.
I always told myself I'd never get into game dev, but after just graduating and seeing all the effort and complexity that goes into something like this, I'm rethinking that.
Thanks, I really appreciate that. I'm definitely in a stage where I'm doing a lot of imitating trying to develop my skills. I'm going to keep working on it. You can check out some of my pixel artist inspirations for that tile set too: twitter.com/UBadler twitter.com/vivavolt twitter.com/MartiansGame
@@dvgen hopefully you don't mind me asking this, but i have an interest in pixel art as well (but much more primitive in my skills, majority of my time goes to uni) and i wanna improve. I understand some parts of colour theory and shading, but in terms of actual drawing, my skill just isn't there. I don't know how to practice it, and I want to learn how to draw while minimising mistakes that would make my pixel art in the future worse off (for example, i study engineering and just a few fundamentals regarding math & physics can make your life much harder down the road if you don't have them). How have you been practicing, and if possible how would you advise me in doing the same? Thank you for reading this.
@@ynnad7778 It is still something I am actively working on, and I related to wanting to build strong foundations. I really just try to practice a little bit when I can, when I find something inspiring, but not be too attached to any of it. I've also found Adam C Younis's UA-cam channel to be really helpful. I also really like the Blender NPR channel for all sorts of non-photorealistic resources and inspiration, which sometimes includes pixel art like things.
i genuinely love seeing videos like this -- really nicely made passion projects. you're not afraid of showing off your pixel art even if you think it needs some more practice, and the explanations are really well done and visual
Thanks! I think, for many skills, including art and programming, there is continual growth and development. So yes, you can't feel bad about your current skills. It may not be where you want to be, but practice is how you grow.
Actually, as far as I can tell, the wave function collapse generation method is the same as quantum mechanical wave function collapse, except we randomly generate measurements (determining the boxes type) to reduce the domain (literally the same terminology, use tensor product space if feeling fancy) until we are left with one possible wavefunction (generated mesh). If we want to get fancy, we can describe it as a) wavefunction in the tensor product space of all the tiles' possibilities (so all the number 5's in each tile being almost independent of each other. If one wants more jargon, then 5 in each tile would be the Schmidt rank of the partial trace which eliminates everything except that tile) b) an operator which takes any possibility which is incompatible with our constraints to 0, while letting all other possibilities alone. This is the information propagation stage in the code. So eigenvalues are 0 and 1, and we demand that our wavefunction be a 1-eignevalue of the operator, so we apply it repeatedly in discrete steps c) the random hit generator which pins down the tile is just a simple projective measurement I see no reason why one couldn't possibly generate more complex structures from this, except that any property which is non-local (not entirely dependent on direct neighbours) like connectivity in a maze, the propagation step gets very complicated very quickly.
I did undergraduate physics only so I was struggling to make the connection, so my question would be in this analogy is each box like an individual particle with an individual state but neighbours are entangled + there's some global constaint?
@@michaelmoran9020 precisely. The total wavefunction would be something like |1⟩|2⟩+|3⟩|1⟩, with various products being determined by the adjacency rules, but to save space we store only the reduced states with each box's information in each box, so |1⟩+|3⟩ in box 1 and |2⟩ + |1⟩ in box 2. (More precisely it's |1⟩⟨1| + |3⟩⟨3| for box 1 if you have done density matrices)
@@michaelmoran9020 You just take tensor products of the eigenstates of the components. If it's non-entangled i.e. separable, then it all factors out. Local interactions and such come from the operators, you can technically take systems of particles on two different sides of the earth, it's just that not many physical operators will act on both simultaneously. e.g. box 1 is in |1⟩, box 2 is in |4⟩, then composiste state is |1⟩ ⨂ |4⟩ (normally i am omitting the tensor product symbol and requiring that the order be maintained here, so |1⟩|4⟩ ≠ |4⟩|1⟩) if box 1 is in |1⟩+|2⟩, box 2 is in |1⟩, then the global state is (|1⟩ + |2⟩) ⨂ |1⟩ = |1⟩|1⟩ + |2⟩|1⟩ if the states are entangled, then we can't factorize it into a box 1 part and box 2 part, like so |1⟩|2⟩ + |2⟩|1⟩
I wrote a caves/maze map generator thing with basically this idea, without ever having heard of it before, so watcing this video kind of surprised me. I think thats pretty cool. My own name for my version was erosion mapping, because it carves out space from a world full of solid blocks, then removes any walls that're only touching other walls, so the new eroded space is perfectly surrounded, ergo maze/cave generation as opposed to world generation.
Awesome video! This is an excellent explanation of wave function collapse. Thoroughly enjoyed watching it and am looking forward to your next video. Keep it up! :)
I've been reading about WFC a lot lately. One guy got amazing results by also using NEGATIVE connectivity examples in WFC. This way you don't have to specify all of the possible connectivity rules but can just prevent the rare cases you don't want for some reason. This gives much more artistic control.
I used something similar on a BotW-like that I made with my kid a little while back. One of the things I really liked about this method was the ability to have "landmark" tiles that would generate villages, ruins, and dungeon entrances in reasonably logical locations.
it might be a good idea for a map to generate a few "necessary" tiles in random places before the wave collapse starts to start out with, so that certain needed locations always exist for what ever gameplay takes place in the generated world. then, if any tiles wind up coming into conflict, special case tiles could be inserted as a way to ensure there is a resolution to any strangeness that could cause.
I've had similar thoughts. You could pre-place some authored tiles, like a path, and have wave function collapse generate to fill in additional details. Boris the Brave's Debroilie / Tessera asset can do that, I think. It is definitely on my list of things to implement. I had not considered a few random tiles just to encourage and overall map feel though. www.boristhebrave.com/2018/10/06/debroglie-v0-1/
@@dvgen you wouldn't necessarily need to have the pre-placed tiles be deliberately placed by a human though is part of what I was saying, you could have a barebones procedurally generated map with almost no detail place the needed components for an adventure, then have the wave collapse fill in the details and make minor changes. basically, have a primary and secondary pass to generate a world more complex than simple terrain generation would allow.
Yeah! I'm imagining a scenario where the player needs to be able to travel across the map. You could generate a random path from one side to the other. Then you could add a constraint that all tiles along the path must be passable. Then when you generate the tiles, you'd always be guaranteed at least one path for the player.
Just came across this vid and it the exact solution to map generation problems I've been having for a while thanks an absolute ton for introducing me to this method
1:14 Wave Function Collapse is actually a really great name for algorithm. I suspect you touch on this in the next video, but this process of the "collapse" of a possibility-space into something concrete is EXACTLY what wave function collapse is in quantum mechanics (albeit much in a much more complex way).
Yep. Quantum mechanics is not my area, but I'll talk a little about the name and influences of wave function collapse in the next video. I'm really going to have to learn a bit more about quantum mechanics I think.
Neato. Just stumbled on "wave function collapse" last night researching a programming language/compiler (Virgil) then your vid appears on my youTube homepage. Intriguing and possibly destiny. Good vid btw. Had thought about random, dynamic texture and object creation with a defined pattern of rules that could be updated on a case basis, but never really got down into the nuts & bolts. Always fascinates me when stumbling into others with similar views. Appears you've got quite a good grasp on the topic - very nice.
This is revitalizing my obsession with auto-generation. But it really should be called *domain collapse* but I can see how it is actually similar to the physics concept
Everything old is new again. This reminds me a lot of Conway's Game of Life and cellular automata in general. Simulations could use this process to great effect, I think. If you had data encoded in each cell regarding say, resources available (food, materials, etc.), you could use that as a basis for things like simulating animal migration, human expansion, stuff like that. Really interesting to learn about practical applications for otherwise dry math concepts.
This is the first video of this channel I saw. Looooove this kind of in depth content. No matter how many views it gets it deserves more, please know that this is super awesome!
Well presented. I would not consider that work you put into a solution you are not going to use as wasted. Some lessons just cost more time than others, what matters is that you developed from that point to where you are now. Keep it up!
What the!!! Your channel has TWO videos! One of them I would honestly not give the time of day, but this one is Sebastian Lague level of quality! Thanks for sharing, you earned a sub!
The pixel shader has a great style to it! Would certainly enjoy seeing more about it and other's like it, particularly interested in how it looks in motion.
Thanks! Data science is not my area of training, but it is one I encounter sometimes doing traditional null-hypothesis testing for my research. I really like that some of these areas connect multiple disciplines. It is a great way to learn about something new, and also learn to see things you already know in a new way. After working on this for a while, I can't help but thing of everything in terms of graphs and constraints.
Consider adding time into the equation (maybe some value between -1 and 1, then you can feed a sine wave in) to the WFC. Eg, water can appear next to sand at -1, but ice at 1. For 2D you could fade between the 2 images for values between -1 and 1, for 3D you’d need a different solution (could use blend shapes if you maintain the same vertex count / order and blend between 2 mesh’s). The sine wave could represent a day / night cycle, a seasonal cycle, or even some sort of “force” (you could simulate earth quakes or waves).
I have no idea how I stumbled across this video but I'm really glad I did. This is a really interesting subject, and something I've wracked my mind against for a long time for similar reasons as you.
Great googley moogley, this looks like it took you absolutely forever to make. Thank you for the wonderful video. It was extremely interesting with phenomenal visualizations, chill background music and a nice voice. Felt like I was watch the next Sebastian Lague. I eagerly await your next Devlog, but no pressure :)
Thanks. I've been a big fan of Sebastian Lague since forever, and I really like his recent "Coding Adventure" series, so that is a very big compliment to me. And yes, it did take way too long. But I think I'm getting the hang of the workflow.
You can use some like Binary Space Partition or any of a slew of other techniques in conjunction with this to add weights and biases to what can and can't generate, sometimes altering the generation rules entirely within a given region defined by the algorithm. It's an extra step that would give you tremendous control over how things look and feel at any scale. It's also probably not too much trouble to throw in any kind of geologically-inclined algorithm at this too, since it's all just about the rules for what the tile can 'collapse' into, after all. These things kinda run first, then you apply your wave collapse algorithm afterward to finalize the generation, and it has to adhere to the weights and biases introduced by any prior algorithms that adjusted what tiles can become. Thus, a very fun to tweak and get just right procedural tool is born. I'm probably going to experiment with this in a Godot project at some point, myself.
I imagine a hybrid approach of perlin noise layering + wave function collapse could create some pretty nice generation. Overall map structure is important.
Probably would be good to use Perlin noise to mask which modules are allowed to be generated by the WFC in certain areas, as if Perlin noise introduces biomes/climates. Could also try using Perlin noise (multiple instances) to add weights to the probability of selecting certain modules, but that’s like a more generalized but less perfect approach to the first idea. I think this second idea would result in the most dynamic generation for the simplest implementation.
An interesting thought that occurred to me while watching this video; when you introduce the grid of cells at 7:11, your rules don't need to be a direct relationship between meshes but could also be their relationships within the grid overall, like you could use Sudoku rules to guarantee that predefined areas contained certain features, or even categorize your meshes further into biomes for more distinct segments. One question, is it possible to generate an "illegal" map where your adjacency rules result in no possible meshes in a space? If that occurs, how do you handle it?
Yes, you can do lots of different rules and constraints. I've only implemented the basics so far. And yes, the generation can fail. I'll show some solutions different algorithms use in the next video, but backtracking or completely restarting are common options. The tile set you use matters a lot too. I've never had it fail in 2D, and 3D failures are rare, unless I don't give the algorithm enough tile types to be flexible.
I love exploring different procedural methods of creating maps and structures. Fractals, and setting rules, limits, and boundaries are neat tricks that with todays technology can work with any kit bashing method approach. Simple and fun, looks good. To truly get realistic or plausible builds these methods must be carefully calibrated and tweaked. Using topographical maps and how water, sand, and even harder stuff flows over time across a landscape can give that plausible yet interesting and even unsuspected look. I like that too, it is a creative process. Thank you for sharing this.
I haven't tried it yet, but I wonder about generating a height and water map first, and then having something like WFC come back and add variability and tiles from there. I did some hydraulic erosion simulations a while back, and modeling a natural process like that really amps up the realism.
How do you guarantee that you don't back yourself into a corner where no tile is allowed? You mentioned favoring picking the next tile where the domain is smaller, and then in later clips you have a very directional method (or is that just the animation?). Are there any rules that affect more than just direct neighbors? This reminds me of weighted wang tiles, which matches against each edge type instead of each whole square.
Good thoughts. I'll go into that more in some of the next videos. But yes, an unsolvable map is a possibility. The main options are 1) regenerate the whole thing, 2) backtrack to an earlier point in the solution and try again, and 3) build the map in smaller pieces, with each overlapping a bit. Solution #3, "modifying in blocks" is what I will try later. For the moment, though, the tile sets I have are pretty robust. As the tiles become more complicated, it is easier to have issues. So thinking about what pieces you have is also important. There are also different ways to do iteration. In most of the clips I pick based on small domain, but in some of the last ones, I just go in order. Each method has strengths, and it's something I'm still evaluating. You can add a lot more rules and constraints. I'm only working in direct neighbor category right now, but check out Boris the Brave's Debrogile / Tessera library for some of the more involved things you can do. boristhebrave.github.io/DeBroglie/
This wont always fit your needs, but you can potentially make one tile that is *always* available for use and that never gets ruled out by neighboring tiles. Something of a fallback tile.
you can take advantage of such cases by adding tiles which should only spawn very rarely and in lines by spawning them in these zones - as unsolvable maps are naturally relatively rare, at least depending on your tilesets. Such tiles would need to be implacable (can be placed next to anything, including itself) and will usually 'clump' in line along the 'dead zones', acting as a sudo-'edge' of that tile - if not literally the edge of that tile if your situation allows it, allowing obtuse tile generation.
I wrote a WFC inspired map generator where the probability for a given tile was pretty complex. Like it took into account how many had been placed among other things. One thing I did was backtrack a tile placement that dropped any cells to zero possible tiles. Granted, sometimes there was only one choice and in that case, I threw the map away.
This came at the perfect time for me - I'm about to start working on a terrain generation system for a hobby project and I've been terrified of approaching it. This has really shed some light on a great way to get more control over the generation algorithm, so thank you for sharing! Also the animations were a great help in understanding how it all works, great vid!
I’d like to see more detail with regards to the tile selection rules, and also the voxel generation if that’s still underlying. It seems that a naive approach would tend to give too random of a distribution at the small scales, leading to no larger overall shape and so no fractal coastlines. Perhaps having a bunch of deeper and deepest ocean tiles, higher mountain tiles, etc. would help, assuming tile selection is what decides the terrain height. Perhaps running multiple iterations of wave-function collapse at progressively narrowing scales would provide better results?
I think you are totally right. Without some help, the algorithm can start to produce things that are a little too random. Having some transition tiles, like water depth, will help. I'm also really interested in the idea of multiple levels of iteration. Hierarchical wave function collapse perhaps? More details to come in the next videos.
@@dvgen This hierarchical thing reminds me of an idea I want to try out some time where you start with generating a graph (nodes & edges) and then turn that into a level in multiple steps, with nodes being more or less large areas and edges the paths between those areas (which might consist of tiles). So kind of along the lines of Monster Hunter or Dark Souls-style world maps with areas linked in various ways. And the way you layout the graph and generate the edges between nodes would influence the overall style.
Looks like most of the comments here are other devs and hackers. I just want to say as someone who likes playing games but not making them that i still found this really interesting. I like your style, direct to the point, no fluff, visually rich. I’m definitely subscribing and hope to see more from you
if you're still not quite satisfied you can try adding a shell or wrapper for it especially for verticality, either a nested waveform, weighted veroni, poison disc sampling, or my personal favorite reaction diffusion. standard waveform never really had the kind of topology I was looking for but is seriously impressive for what it is.
This is a great WFC collapse explanation! I'd be interesting to hear how you're going to deal with situations where there is no valid tile - or whether your marching cubes rules mean that there will always be a valid tile. Have sub'd and looking forward to the next!
Thanks! If you are smart about what tiles and connectivity rules, those issues are rare. Eventually, I will implement a "modifying in blocks" type approach that will regenerate sections as needed. Interestingly, the possibility of encountering an invalid situation also depends on the iteration method. I'm trying both scanline and lowest entropy approaches, and they aren't always equivalent, even with equal weight tilesets. Scanline seems to be faster and more robust, but might have some directional artifacts. That is the kind of thing I want to talk about in later videos.
My thought when seeing your first larger wave function collapse example at 8:36 is that the water areas look too small. Iʼm sure there are ways to solve this with the rules you provided, but my first thought was to extend it so each neighbor, in addition to ruling some things out, changed the probabilities of the adjacent tiles, so that choosing a new tile adjacent to water might have a 90% chance of being water and only a 10% chance of being sand. If there are two adjacent water tiles, that would combine to 99% chance of water (9:1 water to sand ratio, squared), up to 99.99% for four adjacent water tiles (which is probably too extreme, but theyʼre illustrative and easy numbers to work with). Is that a thing thatʼs been done before here?
Either that, or just define different tiles for different depths. So you have shore, shallow water, deep water. Deep water has to be surrounded by shallow water. So if you ever have a Deep Water tile somewhere, the surroundings have to be at least 1 shallow water and one shore. That way, the water areas are bigger in general.
I got a lot of comments on this type of thing, so you are picking up on something many people think is important. This example lacks transition tiles since I wanted something really simple for the first demonstration. Adding the transition tiles softens the change, but also adds a minimum size to the water features. From there, adjusting the probability of tiles, and certain types of transitions can indeed let you dial in the type of generation you want.
@@KYL3R64 You are right, this is also something that can be done. I thought about including it, but I didn't want to do too much at once with the first demo.
4:12 one reason using a switch is actualy a bad idea, to see what's happening you have to scroll all the way up worse you manually write every case. this is still hard coding even if you're not directly putting the number values there a better way to do this is to make each case a member of a (voxel rule class) , that holds the data about the system then if you serialize that you can save it to a file without having to edit the code directly this way could be much faster because every change you make shows up immediately instead of every {close game, recompile, open game}
“It would be nice to talk to people with similar interests” I am impressed. Pardon my lengthy ramble. I probably won’t respond further, I often go quite in depth with thoughts I find this content very knowledgeable while also embracing your intrinsic emotional experience. Memes are funny too. I learned something new not just about voxels, marching squares, wave function collapse, tradeoffs during development, but also about the process of being a human working on a game. Interested in kinesis too One thing I found interesting was how the water would often form in illogical ways. It appears you were already experimenting in that direction with southwards flowing water. Talking about the connectivity rules, I suppose you could make dummy layers for things like oceans/lakes/rivers with the same tiles extended in different axis of scales. So, very deep water being 7o, deep water being 6o, water being 5o, and coast being 4o, with lake being maybe 5L, 4L that don’t connect with the o’s and rivers being 4R. Or changing the selection method, or the propagation method. Certainly easy to get distracted by side projects when there are so many interesting ideas and experiments to explore! I do tend to find in my experience working towards a goal with realistic steps tends to curb the side projects. But then I have to set aside the reward of interesting and learning, so the reward of that goal needs to be suitably enticing to make that trade. Normally I don’t really have a lot of interest watching devlogs of people generating hype for their games by regurgitating the same experiences that others have had and expressed. As someone obsessed with learning, it can often feel pretty disappointing and embittering to invest in watching videos and not learning anything from them. But I grit through that expectation for the sake of possibly learning something. This was more than I bargained for haha. The idea was so well explained that I’m now convinced it’s a great method to implement creatively, much preferred to the marching square tedious manual case by case coding.
You know, I have a career already, I'm not under any illusion of making it so big on UA-cam or making tons of money on a game that I can quit my day job (plus I like parts of my day job), and I've really got nothing to shill. I really just like learning (I'm obsessed too) and talking about kind of stuff. So I really did mean it would be nice to talk to people. I got started on Twitter and met some cool people there. I wasn't, however, expecting this to be so well received. Look at all those comments! So many cool ideas (yours included)! I do think you are on to something with the water. Wave function collapse can give you a valid solution. But it isn't necessarily an aesthetically pleasing one. You have to do a lot of tweaking to get the kind of result you want. I have one picture I might show later, where I was testing out the waterfalls and rivers, and the algorithm gave me a map that was like 90% waterfalls and rivers. So I'm like "okay, I guess that is technically correct." It is a kind of thing where the algorithm is alway right, but not always pretty.
maybe generate a map that biases all the cells, so it biases one region towards water and another towards land. or maybe run the whole thing at multiple resolutions, then subdividing the grid and using the previous to limit the options or bias the picking, maybe with some smoothing like a median or gaussian blur
This is the best explanation of WFC that I've seen, ever. It explained it simply and made it approachable. I'm really looking forward to your explanation of how you implemented your rule set!
The final maps still tend to look too random, like the one at 8:36. Im curious what would the maps look like if there was a weight attached to which tiles should be picked based on neighboring tiles.
It was the first thing I thought to. Having some probability for transitions... It start to sound a little bit as some Markov chains but in more dimensions.
I was thinking there could even be a larger "Region" ruleset - perhaps a region is a 3x3 or 5x5 area of tiles, and in each Region there should be one of a pool of geographical Landmarks (Could be a mountain, forest, canyon, etc.) to draw attention to. Tiles closer to this feature within the Region would be transitionary biomes/tiles/heightmaps bridging the difference between the Feature tile and the outer border Tiles
Appreciate this approachable explanation. The name always reminded me of the Wave Motion Cannon (from Oni), which I understand was itself a reference. On the first watching, it wasn't clear that the number in the cell represented the count of possible solutions to the rules. But I eventually got there! Nice going.
Glad to hear even the boops are appreciated! I'm not sure the bees feel the same way. I'll be back to focusing on behavior a little more once some of the terrain systems are a little more developed.
You're really good at explaining this. Would you perhaps be interested in doing a more detailed walkthrough of working with WFC? It's gonna be a few months till I can get back to programming because of real life stuff, but you've definitely piqued my interest A LOT.
I implemented blocks then marching cubes, but I never sucedded to implement dual contouring, I ended up with a big cloud of triangles that I could never fix. This wave function is not about rendering voxels but generating them, it should be compared to simplex noises, geological simulations, etc. I like the freedom it gives, but the huge amount of rules required and the undeterministic results are serious limitation.
This is truly amazing, your video inspired me to do something like this! I've spent big amount of time working with procedural generation, but never came across this thing. Thanks!
Incredible video and absolutely beautifully animated. Thank you for sharing your findings and making it much easier for the rest of the community to find alternatives to voxel meshes!
Wow I don't know how UA-cam didn't recommend this to me sooner, but this is a masterpiece explanation and demonstration. Excellent work! Edit: Holy shit, buildings generated by your terrain algo is fucking brilliant, I can't believe I never thought of that.
I didn't understand almost the entirety of the video, since it's way above my head. However, it seems like whatever you're doing is really amazing and taking your artistic endeavors to the next level. Keep up the good work and keep moving forward!
Very nice video! I really enjoyed the information, dude, I was thinking oh another video for 10 minutes of blah blah, but I was spell bound! Thanks for sharing, you've got a subscriber here! I'm an aspiring game dev, and I've been considering wave function collapse as a generator for a bunch of things, like terrain, buildings, etc. Thanks again!
Fascinating! The explanations were all really well done, the effort you put into those is super appreciated. The simple rules are so elegant, makes me want to do something with procedural generation.
Wow1 What an intuitive and simple yet genius way to generate things. It makes so much sense right from the beginning, and it looks much cooler than the standard voxel grid. Definitely going to use this for fun. Thanks for sharing!
I've really enjoyed it. It is definitely worth playing with, especially in 2D. I agree, it looks a little more interesting than a voxel grid. Imagine what it could be like in the hands of a talented artist.
I found this video while searching around to see what Voxel CAD tools were floating around. I enjoyed seeing the various different approaches you used to do procedural generation. I hope you are able to make more development diary videos of your projects.
I'm so happy I stumbled upon this. I'm in the process of planning a 2D game out that is essentially an IDLE Colony Sim and my first hurdle is figuring out terrain generation. Thanks for this, as it opened up an entirely new world (heyoooo) of possibilities.
Just found out about Wave Function Collapse today, and this is the second video I've seen on it. Love the irony that I want to implement this on a voxel game.
Damn it is a lightbulb moment, you explained the order of tiles and showed the result and suddenly it was all I could think about :D Nice explanation. Maybe I'm going to use it someday.
Holy shit. You just made me interested in actually using procedural generation in a game. I been thinking of never use it, cuz I don’t typically like how it’s been done, but damn! Also you’ve earned a a sub.
I haven't put much thought into how to approach procedural generation, but after seeing how this works it seems like such a good answer, especially when combined with other forms of logic to generate those initial points.
Really appreciate this video, and you taking the time to just teach us, just like for free. No other purpose. Just taught us something really valuable.
subscribed. You have a pleasant voice and are really good at explaining stuff. I am and developer with one too many hobbies. This was something that interested me a lot but I could just not bring up the time to start another time eating hoppy. So this style of you showing your progress and how things worked was almost like an ASMR video for nerds. I like that. gonna look through your other videos and see what other stuff you have.
Wow the pixel shader looks amazing. This method is exactly what I think I need to finish my procedural dungeons the way I want them! I used another method that just wasn't working for me and was bland. This really seems like it will fill in the gaps I have, and i can't wait to see more!!
Minesweeper is a game where humans practice collapsing waveforms.
Honestly a really helpful way to explain this.
litearlly the baseline of how reality function buddy.
Finally. I knew those years of training would come handy
youre right but I dont want to admit it
I just did….
０．０
Just for the record, a physicist would just call this monte carlo sampling rather than wavefunction collapse. We use similar algorithms all the time for solving lattice models in statistical mechanics for example (see the Ising and six vertex models for examples).
There are ways to make this kind of process much faster if you have some kind of scaling behaviour as well. That class of algorithms is referred to as renormalization group methods by physicists, where you start with lower resolution sampling and then gradually increase the resolution.
An example of that is that if you want to generate terrain with 100 different height levels for example and heights of adjacent tiles would be within 1 height level of each other, then you can simulate 10x10 blocks first and sample them randomly with the constraint that their average height has to be within 10 height levels of each other.
This is a hundred times cheaper to do. Once that is done you fill in the inner squares using that information, but since the average heights per block are already constrained, in each block each square has only 10 possible values to pick from instead of 100, and long range constraints have already been taken care of by the earlier lower res pass.
Of course, not every system can be handled in that way, but many can. And you can also decide to have different rules at each resolution scale if you want to model richer behaviour. For example, for procedural terrain generation you can use the lower res for picking biomes, and then do increasing resolution to get transitions between biomes, and then increase resolution to do the actual terrain.
@Muffinconsumer4
Are you jealous?
This is what you get when you put "wave function" in the title.
what a dork
interesting, thanks for sharing.
Of course, just to qualify the obvious physics perspective that this comment is contradicting:
It's wave function collapse because you're considering a probability space (and I wish weights were mentioned) that reduces in dimensionality as individual values are enforced stochastically (the Monte Carlo part). It is somewhat similar to the corresponding concept in quantum mechanics if you were to measure a bulk sample randomly. Each measurement makes the possibilities of future measurements collapse into certainties.
It's a cute analog to me.
I can really see major utility in combining this with my existing procedurally generated island system to help me navigate designing and placing village prefabs in a natural way. Thanks a lot for sharing
Combining this with other systems is kind of my thought too. If you get something cool working, I would love to see it.
Please post a link to your video once you get it done
If you want to use it for towns, I hope you can come up with a nice rule for paths. The snacking stuff this example was spitting out hurt me lol.
@@Nevir202 I get that, it seems like a very early iteration and I think more robust path generation rules are definitely possible. Thinking about Minecraft when I say that even that billion dollar game can't seem to manage decent path generation. Villages have the craziest paths.
@@CSpottsGaming Ya, you would just have to layer other rules atop the system, like first randomly generating certain points of interest, then running something like standard pathfinding to decide where to lay in the paths, then generate the terrain afterwards.
Or generate the terrain, then then points, and then a more complex pathfinding script that would take terrain into account by weighting things properly. EG: humans will almost always walk a little extra, to avoid an elevation change.
This generates random terrain well, the issue is, paths and things humans and animals make, aren't random.
Immediately I notice that the algorithm can be applied to a partially filled grid, which makes me think that one really cool application of this would be to combine it with manual placement.
The idea is that a level designer could place tiles of interest to shape the "general feel" of an area, and then run the algorithm on that initial state to fill in the rest. This could also be done in chunks - suppose the designer is able to select a region of cells in the grid to apply WFC to, some of which can be partially filled to start with.
This feels promising enough that I might try to make a tool for it in my engine of choice sometime in the next month or so. I could see this being SO useful for speeding up the creation of areas which feel at the same time both hand-crafted and "naturally generated".
I've had a lot of these thoughts too. I think procedural generation as a tool for a level designer is a great way to go. It is one of the things I'm considering implementing much later.
I think sometimes with some intricate and huge system of rules you can get topological defects if you propagate the generation from different spots (manually placed ones)
@@egoreremeev9969 Yeah, I can see that being a possible issue. One way to fix this would be that if there are ever uncollapsed cells which cannot take on any cell in the rules, the algorithm should mark that cell as "uncollapseable" and have a designer come in and fix the cell / the area around it manually after the algorithm finishes. You'd hope that these would be rare, and an alternative to manually fixing it would be to run the algorithm again and hope one doesn't show up.
Another way to fix this, on the manual input side of things, would be to avoid placing topologically restrictive cells (i.e. those with few allowable neighbours) too close to one another. I'd guess that following this principle would, in many rulesets, ensure that the algorithm doesn't run into problems very often.
I think in this context where there is partially manual input and partially procedural generation, the right way to think about WFC is as a tool. It is useful for designing content, but there is also an element of skill involved - as you use it more, I would expect that you'd get a feel for how to get the most potential out of it.
I'm planning to make a Godot plugin for this in the next month that would integrate with Tilesets/Tilemaps. It would be cool to integrate this as yet another tool for level design.
@@egoreremeev9969 Not too much of an issue if you have error handling.
I was thinking of that while watching. Basically make a tile which gets plugged in anywhere that there is a failure to assign a tile given the normal ruleset.
A crater, a structure, anything that would be okay next to any tile, and set its base color to a gradient between the colors of its four sides.
Check out the Dungeon Architect project. They are doing exactly this.
4:40 thats actually a part of procedural generation that I love; I really like spending ages finding a way to have my artistic vision generated programatically, rather than setting it in stone myself.
I think I enjoy the difficulties of trying to figure out how to define my imagination
Programming (logic) is on the opposite spectrum of art (creativity), they can meet but it's complicated (and takes a lot of work).
Example, a computer has no perception of what makes a flower pretty, all it knows is how to categorize them through an input you give it.
In this case him spending years trying to force the program to understand what looks nice was his mistake which he admits.
What he really should have done (what he showcases later) is forced the logic to allow him to implement His own art, his own creative vision, it's is much better approach imo.
Computers are dumb.
@@publicalias8172 I have to say I disagree with you.
Computers are dumb yes, but they don't write the code, do they? Humans do. Does it matter whether someone uses code or a pencil to create art?
Your comment kinda reminds me of traditional artists saying digital art isn't "real art". Just because it's different doesn't mean it's not art.
I mean, what would you call technical artists? Their job (well, a part of their job) is literally to create art... from code, aka creating shaders.
Saying programming and art are opposites of a spectrum is definitely not true.
Sure programming doesn't necessarily need to be art, just as drawing something on a paper doesn't necessarily need to be art.
But I can tell you from personal experience, graphics programmers in the industry put A LOT of work into making things look good, they gather references, both from the real world as well as from other games, just like a regular artist would do. I think they would find it pretty offensive if you reduced their job to just "writing some logic" :P
@@publicalias8172 You have to be creative to be an engineer. You cannot make something if you aren't creative.
@@publicalias8172 I disagree, It's the math which can be the art form, combining different noise functions, tuning your algorithems just right to create the thing you are looking for, but mainly combining noise functions is what really creates the terrain.
@@publicalias8172 You're confusing medium with art. Programming is a medium, art is a form of expression that uses it. They are interconnected just like engineering, science, and technology have always been connected to art. You can't make new breakthroughs without creativity.
I'm a new programmer and I've always wondered about how world generation was implemented in games. This video is AMAZING and answered every question of mine. The production quality, too- just wonderful. Thank you.
Funnily enough, the WFC algorithm for procedural generation actually _is_ based on the wave function collapse in quantum mechanics.
Like the whole thing is basically setting each cell to a superposition of all states, then collapsing nearby cells by adjusting their probability distributions by adjusting the possible eigenstates. So it goes from a mixed system to a classical one.
So cool
There is no superposition of states involved, though. It’s more like the freezing of a liquid like water into a crystalline state.
@@lawrencedoliveiro9104 Any tile which could be one of multiple possibilities is functionally in a superposition of all of those states until it's "measured."
@@jakegearhart In quantum theory, a “superposition of states” means a weighted sum of the wave functions for all those different states. Since wave functions are complex-valued, this can lead to well-known wave-interference effects, as in the classic double-slit experiment.
There are no such phenomena going on here. There is no equivalent to the wave function; it’s just simple conditional probabilities, nothing more. No Bell’s Theorem, no causality violation or hidden variables.
Yeah like others said this has nothing to do with wavefunction collapse. This is just some cells and we make them continuous
Even for me who does not use Unity at all, your charming voice is so lovely to hear with the explanations you do. Gorgeous!
Thanks. I'll try to keep at least some of my material generalized and not Unity specific.
This algorithm feels like a huge advancement in procedurally generated maps! Thank you for sharing it
Of course it won’t be right for every situation, but it has so many possibilities. For a first person game, I wonder if it would make sense to combine Wave Function Collapse with the 3D noise underlying marching cubes? Something like at the start, you’d restrict which tiles are placable at each location based on the noise value there. I’ll have to play around with this!
That is a great thought, for a game of any style! It is actually on my to-do list. I have some code working now that can restrict the floors to solid tiles, the ceiling to empty air, and the sides to empty air as well. Ultimately, my goal is to have the wave function collapse algorithm read from a height map, but give it some room to do its own thing too.
It could be used for biomes?
@@ThylineTheGay : You'd probably want an iterative approach to that- generate an initial landscape, maybe run it through a convolution step to make sure the entire thing makes sense (e.g. joining near but not quite adjacent tiles to form rivers), then run it through another convolution to add biomes to the landscape.
@@ThylineTheGay Sure. If you want to think in terms of biome adjacency, this could work for giving you patches of biomes with transitions. I'm thinking something like transitioning from an extreme desert, to a moderate desert, to a scrub land, to a grass land, to a temperate forest. You could use wave function collapse to put things together, then use some other method to generate the tiles inside the biomes, maybe even with another layer of wave function collapse. @Jared Maddox makes good points too. I would probably want to factor in things like elevation and temperature. But adjacency alone might work too, depending on what you want.
It's actually 6 years old by now, it's cool that people have started using it more and more recently. Ultimately it's a simple version of constraint programming, it'd be cool to see if super-performant algorithms from that will start seeing usage in game development.
I always told myself I'd never get into game dev, but after just graduating and seeing all the effort and complexity that goes into something like this, I'm rethinking that.
I suggest try something simple as a hobby, with no expectations. It can be really fun if you like creative and technical kinds of things.
Dawg, 8:52 your pixel art is fantastic! Your control of contrast and form is unmatched dude. Don’t underplay yourself, you are talented!
Thanks, I really appreciate that. I'm definitely in a stage where I'm doing a lot of imitating trying to develop my skills. I'm going to keep working on it. You can check out some of my pixel artist inspirations for that tile set too:
twitter.com/UBadler
twitter.com/vivavolt
twitter.com/MartiansGame
@@dvgen hopefully you don't mind me asking this, but i have an interest in pixel art as well (but much more primitive in my skills, majority of my time goes to uni) and i wanna improve.
I understand some parts of colour theory and shading, but in terms of actual drawing, my skill just isn't there. I don't know how to practice it, and I want to learn how to draw while minimising mistakes that would make my pixel art in the future worse off (for example, i study engineering and just a few fundamentals regarding math & physics can make your life much harder down the road if you don't have them).
How have you been practicing, and if possible how would you advise me in doing the same? Thank you for reading this.
it reminded me of the early Ultima games, almost like an EGA palate on black.
Yeah, I was thinking it was pretty good too. So humble hehe
@@ynnad7778 It is still something I am actively working on, and I related to wanting to build strong foundations. I really just try to practice a little bit when I can, when I find something inspiring, but not be too attached to any of it. I've also found Adam C Younis's UA-cam channel to be really helpful. I also really like the Blender NPR channel for all sorts of non-photorealistic resources and inspiration, which sometimes includes pixel art like things.
i genuinely love seeing videos like this -- really nicely made passion projects. you're not afraid of showing off your pixel art even if you think it needs some more practice, and the explanations are really well done and visual
Thanks! I think, for many skills, including art and programming, there is continual growth and development. So yes, you can't feel bad about your current skills. It may not be where you want to be, but practice is how you grow.
Actually, as far as I can tell, the wave function collapse generation method is the same as quantum mechanical wave function collapse, except we randomly generate measurements (determining the boxes type) to reduce the domain (literally the same terminology, use tensor product space if feeling fancy) until we are left with one possible wavefunction (generated mesh).
If we want to get fancy, we can describe it as
a) wavefunction in the tensor product space of all the tiles' possibilities (so all the number 5's in each tile being almost independent of each other. If one wants more jargon, then 5 in each tile would be the Schmidt rank of the partial trace which eliminates everything except that tile)
b) an operator which takes any possibility which is incompatible with our constraints to 0, while letting all other possibilities alone. This is the information propagation stage in the code. So eigenvalues are 0 and 1, and we demand that our wavefunction be a 1-eignevalue of the operator, so we apply it repeatedly in discrete steps
c) the random hit generator which pins down the tile is just a simple projective measurement
I see no reason why one couldn't possibly generate more complex structures from this, except that any property which is non-local (not entirely dependent on direct neighbours) like connectivity in a maze, the propagation step gets very complicated very quickly.
I appreciate this description. It makes reading into the original quantum mechanics wave function collapse a little easier.
I did undergraduate physics only so I was struggling to make the connection, so my question would be in this analogy is each box like an individual particle with an individual state but neighbours are entangled + there's some global constaint?
@@michaelmoran9020 precisely. The total wavefunction would be something like |1⟩|2⟩+|3⟩|1⟩, with various products being determined by the adjacency rules, but to save space we store only the reduced states with each box's information in each box, so |1⟩+|3⟩ in box 1 and |2⟩ + |1⟩ in box 2. (More precisely it's |1⟩⟨1| + |3⟩⟨3| for box 1 if you have done density matrices)
@@VaradMahashabde so how is the global probability thing done since that's very non-local?
@@michaelmoran9020 You just take tensor products of the eigenstates of the components. If it's non-entangled i.e. separable, then it all factors out. Local interactions and such come from the operators, you can technically take systems of particles on two different sides of the earth, it's just that not many physical operators will act on both simultaneously.
e.g. box 1 is in |1⟩, box 2 is in |4⟩, then composiste state is |1⟩ ⨂ |4⟩ (normally i am omitting the tensor product symbol and requiring that the order be maintained here, so |1⟩|4⟩ ≠ |4⟩|1⟩)
if box 1 is in |1⟩+|2⟩, box 2 is in |1⟩, then the global state is (|1⟩ + |2⟩) ⨂ |1⟩ = |1⟩|1⟩ + |2⟩|1⟩
if the states are entangled, then we can't factorize it into a box 1 part and box 2 part, like so |1⟩|2⟩ + |2⟩|1⟩
I wrote a caves/maze map generator thing with basically this idea, without ever having heard of it before, so watcing this video kind of surprised me. I think thats pretty cool.
My own name for my version was erosion mapping, because it carves out space from a world full of solid blocks, then removes any walls that're only touching other walls, so the new eroded space is perfectly surrounded, ergo maze/cave generation as opposed to world generation.
Awesome video! This is an excellent explanation of wave function collapse. Thoroughly enjoyed watching it and am looking forward to your next video. Keep it up! :)
Thanks. Glad you enjoyed it.
Dude came outta nowhere and made a banger video. Super interesting and fun to watch. Please keep at UA-cam! I love your content thusfar
Really liked how you showed all the progress you made and explained everything, keep it up!
Thanks. Glad you liked it.
@@dvgen This video really picked up!
I've been reading about WFC a lot lately. One guy got amazing results by also using NEGATIVE connectivity examples in WFC. This way you don't have to specify all of the possible connectivity rules but can just prevent the rare cases you don't want for some reason. This gives much more artistic control.
I used something similar on a BotW-like that I made with my kid a little while back. One of the things I really liked about this method was the ability to have "landmark" tiles that would generate villages, ruins, and dungeon entrances in reasonably logical locations.
This is one of the best visualizations I’ve ever seen. It really helped me to understand this concept. Very good video.
it might be a good idea for a map to generate a few "necessary" tiles in random places before the wave collapse starts to start out with, so that certain needed locations always exist for what ever gameplay takes place in the generated world. then, if any tiles wind up coming into conflict, special case tiles could be inserted as a way to ensure there is a resolution to any strangeness that could cause.
I've had similar thoughts. You could pre-place some authored tiles, like a path, and have wave function collapse generate to fill in additional details. Boris the Brave's Debroilie / Tessera asset can do that, I think. It is definitely on my list of things to implement. I had not considered a few random tiles just to encourage and overall map feel though. www.boristhebrave.com/2018/10/06/debroglie-v0-1/
@@dvgen you wouldn't necessarily need to have the pre-placed tiles be deliberately placed by a human though is part of what I was saying, you could have a barebones procedurally generated map with almost no detail place the needed components for an adventure, then have the wave collapse fill in the details and make minor changes.
basically, have a primary and secondary pass to generate a world more complex than simple terrain generation would allow.
@@thomasstewart9752 Ah, okay, I understand. That could work well too.
Yeah! I'm imagining a scenario where the player needs to be able to travel across the map. You could generate a random path from one side to the other. Then you could add a constraint that all tiles along the path must be passable. Then when you generate the tiles, you'd always be guaranteed at least one path for the player.
Just came across this vid and it the exact solution to map generation problems I've been having for a while thanks an absolute ton for introducing me to this method
1:14 Wave Function Collapse is actually a really great name for algorithm. I suspect you touch on this in the next video, but this process of the "collapse" of a possibility-space into something concrete is EXACTLY what wave function collapse is in quantum mechanics (albeit much in a much more complex way).
Yep. Quantum mechanics is not my area, but I'll talk a little about the name and influences of wave function collapse in the next video. I'm really going to have to learn a bit more about quantum mechanics I think.
It seems to be more of a marketing term. Stick the word “quantum” on something, and everybody immediately goes ooh and ah.
Neato.
Just stumbled on "wave function collapse" last night researching a programming language/compiler (Virgil) then your vid appears on my youTube homepage. Intriguing and possibly destiny. Good vid btw. Had thought about random, dynamic texture and object creation with a defined pattern of rules that could be updated on a case basis, but never really got down into the nuts & bolts. Always fascinates me when stumbling into others with similar views. Appears you've got quite a good grasp on the topic - very nice.
Well now you have me reading about Virgil. Possibly destiny. :)
This is revitalizing my obsession with auto-generation. But it really should be called *domain collapse* but I can see how it is actually similar to the physics concept
This came across my recommended and after finishing it, I went straight to your channel. Eagerly awaiting more videos!
Everything old is new again. This reminds me a lot of Conway's Game of Life and cellular automata in general. Simulations could use this process to great effect, I think. If you had data encoded in each cell regarding say, resources available (food, materials, etc.), you could use that as a basis for things like simulating animal migration, human expansion, stuff like that. Really interesting to learn about practical applications for otherwise dry math concepts.
This is the first video of this channel I saw. Looooove this kind of in depth content. No matter how many views it gets it deserves more, please know that this is super awesome!
Well presented. I would not consider that work you put into a solution you are not going to use as wasted. Some lessons just cost more time than others, what matters is that you developed from that point to where you are now. Keep it up!
What the!!!
Your channel has TWO videos! One of them I would honestly not give the time of day, but this one is Sebastian Lague level of quality!
Thanks for sharing, you earned a sub!
Haha thanks. I'll redo the other one at some point. It was sort of a practice video. I might have upgraded a few things since then. :)
The pixel shader has a great style to it! Would certainly enjoy seeing more about it and other's like it, particularly interested in how it looks in motion.
Totally aggree on this. Resources on Pixelart Shaders are very rare. Would you be willing to share it?
I found the concepts you discussed pretty cool and applicable to data science as well, your teaching style is clear and your voice is great, subbed!
Thanks! Data science is not my area of training, but it is one I encounter sometimes doing traditional null-hypothesis testing for my research. I really like that some of these areas connect multiple disciplines. It is a great way to learn about something new, and also learn to see things you already know in a new way. After working on this for a while, I can't help but thing of everything in terms of graphs and constraints.
Consider adding time into the equation (maybe some value between -1 and 1, then you can feed a sine wave in) to the WFC. Eg, water can appear next to sand at -1, but ice at 1. For 2D you could fade between the 2 images for values between -1 and 1, for 3D you’d need a different solution (could use blend shapes if you maintain the same vertex count / order and blend between 2 mesh’s). The sine wave could represent a day / night cycle, a seasonal cycle, or even some sort of “force” (you could simulate earth quakes or waves).
I have no idea how I stumbled across this video but I'm really glad I did. This is a really interesting subject, and something I've wracked my mind against for a long time for similar reasons as you.
Great googley moogley, this looks like it took you absolutely forever to make. Thank you for the wonderful video. It was extremely interesting with phenomenal visualizations, chill background music and a nice voice. Felt like I was watch the next Sebastian Lague. I eagerly await your next Devlog, but no pressure :)
Thanks. I've been a big fan of Sebastian Lague since forever, and I really like his recent "Coding Adventure" series, so that is a very big compliment to me. And yes, it did take way too long. But I think I'm getting the hang of the workflow.
Randomly found this video on my main page. Absolutely do not regret watching it! Well done
You can use some like Binary Space Partition or any of a slew of other techniques in conjunction with this to add weights and biases to what can and can't generate, sometimes altering the generation rules entirely within a given region defined by the algorithm. It's an extra step that would give you tremendous control over how things look and feel at any scale. It's also probably not too much trouble to throw in any kind of geologically-inclined algorithm at this too, since it's all just about the rules for what the tile can 'collapse' into, after all. These things kinda run first, then you apply your wave collapse algorithm afterward to finalize the generation, and it has to adhere to the weights and biases introduced by any prior algorithms that adjusted what tiles can become. Thus, a very fun to tweak and get just right procedural tool is born. I'm probably going to experiment with this in a Godot project at some point, myself.
Looking forward to your next video! You have no idea, this is exactly what I've been looking for, and now I have a name for it. Thank you!
I imagine a hybrid approach of perlin noise layering + wave function collapse could create some pretty nice generation. Overall map structure is important.
Probably would be good to use Perlin noise to mask which modules are allowed to be generated by the WFC in certain areas, as if Perlin noise introduces biomes/climates. Could also try using Perlin noise (multiple instances) to add weights to the probability of selecting certain modules, but that’s like a more generalized but less perfect approach to the first idea. I think this second idea would result in the most dynamic generation for the simplest implementation.
it's always refreshing to see discussions about world gen stuff... that I can actually understand. Pleasant work, keep it up
An interesting thought that occurred to me while watching this video; when you introduce the grid of cells at 7:11, your rules don't need to be a direct relationship between meshes but could also be their relationships within the grid overall, like you could use Sudoku rules to guarantee that predefined areas contained certain features, or even categorize your meshes further into biomes for more distinct segments.
One question, is it possible to generate an "illegal" map where your adjacency rules result in no possible meshes in a space? If that occurs, how do you handle it?
Yes, you can do lots of different rules and constraints. I've only implemented the basics so far. And yes, the generation can fail. I'll show some solutions different algorithms use in the next video, but backtracking or completely restarting are common options. The tile set you use matters a lot too. I've never had it fail in 2D, and 3D failures are rare, unless I don't give the algorithm enough tile types to be flexible.
I love exploring different procedural methods of creating maps and structures. Fractals, and setting rules, limits, and boundaries are neat tricks that with todays technology can work with any kit bashing method approach. Simple and fun, looks good. To truly get realistic or plausible builds these methods must be carefully calibrated and tweaked. Using topographical maps and how water, sand, and even harder stuff flows over time across a landscape can give that plausible yet interesting and even unsuspected look. I like that too, it is a creative process. Thank you for sharing this.
I haven't tried it yet, but I wonder about generating a height and water map first, and then having something like WFC come back and add variability and tiles from there. I did some hydraulic erosion simulations a while back, and modeling a natural process like that really amps up the realism.
How do you guarantee that you don't back yourself into a corner where no tile is allowed? You mentioned favoring picking the next tile where the domain is smaller, and then in later clips you have a very directional method (or is that just the animation?). Are there any rules that affect more than just direct neighbors?
This reminds me of weighted wang tiles, which matches against each edge type instead of each whole square.
Good thoughts. I'll go into that more in some of the next videos. But yes, an unsolvable map is a possibility. The main options are 1) regenerate the whole thing, 2) backtrack to an earlier point in the solution and try again, and 3) build the map in smaller pieces, with each overlapping a bit. Solution #3, "modifying in blocks" is what I will try later. For the moment, though, the tile sets I have are pretty robust. As the tiles become more complicated, it is easier to have issues. So thinking about what pieces you have is also important.
There are also different ways to do iteration. In most of the clips I pick based on small domain, but in some of the last ones, I just go in order. Each method has strengths, and it's something I'm still evaluating.
You can add a lot more rules and constraints. I'm only working in direct neighbor category right now, but check out Boris the Brave's Debrogile / Tessera library for some of the more involved things you can do.
boristhebrave.github.io/DeBroglie/
you could probably just reroll tiles adjacent to bad tiles until there are no bad tiles left.
This wont always fit your needs, but you can potentially make one tile that is *always* available for use and that never gets ruled out by neighboring tiles. Something of a fallback tile.
you can take advantage of such cases by adding tiles which should only spawn very rarely and in lines by spawning them in these zones - as unsolvable maps are naturally relatively rare, at least depending on your tilesets.
Such tiles would need to be implacable (can be placed next to anything, including itself) and will usually 'clump' in line along the 'dead zones', acting as a sudo-'edge' of that tile - if not literally the edge of that tile if your situation allows it, allowing obtuse tile generation.
I wrote a WFC inspired map generator where the probability for a given tile was pretty complex. Like it took into account how many had been placed among other things. One thing I did was backtrack a tile placement that dropped any cells to zero possible tiles. Granted, sometimes there was only one choice and in that case, I threw the map away.
This came at the perfect time for me - I'm about to start working on a terrain generation system for a hobby project and I've been terrified of approaching it. This has really shed some light on a great way to get more control over the generation algorithm, so thank you for sharing! Also the animations were a great help in understanding how it all works, great vid!
I’d like to see more detail with regards to the tile selection rules, and also the voxel generation if that’s still underlying. It seems that a naive approach would tend to give too random of a distribution at the small scales, leading to no larger overall shape and so no fractal coastlines. Perhaps having a bunch of deeper and deepest ocean tiles, higher mountain tiles, etc. would help, assuming tile selection is what decides the terrain height. Perhaps running multiple iterations of wave-function collapse at progressively narrowing scales would provide better results?
I think you are totally right. Without some help, the algorithm can start to produce things that are a little too random. Having some transition tiles, like water depth, will help. I'm also really interested in the idea of multiple levels of iteration. Hierarchical wave function collapse perhaps? More details to come in the next videos.
@@dvgen This hierarchical thing reminds me of an idea I want to try out some time where you start with generating a graph (nodes & edges) and then turn that into a level in multiple steps, with nodes being more or less large areas and edges the paths between those areas (which might consist of tiles). So kind of along the lines of Monster Hunter or Dark Souls-style world maps with areas linked in various ways. And the way you layout the graph and generate the edges between nodes would influence the overall style.
@@SaHaRaSquad Ooo, I'm into that. I'm trying to get more into graph things like that.
Looks like most of the comments here are other devs and hackers. I just want to say as someone who likes playing games but not making them that i still found this really interesting. I like your style, direct to the point, no fluff, visually rich. I’m definitely subscribing and hope to see more from you
if you're still not quite satisfied you can try adding a shell or wrapper for it especially for verticality, either a nested waveform, weighted veroni, poison disc sampling, or my personal favorite reaction diffusion. standard waveform never really had the kind of topology I was looking for but is seriously impressive for what it is.
This is an awesome video!! I love Oskar’s posts. Can’t wait for your next video :)
This is a great WFC collapse explanation! I'd be interesting to hear how you're going to deal with situations where there is no valid tile - or whether your marching cubes rules mean that there will always be a valid tile. Have sub'd and looking forward to the next!
Thanks! If you are smart about what tiles and connectivity rules, those issues are rare. Eventually, I will implement a "modifying in blocks" type approach that will regenerate sections as needed.
Interestingly, the possibility of encountering an invalid situation also depends on the iteration method. I'm trying both scanline and lowest entropy approaches, and they aren't always equivalent, even with equal weight tilesets. Scanline seems to be faster and more robust, but might have some directional artifacts. That is the kind of thing I want to talk about in later videos.
I have enjoyed it. Thank you so much for documenting your WORK!
My thought when seeing your first larger wave function collapse example at 8:36 is that the water areas look too small. Iʼm sure there are ways to solve this with the rules you provided, but my first thought was to extend it so each neighbor, in addition to ruling some things out, changed the probabilities of the adjacent tiles, so that choosing a new tile adjacent to water might have a 90% chance of being water and only a 10% chance of being sand. If there are two adjacent water tiles, that would combine to 99% chance of water (9:1 water to sand ratio, squared), up to 99.99% for four adjacent water tiles (which is probably too extreme, but theyʼre illustrative and easy numbers to work with). Is that a thing thatʼs been done before here?
Either that, or just define different tiles for different depths. So you have shore, shallow water, deep water. Deep water has to be surrounded by shallow water. So if you ever have a Deep Water tile somewhere, the surroundings have to be at least 1 shallow water and one shore. That way, the water areas are bigger in general.
I got a lot of comments on this type of thing, so you are picking up on something many people think is important. This example lacks transition tiles since I wanted something really simple for the first demonstration. Adding the transition tiles softens the change, but also adds a minimum size to the water features. From there, adjusting the probability of tiles, and certain types of transitions can indeed let you dial in the type of generation you want.
@@KYL3R64 You are right, this is also something that can be done. I thought about including it, but I didn't want to do too much at once with the first demo.
@@dvgen You did transition tiles with the large and small trees; I think it makes sense to not also do them on the other end.
This was quite fun to watch, I'd love to see more of your processes
Even if I don't ever have much use for it, it's still fairly interesting
4:12 one reason using a switch is actualy a bad idea, to see what's happening you have to scroll all the way up
worse you manually write every case. this is still hard coding even if you're not directly putting the number values there
a better way to do this is to make each case a member of a (voxel rule class) , that holds the data about the system
then if you serialize that you can save it to a file without having to edit the code directly
this way could be much faster because every change you make shows up immediately instead of every {close game, recompile, open game}
That is a great idea. Would have been really helpful if I kept going that direction.
AHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
Great description and discussion, really looking forward to your follow up video on this topic!
“It would be nice to talk to people with similar interests” I am impressed. Pardon my lengthy ramble. I probably won’t respond further, I often go quite in depth with thoughts
I find this content very knowledgeable while also embracing your intrinsic emotional experience. Memes are funny too. I learned something new not just about voxels, marching squares, wave function collapse, tradeoffs during development, but also about the process of being a human working on a game. Interested in kinesis too
One thing I found interesting was how the water would often form in illogical ways. It appears you were already experimenting in that direction with southwards flowing water. Talking about the connectivity rules, I suppose you could make dummy layers for things like oceans/lakes/rivers with the same tiles extended in different axis of scales. So, very deep water being 7o, deep water being 6o, water being 5o, and coast being 4o, with lake being maybe 5L, 4L that don’t connect with the o’s and rivers being 4R. Or changing the selection method, or the propagation method. Certainly easy to get distracted by side projects when there are so many interesting ideas and experiments to explore! I do tend to find in my experience working towards a goal with realistic steps tends to curb the side projects. But then I have to set aside the reward of interesting and learning, so the reward of that goal needs to be suitably enticing to make that trade.
Normally I don’t really have a lot of interest watching devlogs of people generating hype for their games by regurgitating the same experiences that others have had and expressed. As someone obsessed with learning, it can often feel pretty disappointing and embittering to invest in watching videos and not learning anything from them. But I grit through that expectation for the sake of possibly learning something. This was more than I bargained for haha. The idea was so well explained that I’m now convinced it’s a great method to implement creatively, much preferred to the marching square tedious manual case by case coding.
You know, I have a career already, I'm not under any illusion of making it so big on UA-cam or making tons of money on a game that I can quit my day job (plus I like parts of my day job), and I've really got nothing to shill. I really just like learning (I'm obsessed too) and talking about kind of stuff. So I really did mean it would be nice to talk to people. I got started on Twitter and met some cool people there. I wasn't, however, expecting this to be so well received. Look at all those comments! So many cool ideas (yours included)!
I do think you are on to something with the water. Wave function collapse can give you a valid solution. But it isn't necessarily an aesthetically pleasing one. You have to do a lot of tweaking to get the kind of result you want. I have one picture I might show later, where I was testing out the waterfalls and rivers, and the algorithm gave me a map that was like 90% waterfalls and rivers. So I'm like "okay, I guess that is technically correct." It is a kind of thing where the algorithm is alway right, but not always pretty.
maybe generate a map that biases all the cells, so it biases one region towards water and another towards land. or maybe run the whole thing at multiple resolutions, then subdividing the grid and using the previous to limit the options or bias the picking, maybe with some smoothing like a median or gaussian blur
This is the best explanation of WFC that I've seen, ever. It explained it simply and made it approachable. I'm really looking forward to your explanation of how you implemented your rule set!
The final maps still tend to look too random, like the one at 8:36. Im curious what would the maps look like if there was a weight attached to which tiles should be picked based on neighboring tiles.
It was the first thing I thought to. Having some probability for transitions... It start to sound a little bit as some Markov chains but in more dimensions.
More tile types with more rules can help with that, as well as broader rules that may take into consideration "tile" types that are further out.
I was thinking there could even be a larger "Region" ruleset - perhaps a region is a 3x3 or 5x5 area of tiles, and in each Region there should be one of a pool of geographical Landmarks (Could be a mountain, forest, canyon, etc.) to draw attention to. Tiles closer to this feature within the Region would be transitionary biomes/tiles/heightmaps bridging the difference between the Feature tile and the outer border Tiles
Appreciate this approachable explanation. The name always reminded me of the Wave Motion Cannon (from Oni), which I understand was itself a reference. On the first watching, it wasn't clear that the number in the cell represented the count of possible solutions to the rules. But I eventually got there!
Nice going.
The behavioural research, computational automata, and bee booping are right up my alley. I'm excited to see what other cool stuff you make!
Glad to hear even the boops are appreciated! I'm not sure the bees feel the same way. I'll be back to focusing on behavior a little more once some of the terrain systems are a little more developed.
I'm not currently working on any projects that could use this but I'm gonna keep it in mind for my big future dream game. Thanks so much!
You're really good at explaining this. Would you perhaps be interested in doing a more detailed walkthrough of working with WFC? It's gonna be a few months till I can get back to programming because of real life stuff, but you've definitely piqued my interest A LOT.
Hey man I watched both of your videos and I must say, I'm a fan!!! I'd love to see more such content, so PLEASE make more!
I implemented blocks then marching cubes, but I never sucedded to implement dual contouring, I ended up with a big cloud of triangles that I could never fix.
This wave function is not about rendering voxels but generating them, it should be compared to simplex noises, geological simulations, etc. I like the freedom it gives, but the huge amount of rules required and the undeterministic results are serious limitation.
8:30 Gorgeous results for such simple rules.
0:57 how you get, that would be great for lava :O
you have a realy nice way of explaining stuff and I was left wanting more. keep up the great work!
🤔 how strange. i watched your video and you gained a subscriber
Strange indeed. One of the many mysteries of the universe.
This is right up my alley! Looking forward to your next release
This is truly amazing, your video inspired me to do something like this! I've spent big amount of time working with procedural generation, but never came across this thing. Thanks!
I hope you are able to make some fun things with it. I'd love to see what you come up with.
Incredible video and absolutely beautifully animated. Thank you for sharing your findings and making it much easier for the rest of the community to find alternatives to voxel meshes!
Wow I don't know how UA-cam didn't recommend this to me sooner, but this is a masterpiece explanation and demonstration. Excellent work! Edit: Holy shit, buildings generated by your terrain algo is fucking brilliant, I can't believe I never thought of that.
This was surprisingly easy to digest, and very entertaining!
it's great, in particular, as a CS student, I liked that you put the source in the description or showed it, it's handy.
I'm an academic, so I've gotta cite my sources! :)
Thank you for this video! So interesting, I had no idea about neither of both algorithms and now I’m looking forward to try by myself!
This has so much potential it looks really good
I didn't understand almost the entirety of the video, since it's way above my head. However, it seems like whatever you're doing is really amazing and taking your artistic endeavors to the next level. Keep up the good work and keep moving forward!
I love it, super excited to see this channels direction
Very nice video! I really enjoyed the information, dude, I was thinking oh another video for 10 minutes of blah blah, but I was spell bound! Thanks for sharing, you've got a subscriber here! I'm an aspiring game dev, and I've been considering wave function collapse as a generator for a bunch of things, like terrain, buildings, etc. Thanks again!
Thanks! I hope you will find some of the later videos useful as you work on your project.
Thanks for explaining wave function collapse in a way that's easy to understand!
Really nice and interesting video, looking forward for the next one!
Fascinating! The explanations were all really well done, the effort you put into those is super appreciated. The simple rules are so elegant, makes me want to do something with procedural generation.
Wow1 What an intuitive and simple yet genius way to generate things. It makes so much sense right from the beginning, and it looks much cooler than the standard voxel grid. Definitely going to use this for fun. Thanks for sharing!
I've really enjoyed it. It is definitely worth playing with, especially in 2D. I agree, it looks a little more interesting than a voxel grid. Imagine what it could be like in the hands of a talented artist.
This is amaizing. Can't wait for the next video!
Awesome! Loved the video! I’m going through something very similar with my own map generation and it’s awesome to see your thought process! Thanks!
Awesome video! Excited to see what’s coming!
Thank you for the unexpected Wilhelm scream. It gave me a hearty chuckle.
I found this video while searching around to see what Voxel CAD tools were floating around.
I enjoyed seeing the various different approaches you used to do procedural generation.
I hope you are able to make more development diary videos of your projects.
ditto
I'm so happy I stumbled upon this. I'm in the process of planning a 2D game out that is essentially an IDLE Colony Sim and my first hurdle is figuring out terrain generation. Thanks for this, as it opened up an entirely new world (heyoooo) of possibilities.
Cant wait for the second video and see the technical side of your implementation
It's coming, just taking a little longer than I first thought. There are some fun technical details to cover.
Thank you , thank you, thank you. I was struggling with my PG terrain design and you've inspired me to try this approach.
Just found out about Wave Function Collapse today, and this is the second video I've seen on it.
Love the irony that I want to implement this on a voxel game.
Damn it is a lightbulb moment, you explained the order of tiles and showed the result and suddenly it was all I could think about :D Nice explanation. Maybe I'm going to use it someday.
Holy shit. You just made me interested in actually using procedural generation in a game. I been thinking of never use it, cuz I don’t typically like how it’s been done, but damn!
Also you’ve earned a a sub.
I haven't put much thought into how to approach procedural generation, but after seeing how this works it seems like such a good answer, especially when combined with other forms of logic to generate those initial points.
Really appreciate this video, and you taking the time to just teach us, just like for free. No other purpose. Just taught us something really valuable.
subscribed. You have a pleasant voice and are really good at explaining stuff. I am and developer with one too many hobbies. This was something that interested me a lot but I could just not bring up the time to start another time eating hoppy. So this style of you showing your progress and how things worked was almost like an ASMR video for nerds. I like that. gonna look through your other videos and see what other stuff you have.
edit from 10 sec later: just 1 other video. awww man. Guess I need to wait for the next video. But alas, quality videos do take time.
Soon ™ :)
Those look awesome, I'm gonna use this. This was an excellent video, sad you've only got two on your channel. Subbed and waiting for more
ez sub, that shit was badass. I can't wait to hear the technical breakdown, it give me so many idea!
I've only ever seen wave collapse algorithms in regards to quantum computing so this is a very interesting change of pace.
It looks like a simpler version to save the computer the pain of doing it wothout superpositions
Wow the pixel shader looks amazing. This method is exactly what I think I need to finish my procedural dungeons the way I want them! I used another method that just wasn't working for me and was bland. This really seems like it will fill in the gaps I have, and i can't wait to see more!!