Boris the Brave writes on procedural generation, covering dungeon generation in games, Wave Function Collapse, constraint solving, and related graphics algorithms.
HN commenters call his writeups some of the best explanations of these topics, and link his posts on Diablo dungeons, graph rewriting, and dual contouring.
> The maze-creating algorithms might be interesting for computer scientists, but they're terrible at creating mazes interesting for humans!
Not sure what would lead you to that conclusion. There's only so much you can do with (for example) a two color palette and no lawn art but it goes without saying that there's nothing restricting an implementation to the sort of minimalist methodology that's so useful for demonstrating an algorithm for the reader.
The last time this was posted [0] someone linked this article [1] which provides a nice visual demonstration of the structural differences between a few of the algorithms (scroll down for the color floods I'm referring to). Of course this can all be implemented as a graph (ie nodes that have coordinates) rather than as a grid, empty space expanded (ie coordinates subjected to an arbitrary series of affine transformations), branches of the tree overlaid after the fact to add weave (ie rotating and translating the coordinates of subtrees), nodes expanded to represent larger areas instead of single grid cells, whatever you'd like.
Also see the modifying in blocks algorithm applied to an escheresque tileset [2] (from this article [3]) which will produce a solvable 3D maze (multi-path and multi-solution) if given an appropriate tileset.
[0] https://news.ycombinator.com/item?id=10101728
[1] https://bost.ocks.org/mike/algorithms/#maze-generation
[2]…
It's been discussed numerous times that this is simply a constraint satisfaction problem with hand-wavey BS applied over the top.
Here's a good (free) explanation:
https://www.boristhebrave.com/2020/04/13/wave-function-collapse-explained/
Specifically read the 'Least Entropy' section: It's broken down very simply:
Pick a random tile which is the 'least random', because (due to already having resolved the constraints we can), this is most likely to be a cell that won't cause problems (ie. unsatisfiable constraints) later.
You might also like to read this (also) free paper on implementing WFC using a constraint solving library: https://canvas.ucsc.edu/files/109152/download?download_frd=1, which I quote here:
> The heuristic of selecting the most constrained variable or equivalently the variable with minimum remaining values (MRV) is well known in constraint solving.
> Since there is more than one valid pattern for that location—or it would already have been set to zero entropy in the previous loop—one of those patterns needs to be chosen. One of the patterns is chosen with a random sample, weighted by the frequency that pattern appears in the input image.
> This implements Gumin’s secondary goal for local similarity: that patterns appear with a
similar distribution in the output as are found in the input [12].
Read through the Super-Mario analysis, but refer to the all-caps table down below as you're reading. (HERO, NEO, BAD, DRAKE)
They're basically analyzing "tropes" (common storytelling patterns), and doing something similar to advanced procedural dungeon/level generation: https://www.boristhebrave.com/2021/04/10/dungeon-generation-in-unexplored/#Cyclic_Dungeon_Generation
...at least this appears to be a first cut at defining a vocabulary for the storytelling aspect of the problem.
They refer also to other "Key + Door == Progress" aspects of procedural content generation (ie: make a zone, place a [locked] door to another zone, place a key within the original zone and then recurse).
All told, a very interesting area to explore.
Boris the brave coined the term "Constraint Based Tile Generators" (CBTG) [0], which is a specialization of the more general CSPs to this particular domain.
Personally, I find CSPs overly general and mired in esoteric, byzantine terminology. It's a large cognitive load to put on people to run through the glossary of terms just to talk about the problem set up. I don't think the quantum mechanic analogy is great but I can see it being much more intuitive than the obscure language of CSPs.
[0] https://www.boristhebrave.com/2021/10/31/constraint-based-tile-generators/
Explanations of the method:
- https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/, 44 comments https://news.ycombinator.com/item?id=18744696
- https://www.boristhebrave.com/2020/04/13/wave-function-collapse-explained/, 18 comments https://news.ycombinator.com/item?id=18321168
More threads: https://hn.algolia.com/?q=wave+function+collapse
+1 datapoint: I've decompiled several to find out how they work, and found most use mono. Maybe it depends how indie your game is?
My dcompilation writeups can be found here: https://www.boristhebrave.com/category/level-generation/