Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building a Procedural Hex Map with Wave Function Collapse

felixturner.github.io

Post reply on HN
Print view View original

41–50 of 92 posts

Re: Building a Procedural Hex Map with Wave Function Collapse

#41

Post by zimpenfish »

jesse__ wrote: post #8

Love 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 ti…

> 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 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.

Re: Building a Procedural Hex Map with Wave Function Collapse

#42

Post by zimpenfish »

llm_nerd wrote: post #40

This 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…

> 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/01E5NFWNPGZWNJ0DS1WE88... - bottom 3 rows, just past halfway across

Re: Building a Procedural Hex Map with Wave Function Collapse

#44

Post by gmueckl »

teamonkey wrote: post #30
OscarCunningham wrote: post #29

It 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…

I 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, whe…

Less 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.

Re: Building a Procedural Hex Map with Wave Function Collapse

#45

Post by djray »

The 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.

Re: Building a Procedural Hex Map with Wave Function Collapse

#48

Post by refulgentis »

djray wrote: post #45

The 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 diffi…

I’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)

Re: Building a Procedural Hex Map with Wave Function Collapse

#50

Post by socalgal2 »

djray wrote: post #45

The 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 diffi…

your on windows or linux or ... maybe your on CPU rasterization?
Post reply on HN