Discussion
Building a Procedural Hex Map with Wave Function Collapse
MattDamonSpace: Gorgeous
gedy: Real engineering skills, I love it.
moi2388: This entire article reads like it was fully written by AI unfortunately
tomtomistaken: Reminds me of Dorfromantik[0].[0] https://store.steampowered.com/app/1455840/Dorfromantik/
jcul: That "Carcassonne" game sounds really fun. I'd never heard of it before.
jcalx: Reminds me of Jasper Flick's Unity tutorial on hex terrain [0] which is similarly wonderfully detailed. Interesting contrast: this project uses premade tiles and constraint solving to match tile boundaries, while that one dynamically generates tile boundaries (geometries, blending, etc.) on the fly. Both enjoyable reads![0] https://catlikecoding.com/unity/tutorials/hex-map/
porphyra: The post glosses over the "backtracking" and says they just limit it to 500 steps but actually constraint programming is an extremely interesting and complicated field with lots of cool algorithms and tricks. In this case we could solve it with Knuth's Algorithm X [1], which is a special kind of backtracking.Furthermore, various heuristics can speed up the backtracking a lot compared to a brute force approach. As anyone who has implemented a Sudoku solver can attest, a brute force backtracking is easy to implement but will immediately get bogged down with slowness.[1] https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
bhaak: Which is based on the board game of the same name.https://boardgamegeek.com/boardgame/370591/dorfromantik-the-...
the_mitsuhiko: The other way around.
bhaak: Oh, wow, TIL. Both were released in 2022 but the video game already had an alpha release in 2021.
jbmsf: Years and years ago (pre-smart phone), I built a mobile map and navigation product. Labeling streets was one of the more interesting side quests and the solution I found took a similar approach of generating a large number of candidates, picking one solution, and iterating. It worked quite well in practice.
shoo: there's also a bunch of dedicated constraint programming solvers / high level modelling languages for these kinds of constraint-y combinatorial optimisation problemse.g. https://www.minizinc.org/ offers a high level modelling language that can target a few different solver backendsmight be pretty good results to completely ignore writing a custom algorithm and drop in an existing industrial-grade constraint programming solver, model your procgen problem using a high level language, and use the existing solver to find you random solutions (or exhaustively enumerate them). then more time to iterate on changing the problem definition to produce more interesting maps rather than getting bogged down writing a solver.
