Really interesting, but I think anyone interested in this would do well to check out [0]. It takes the article's second algorithm somewhat further, considering all the output tiles to start out as uncollapsed wave functions, and then going through and trying to collapse them in such a way as to obey local constraints (matching at their borders) and large-scale constraints (having each tile occur in the output at a frequency similar to some frequency defined by the inputs).
Also on the notational side, [0]'s approach of using a plain graphic as an input, and inferring the desired tiles and tile frequencies from it, is maybe more approachable than that of TFA. (Though in either case, if you hack on it I suspect you'll eventually wind up doing something ad-hoc..)
The other fun thing with WFC is that you can wrap the constraints on the edges (ex. matching the right edge of the rightmost tiles to the left edge of the leftmost tiles), which allows you to easily make tiling patterns.
You can also start matching tiles and edges for more than just colours... for example, you can have 3-dimensional tiles, or you can even match edges of tiles using time as a dimension, like I did here: https://twitter.com/MattRix/status/979020989181890560
I second that. Nice presentation of the material, but I think that https://twitter.com/ExUtumno "WaveFunctionCollapse" is most likely a direct predecessor and big influence on this work. So, must be referenced much earlier, and not reduced to a footnote in the end, otherwise it feels we are cheated here.
The best part is probably that this system is so simple that it allows for many extensions, customizations or new rules and variations. You could solve this on prolog, for example, defining tiles as 4 numbers (one for each side), and what you effectively get is a distribution of tiles, that you can later "paint" as you want. You could later add even softer constraints, like density or others.
Neat, yes, but when you do procedural generation from local information only, you often get artificial looking "dungeons".
Though, it does make me curious about what extending this to use a "hierarchical" tileset might do. For example, start with large tiles that define a probability distribution. Tile those. Use that to initialize the probability distribution for the smaller tile generation.
I just played Carcassonne last night and immediately thought of it when I started reading the piece. I am not sure how the game designers built the game to almost always ensure there was a valid configuration, in my play-throughs I think I have only hit that situation once.
After looking up a couple images -- that game appears to use Wang tiles. They're also sometimes used for terrain textures in video games to make seamless mosaics with less obvious repetition.
While they could be drawn similarly to how Wang tiles are drawn, they definitely lack the aperiodicity property of Wang tiles. (Eg there are tiles with all four edges the same, hence you could tile the plain with nothing but that tile.) Of course the other distinction is that you only use each tile once in Carcassonne, unlike a set of Wang tiles.
With Carcassonne it's easy. You never have to go back in and solve the unsolvable areas of the puzzle. I've had players get really pissed when they realized my river placement meant they'd never be able to finish their city. There also aren't that many edge types, you can rotate your tiles, and there isn't a space limitation (you can just keep building outwards).
I'm impressed by the procedural world in the link, but I am curious about the situations that lead to unsolvable maps in his second algorithm.
As long as your tile spheres are large enough that all probabilities along the edge are non-zero (this may mean infinitely large), the only situation that creates an unsolvable map is when a tile's probability in a space goes to zero. In his algorithm, this can send the real probability of tiles in other spaces to 0 (without the calculated probability being set to 0). Given that there are polynomial number of probabilities across all spaces and all tiles, I wonder if there's some calculation you could do every time a probability goes to 0 that would update the other probabilities and prevent unsolvable situations.
Edit: I should point out that I am not very convinced about the futility of this, given that he has demonstrated that tiling is a subset of CSP, not that CSP is a subset of tiling.
Constraints can be "easy" enough to prove that a solution can be found trivially without backtracking (e.g. large sets of Wang tiles with one or more tile choices for any possible combination of edge types), "hard" enough to emulate a Turing machine (possible with Wang tiles alone), or anything in between.
Going beyond Wang tiles and corner tiles, constraints can be nonlocal, for example "the map contains 2 to 3 treasure room tiles" (which can be proved to form exactly 1 treasure room) or "river tiles belong to the same connected river component, accounting for flow direction, as a river tile on the edge of the map, or a river beginning tile, or a river end tile".
So efficient CSP solution is an engineering problem: there is the very easy case (no backtracking), the hard case (let's search for a couple of hours with a state of the art constraint solving package) and the interesting generic case (general constraints, used with significant restraint for efficiency reasons; complex but hopefully quick computation; interactive assistance to signal unsolvable and close to unsolvable sets of constraints and their problem sites.
Also on the notational side, [0]'s approach of using a plain graphic as an input, and inferring the desired tiles and tile frequencies from it, is maybe more approachable than that of TFA. (Though in either case, if you hack on it I suspect you'll eventually wind up doing something ad-hoc..)
https://github.com/mxgmn/WaveFunctionCollapse