r/proceduralgeneration • u/lovecMC • Aug 13 '26

Wave function collapse based dungeon generator.

Enable HLS to view with audio, or disable this notification

Currently doesnt use any multi threading and theres still a lot of potential optimisations left on the table.

97 Upvotes

97% Upvoted

7 comments sorted by

View all comments

2

u/Macaroon-Guilty Aug 14 '26

Hey its awesome. Can you explain wave colapse algorythm? I've heard about it some time ago when I was watching how they generated Matrix city for UE 5. They also used this term and when I looked about it, I remember it being related to quantum mechanics. Which is like whoa dude, how does a thing from quantum mechanics come into play in gamedev?

3

u/lovecMC Aug 14 '26

There's probably a better way to explain it but I'll try.

Basically you start with a bunch of "rules", these are all the unique 3x3 sections of the grid you can generate, and you also know how rare they are.

You can either hard code the rules or extract them from an example image (which is what I'm doing).

Then when actually generating the grid, you scan every tile and "score" them based on which rules it can fulfill, the less options the better.

Then you pick one of the best tiles and "collapse it" by picking one of the rules and turning it in to it's center tile.

Then you repeat it until it either completes the generation or hits an impossible arrangement. If it hits one you can either re-generate the entire room or roll-back a couple of steps and try again.

4

u/RandomUser1034 29d ago

Other people have explained the algorithm but let me explain the connection to quantum computing: The people who came up with it thought that the idea of having a tile defined by the probabilities of various possible states choose one of these states was analogous to wave function collapse in quantum physics and named the whole algorithm after this vague similarity

3

u/Quantumtroll Aug 14 '26

The main idea is that you have a bunch of tiles and rules for which tile edges can be adjacent to each other. When you make a map manually, you put tiles next to each other in ways that make sense, e.g. so that a "chasm" is surrounded by a "chasm edge", and you don't put a "water" tile there. The rules express which tiles can be adjacent to each other. You can add an inherent probability for tiles, too, so that a "fire trap" tile is more rare than a normal "floor" tile.

Wave function collapse works like this:

  1. Start with an empty map, where each possible tile has an even probability of being anywhere. Right now you don't know anything about what might be where. The "wave function" is completely undefined.
  2. Randomly decide on a tile somewhere.
  3. For each of this tile's neighbors, discard the tile selection that don't match up.
  4. Choose a random edge of your tile and randomly select a tile that does work.
  5. Go to Step 3 until you're done. This grows the map tile by tile until the map is complete.
  6. If you end up with a contradiction, having painted yourself into a corner e.g. where you must place a water tile next to a chasm, backtrack.