I absolutely hate the name Wave Function Collapse, though I do get the logic behind the naming choice. But indeed, this is really just constraint solving with a different name, a domain-specific heuristic, and the neat "learn from an example image" capability.
The latter isn't even required, one can define the adjacency rules manually, which can be really useful to implement an editor for example (and is something machine learning-based solutions can't match).
The nice thing about WFC being just constraint solving, is that all the techniques from constraint solving apply: You can make the "flood fill" part really efficient with a proper arc-consistency algorithm like AC3. Backtracking a bottleneck? Go the SAT-route and add conflict-driven clause learning. Want to add an optimization goal (e.g., maximize the number of snow tiles) and solve that efficiently? Go the MIP-route and add in linear relaxations and Simplex. Need to generate absolutely massive tilemaps/images? Can use portfolio solving, cube-and-conquer, or mix in local search techniques like large neighborhood search, etc.
People sleep on constraint solving and just how powerful it can get.
To be fair, Wave Function Collapse is quite a marketable name, and it does give a nice set of vocabulary to use when talking about the different steps of the algorithm (e.g., a tile position has collapsed to one possibility). But yeah, it makes it sound way cooler than it actually is, but then again, who doesn't engage in a bit of clickbait?
I do think the "learn from an example image" feature is quite useful when using the overlapping tile model and reflections/rotations (which I didn't really cover in this article). You can generate a lot of unique tiles from a very small source image when doing that, and the algorithm will figure out all the adjacency rules for you. Though, I do agree that if you already know the adjacency rules beforehand, it's easier/more reliable to just encode them manually.
As for using AC-3, the vanilla implementation of WFC only has local constraints that have to be solved more-or-less in sequential order, so I think flood-fill is pretty optimal for that (though, I've never used WFC for particularly large outputs either, so idk for sure). However, I do find it interesting to use WFC in combination with other constraint-solving techniques. A more general constraint-solver would allow you to specify constraints beyond X tile can/can't be placed next to Y
Yup, combining with other kinds of constraints makes for some really neat possibilities. You could for example mark two tiles in the target tilemap and add a constraint that there must be an open path from one to the other. That requires tracking extra information beyond adjacency, in this case traversal.
I absolutely hate the name Wave Function Collapse, though I do get the logic behind the naming choice. But indeed, this is really just constraint solving with a different name, a domain-specific heuristic, and the neat "learn from an example image" capability.
The latter isn't even required, one can define the adjacency rules manually, which can be really useful to implement an editor for example (and is something machine learning-based solutions can't match).
The nice thing about WFC being just constraint solving, is that all the techniques from constraint solving apply: You can make the "flood fill" part really efficient with a proper arc-consistency algorithm like AC3. Backtracking a bottleneck? Go the SAT-route and add conflict-driven clause learning. Want to add an optimization goal (e.g., maximize the number of snow tiles) and solve that efficiently? Go the MIP-route and add in linear relaxations and Simplex. Need to generate absolutely massive tilemaps/images? Can use portfolio solving, cube-and-conquer, or mix in local search techniques like large neighborhood search, etc.
People sleep on constraint solving and just how powerful it can get.
To be fair, Wave Function Collapse is quite a marketable name, and it does give a nice set of vocabulary to use when talking about the different steps of the algorithm (e.g., a tile position has collapsed to one possibility). But yeah, it makes it sound way cooler than it actually is, but then again, who doesn't engage in a bit of clickbait?
I do think the "learn from an example image" feature is quite useful when using the overlapping tile model and reflections/rotations (which I didn't really cover in this article). You can generate a lot of unique tiles from a very small source image when doing that, and the algorithm will figure out all the adjacency rules for you. Though, I do agree that if you already know the adjacency rules beforehand, it's easier/more reliable to just encode them manually.
As for using AC-3, the vanilla implementation of WFC only has local constraints that have to be solved more-or-less in sequential order, so I think flood-fill is pretty optimal for that (though, I've never used WFC for particularly large outputs either, so idk for sure). However, I do find it interesting to use WFC in combination with other constraint-solving techniques. A more general constraint-solver would allow you to specify constraints beyond X tile can/can't be placed next to Y
Yup, combining with other kinds of constraints makes for some really neat possibilities. You could for example mark two tiles in the target tilemap and add a constraint that there must be an open path from one to the other. That requires tracking extra information beyond adjacency, in this case traversal.