7 ms·
Building a Procedural Hex Map with Wave Function Collapse
- MattDamonSpace 7mo agoGorgeous
- gedy 7mo agoReal engineering skills, I love it.
- contextfree 7mo ago"Stop playing your AI garbage and get to bed!" "Mooooom! It's not AI garbage, it's classical procedurally generated content!"
- xipho 7mo agoInspirational stuff, with lots of great references to the OGs at the bottom, and source available. Now can it be merged with the look/feel of https://heredragonsabound.blogspot.com/ https://heredragonsabound.blogspot.com/. ;)
- verdverm 7mo agoRelated (?) has anyone else been following the Hytale Worldgen v2? They've built a visual node editor so anyone can create biomes, structures, or complete worlds. I believe there is a competition going on right now. They are essentially making the entire game based on similar concepts and then using them to develop their core content. Simon is an inspiration and has said they won't be taking investor money so they can stay true to the users and creators.
- nickandbro 7mo agoThis looks amazing man, seriously good job with this.
- jesse__ 7mo agoLove this. As an aside, if the author reads this, did you consider using bitfields for the superposition state (ie, what options are available for a tile)? I did a wfc implementation a while back and moved to bitfields after a while.. the speedup was incredible. It became faster to just recompute a chunk from scratch than backtrack because the inner loop was nearly completely branchless. I think my chunks were 100 tiles cubed or something.
- zimpenfish 7mo ago> I did a wfc implementation a while back and moved to bitfields after a while.. the speedup was incredible. Yeah, my WFC bot (which happens to generate Carcassonne maps in an amusing coincidence) eventually ended up using https://github.com/bits-and-blooms/bitset https://github.com/bits-and-blooms/bitset which improved things hugely. > It became faster to just recompute a chunk from scratch Kinda what mine does - every now and again[0] it stacks the current state and if it gets stuck, just pops the last one and continues from there. [0] Just checked and it's every `tileCount / 20` iterations, hilariously in a variable named `tenper`. I hate past me.
- jesse__ 7mo agoI read an 'i hate myself' post one time where someone encountered a variable named leghands. Obviously, it had once read legendHandles, and had since been helpfully shortened by the author.
- bobek 7mo agoMade me smile. Thank you!
- moi2388 7mo agoThis entire article reads like it was fully written by AI unfortunately
- imadr 7mo agoIs it the em dashes? I didn't get the feeling it was AI generated at all
- zparky 7mo agoIt's current year, of course they used AI to help [0], and it does feel like the article was AI assited. "This map isn't flat — it has 5 levels of elevation." "The ocean isn't just a blue plane — it has animated caustic sparkles" "The fundamental issue:" and "The key constraint:" I still enjoyed the article. [0] https://github.com/felixturner/hex-map-wfc/commit/1679be https://github.com/felixturner/hex-map-wfc/commit/1679be
- socalgal2 7mo agoAt what point is this style going to become human style? Kids use LLMs to learn, pick up their patterns, repeat them.
- _bent 7mo agojust a quick example from the backtracking section: "Here's the dirty secret of WFC: it fails. A lot. You make a series of random choices, propagate constraints, and eventually back yourself into a corner where some cell has zero valid options left. Congratulations, the puzzle is unsolvable."
- BretonForearm 7mo agoBesides what others said. The "The Numbers" section is a dead giveaway. LLM likes to generate random summary stats in a metrics grid without any prompting.
- ArcaneMoose 7mo agoBeautiful work!
- tomtomistaken 7mo agoReminds me of Dorfromantik[0]. [0] https://store.steampowered.com/app/1455840/Dorfromantik/ https://store.steampowered.com/app/1455840/Dorfromantik/
- bhaak 7mo agoWhich is based on the board game of the same name. https://boardgamegeek.com/boardgame/370591/dorfromantik-the-board-game https://boardgamegeek.com/boardgame/370591/dorfromantik-the-...
- the_mitsuhiko 7mo agoThe other way around.
- bhaak 7mo agoOh, wow, TIL. Both were released in 2022 but the video game already had an alpha release in 2021.
- kevinsync 7mo agoSuper awesome, love the tilt-shift camera effect! I was also wishing I could zoom in to human size and run around HAHAHA
- matthewfcarlson 7mo agoI started on a simple coop top-down pirate game yesterday when this popped up. I will probably switch the map generation to be using something like this tbh
- schemathings 7mo agoOP is probably familiar but this site has a lot of good examples of hex math with code examples - https://www.redblobgames.com/grids/hexagons/ https://www.redblobgames.com/grids/hexagons/
- zparky 7mo agoThey link to that site in the post
- schemathings 7mo agoAh I read it but missed it!
- behnam_amiri 7mo agoThis is cool. Curious if you plan on keep it as a map generator or turn it into something more interactive too.
- rhdunn 7mo agoOskar Stålberg used wave function collapse for various games, including Townscaper. He talks about it here: https://www.youtube.com/watch?v=Uxeo9c-PX-w&pp=ygUhdG93bnNjYXBlciB3YXZlIGZ1bmN0aW9uIGNvbGxhcHNl0gcJCa4KAYcqIYzv https://www.youtube.com/watch?v=Uxeo9c-PX-w&pp=ygUhdG93bnNjY... (SGC21- Oskar Stålberg - Beyond Townscapers).
- jcalx 7mo agoReminds 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/ https://catlikecoding.com/unity/tutorials/hex-map/
- meander_water 7mo agoThis is an amazing resource, thanks for sharing
- jcul 7mo agoThat "Carcassonne" game sounds really fun. I'd never heard of it before.
- porphyra 7mo agoThe 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] with dancing links, which is a special kind of backtracking. Algorithm X should, in theory, be able to solve the border region described in the article's "Layer 2" with a higher success rate as opposed to 86%. 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 https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
- shoo 7mo agothere's also a bunch of dedicated constraint programming solvers / high level modelling languages for these kinds of constraint-y combinatorial optimisation problems e.g. https://www.minizinc.org/ https://www.minizinc.org/ offers a high level modelling language that can target a few different solver backends might 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.
- porphyra 7mo agoYeah, you can also use Clingo [0] which is pretty popular and people have tried it specifically with WFC content generation [1]. You can even run it in the browser easily [2]. [0] https://potassco.org/clingo/ https://potassco.org/clingo/ [1] https://adamsmith.as/papers/tog-wfc.pdf https://adamsmith.as/papers/tog-wfc.pdf [2] https://potassco.org/clingo/run/ https://potassco.org/clingo/run/
- felixturner 7mo agoThanks for the feedback. Feel free to drop a PR :)
- westurner 7mo agoModel synthesis: https://en.wikipedia.org/wiki/Model_synthesis https://en.wikipedia.org/wiki/Model_synthesis : > Model synthesis (also wave function collapse or 'wfc') is a family of constraint-solving algorithms commonly used in procedural generation, especially in the video game industry. > [...] One of the differences between Merrell & Gumin's implementation and 'wave function collapse' lies in the decision of which cell to 'collapse' next. Merrell's implementation uses a scanline approach, whereas Gumin's always selects as next cell the one with the lowest number of possible outcomes And then `## Developments` mentions: "Hierarchical semantic wave function collapse" (2023) Alaska, Bidarra: .. citations of: https://scholar.google.com/scholar?cites=16710197436116876139&as_sdt=5,43&sciodt=0,43&hl=en https://scholar.google.com/scholar?cites=1671019743611687613...
- ionwake 7mo agoThis is absolutely beautiful, I could even tell I was going to like it from the title. Good job.
- btbuildem 7mo agoI really like the part where you can "reroll" sub-areas of each tile. Consider exposing some of the weight knobs (eg, I'd like to tweak it to favour mountainous terrain)!
- OscarCunningham 7mo agoIt seems like a lot of the difficulty is in finding arrangements that satisfy constraints. I wonder if an alternative approach would be to use a SAT solver. I suppose the problem with that approach would be that the solver might always find an 'easy' solution that doesn't look random. I know that some SAT solvers let you randomly assign the initial assignments of the variables, but that doesn't mean you get a random solution. Has anyone tried a similar approach?
- teamonkey 7mo agoI think the problem with SAT solvers is that they’re complicated, in terms of computation and also how easy it is to understand by someone who didn’t study formal methods. WFC is brute-force-simple, but because it’s simple it’s quite computationally inexpensive (unless it hits a lot of dead-ends) and I wouldn’t be surprised if it could often find an adequate solution quicker than a SAT solver. At least for games, where a result doesn’t need to be perfect, just good enough.
- gmueckl 7mo agoLess than perfect solutions can make certain types of video games more interesting because the domain of potential results is generally larger and can include many more variations of challenges to the player.
- jbmsf 7mo agoYears 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.
- z3t4 7mo ago"WebGPU is not available on your device or browser.". Other 3d demos works fine though. Tried Firefox and Opera on mobile.
- socalgal2 7mo agowhat's your device? guessing android? new? old? Has Firefox shipped WebGPU on Android? MDN says no, though it does claim Opera has.
- foota 7mo agoI realize this comes up every so often, but I was just looking at this the other day :) A related idea is wang tiles, which are a way to construct a tileset such that you can place them without ever running into a contradiction.
- MattRix 7mo agoFun fact: because WFC is graph-based, you can do stuff like creating a graph where it uses time as a dimension, so you can create animations that “wrap” in time. In this rabbit example I made 8 years ago, the WFC solver ensures that the animation must loop, which means you will always end up with an equal number of births and deaths. https://xcancel.com/MattRix/status/979020989181890560 https://xcancel.com/MattRix/status/979020989181890560
- llm_nerd 7mo agoThis is fun and neat, and looks fantastic, but the generated maps are basically nonsensical, aren't they? Landmasses and waterways and roads and buildings and forests and so on that don't make any logical sense for their placement. I say this having had a couple of fun "hex-based strategy game hobby projects" over the years (sidenote -- trying to cover a sphere in hexes is actually a non-trivial matter). Invariably I ended up with "to make a map from scratch, first you create the universe" where I'd go through all of the ages, compute waterflows and precipitation, and on and on. Maybe I made the requirements too unreasonable and that's precisely why I never yielded a working game from it.
- zimpenfish 7mo ago> This is fun and neat, and looks fantastic, but the generated maps are basically nonsensical, aren't they? WFC lets you address that though with extra constraints. e.g. my bot today generated a church inside a river loop[0] - completely useless! But I could add a rule that says "if you place the church-above-river tile, the tile above that cannot be anything horizontally blocking" (obviously after tagging any relevant tiles as "horizontally blocking" in the tileset) and that would prevent "church in a river loop" situations. (I've already been working on some extra rules because, e.g., I don't like the one-edge-castle-wall tiles being placed next to each other - you get tiny pasty shaped castles and I hate them.) [0] https://social.browser.org/fileserver/01E5NFWNPGZWNJ0DS1WE88GBAS/attachment/original/01KK9VY282S25F7EFS0M53J06B.jpeg https://social.browser.org/fileserver/01E5NFWNPGZWNJ0DS1WE88... - bottom 3 rows, just past halfway across
- socalgal2 7mo agonot trying to be contrarian but a church inside a river loop sounds like a super sacred church that requires a pilgrimage to visit. That said, there's an Apple TV video of a castle on an island where my first thought was "why does this exist?" https://vimeo.com/657386068 https://vimeo.com/657386068
- zimpenfish 7mo ago> "why does this exist?" "Though hidden from the sea, the castle controls access to Loch Shiel" says Wikipedia. Which is a sensible thing for a castle to do back in the olden times. Plus it's a tidal island - you can just walk across. Don't even need a drawbridge (although I guess that makes defending attacks from inland a bit tricky.) https://en.wikipedia.org/wiki/Castle_Tioram https://en.wikipedia.org/wiki/Castle_Tioram
- profer602 7mo ago[flagged]
- djray 7mo agoThe demo runs at 5 FPS on my laptop (11th gen Core i5 and Iris Xe graphics, Chrome Latest as the browser, with the GPU being the bottleneck). I was hoping for something rather more efficient given the write-up saying it ran at 60 fps on mobile. The maps are pretty, but the per-tile build constraints of the WFC build approach means that pretty unnatural generations end up happening because non-local influence is difficult to take into account. I think this may be OK for games where you discover tiles one at a time, but for a full map generator it's not great, and better solutions exist. Red Blob Games did a writeup of a noise-based method which looks superior imo. You can use moisture-tracking approaches for rivers, lay roads, bridges and other artificial elements in a separate pass, and it will likely end up faster and more robust. I think WFC is an interesting programming problem, though, so it was likely fun to implement. Nonetheless, this was an excellent write-up and impressive demo.
- refulgentis 7mo agoI’m stunned - works fine on mobile for me. I’m curious how you determine FPS, I was hoping the site had an indicator, but either I’m missing it, or it’s Chrome Dev Tools (and thus it’s presumably impossible for me to get on iOS/Android)
- socalgal2 7mo agoyour on windows or linux or ... maybe your on CPU rasterization?
- rafram 7mo agoIt runs quite smoothly on my iPhone 15, so I think there’s something wrong with your graphics setup.
- wmil 7mo agoYou should be able to use chrome://gpu/ or about:gpu to tell if Chrome is doing software rendering.
- djray 7mo agoI said in my comment that it was GPU bound. Task Manager was reporting 100% GPU usage from the browser, which went down to 0% after closing the tab. It looks to be that the demo has been fixed since I initially looked. Testing today showed much improved performance.
- hananova 7mo ago[flagged]
- iamjs 7mo agoThis sentiment is quickly becoming the most annoying low-effort comment on HN. If you don't want to read it, don't read it. If something about the writing offends you, then describe it, so we can talk about it.
- _bent 7mo agoIt's extremely distracting to read heavily ai edited texts like these because every single aism throws me a curveball. It doesn't help that the figures of speech ai loves to use are those that stress things and create tension and drama. And it uses one in every single paragraph, rendering the text into the literal equivalent of a deepfried faux HDR jpg (or a dialogue scene in a Michael Bay movie). And beyond those practical concerns it's just hard to gauge how much the author truly understands of what he's writing about (and transitively if it's worth to continue reading)
- ant28 7mo ago[dead]
- hananova 7mo agoI’m pretty sure AI-written comments hold that crown. I have described what bothers me about the writing, and also a proposed solution. Post the prompt, not the slop.
- spopejoy 7mo ago> I have described what bothers me about the writing No you haven't, you've made an unprovable claim about how the writing was accomplished without pointing out a single feature of the writing itself. Too long? OK, but homebrew gamedev articles often are. Skimming was a good skill before AI and still is. Bad writing? Again -- hobbyist posts don't exactly win awards. I suspected possibly some AI myself but not to the extent you're baselessly asserting: I really doubt there was a single prompt in any case. The article is structured like any other. If it were content-free clickbait or something, the complaint would hold water. As it is this is a reasonably interesting article that has generated a large and fun discussion on HN, so even if you _could_ prove AI use, so what?
- hermitcrab 7mo agoThe maps look beautiful.
- deterministic 7mo agoExcellent beautiful work. And a great write up. Thanks!
- juleiie 7mo agoInteresting. In my little project I only need one generation of hex tiled terrain but based on certain lore and vision for thousands of objects with different lore. I tell LLM to research the lore and paint the terrain using json in chunks. Some results are shit, some results are great. Still, it would be impossible manually. I can always do another pass for unsatisfying results with different prompt engineering.
- linkdd 7mo agoThis is not Wave Function Collapse. This is a constraint solver. The goal of the original algorithm ( https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse ) is to infer the constraints from a sample, and then run a constraint solver. Hard-coding the constraints skips the whole point of the algorithm (which is also badly named by the way).
- nextaccountic 7mo agoNote that the original algorithm is model synthesis. WFC is just a minor tweak on it
- jcalx 7mo agoI didn't want to nitpick terminology, but yes, the tile-placement algorithm here is just a way of solving constraint satisfaction problems with DFS using a "minimum remaining values" heuristic [0]. The original use case for generating textures [1] is different in that the constraints are implicit in the input bitmap, but this project is a more straightforward tile placement with explicit constraints. I think this algorithm is more efficient for generating maps with only local (adjacency) constraints, but setting this up as an integer linear program and plugging it into a constraint solver is more generalizable (say, if you wanted to enforce a constraint that rivers had to flow across the whole map and could not loop). But I agree "wave function collapse" is not really the best name, for two reasons: - the original repository mentions "it doesn't do the actual quantum mechanics, but it was inspired by QM", but it implies something QM-related. - as an ORIE major in college that loved optimization, I think constraint satisfaction problems are really cool and actually somewhat approachable! So calling the heuristic something else like "wave function collapse" might limit people from finding previous work and known improvements (e.g. forward checking). [0] https://www.cs.cornell.edu/courses/cs4700/2011fa/lectures/05_CSP.pdf https://www.cs.cornell.edu/courses/cs4700/2011fa/lectures/05... [1] https://github.com/mxgmn/WaveFunctionCollapse https://github.com/mxgmn/WaveFunctionCollapse
- swiftcoder 7mo agoColloquially this is what gamedevs mean when they refer to WaveFunctionCollapse (though the constraints may or may not be inferred from tiles or 3D models, depending on the implementation). It may not match the academic terminology exactly
- andrewingram 7mo agoI used something similar for my Super Mario Maker 2 level viewer (eg https://www.smm2-viewer.com/courses/1HH-CJ8-KYF https://www.smm2-viewer.com/courses/1HH-CJ8-KYF) In the level data, the start/goal tiles (approx 10x10 blocks of solid ground under the player and goal) and slopes aren't represented by their tile offset in the level data -- whilst all other "ground" tiles are. Instead, for slopes you're only told the start and end coordinates, and they often overlap. So to render the slopes correctly I had to work out all the rules for which tiles were allowed next to each other, and solve some ambiguity rules -- I figured out that shallow slopes take precedence over steep ones. Eventually I cracked it, but it took quite a week or so of iteration to figure it out.
- coolcoder9520 7mo ago[flagged]
- RiDiracTid 7mo agoAI comment
- vintermann 7mo agoIt's beautiful. But also pretty unsatisfying in a way. Roads don't make sense. Rivers barely make sense. There's no higher-scale structure - the reason why most games with incremental procedural generation usually feel stale after a while, and always static. Every planet is different, yet feels the same. (Dwarf Fortress is the one procedural game I know - besides maybe its more faithful clones - which isn't static. But the procedural generation there is also mostly not incremental, it generates the whole world beforehand and only some of the fill-in details are incrementally generated). The holy grail has to be a graph-based refinement/embellishment system, where it generates just the nodes, temporally and spatially, which matter for the situation the player is in.
- orbital-decay 7mo agoSituation-adaptive generation also gets predictable and boring once you can read it easily. Classic procedural generation is good for perceived variety and breaking small patterns, but it doesn't introduce novelty on its own, it just shifts it from the asset design to the algorithm design.
- antonvs 7mo ago> Roads don't make sense. Rivers barely make sense. There's no higher-scale structure It feels a bit like the graphical equivalent of Markov chain text generation.
- VorpalWay 7mo agoI think it helps in Dwarf Fortress that you are not really exploring the world (well, unless you play adventurer mode, but that seems far less popular), you pick a site and settle and start building. You see far less of the world than in something like Minecraft. Yes, you get to see more of the world over multiple runs, but it is still far more limited. Rimworld is interesting here, as it is what I would consider a DF style game. And I would have said the same for it, except that the latest expansion (Oddessy) added space ships that you can build, and fly to another area. While fun this has made the procedural generation show its weaknesses. (That said, DF world gen is top notch, but probably not quite as good as it may seem due to what I mentioned.)
- 7mo ago
- zem 7mo agothe game dorfromantik is a fun twist on this idea - the game generates random tiles and you have to fit them in with matching edges. you produce some beautiful pastoral landscapes while playing a pretty fun and challenging game. https://en.wikipedia.org/wiki/Dorfromantik https://en.wikipedia.org/wiki/Dorfromantik
- netdevphoenix 7mo agoIs there anything special about using the wave function collapse algorithm in this particular context? I feel this is like when experimental musician make music with plant electrical signals, wind flow or sea wave movements, etc. The idea sounds great but the execution not so much.
- danbruc 7mo agoHex math is weird. Since there are 6 directions instead of 4, there's no simple mapping between hex positions and 2D x,y coordinates. There is, a hexagonal grid is isomorphic to a [skewed] rectangular grid, i.e. it can also be indexed with a coordinate pair (u, v). The neighbours are at offsets (+1, 0), (-1, 0), (0, +1), and (0, -1) - just as in a rectangular grid - and the two additional neighbours are at (+1, -1) and (-1, +1). The coordinates in the plane are (x, y) = (√3(u + v/2), 3v/2) or some variation of this, depending on how exactly one lays out the hexagons and picks axes. It is surprisingly hard to find a good illustration for this, or maybe I am using the wrong search terms, but here [1] is the best one I could quickly find. [1] https://www.researchgate.net/figure/Rhomboidal-and-hexagonal-tiling-of-data-in-the-spatial-and-frequency-domains_fig1_268177078 https://www.researchgate.net/figure/Rhomboidal-and-hexagonal...
- swiftcoder 7mo agoAmit has a pretty good overview of the (many) ways to map coordinates to hexes: https://www.redblobgames.com/grids/hexagons/ https://www.redblobgames.com/grids/hexagons/
- danbruc 7mo agoThat is one of the first results I found and it is probably a great resource if you want to dive into the topic, but it also lacks an image of the rectangular - or rhombic - grid on top of the hexagonal tiling which I think is visually much clearer than those interactive maps highlighting only the axes of the cell under the cursor. But I understand why they made the choice, other coordinate systems do not admit the same type of visualization while the interactive maps are universal in that sense.
- mzl 7mo agoAs others have said, this is more of a constraint programming system than Wave Function Collapse. Whatever one wants to call it, I liked it. For guiding the search, you might want to consider search steps that select only one feature, for example that a pair of adjacent tiles should be connected by a road, and just propagate that information. That could be used as a way to guide the search on high-level features first, and then later realize the plans by doing the normal search.
- priowise 7mo ago[dead]