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

71–80 of 92 posts

Re: Building a Procedural Hex Map with Wave Function Collapse

#71

Post by vintermann »

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

Re: Building a Procedural Hex Map with Wave Function Collapse

#72

Post by zem »

the 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

Re: Building a Procedural Hex Map with Wave Function Collapse

#73

Post by netdevphoenix »

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

Re: Building a Procedural Hex Map with Wave Function Collapse

#74

Post by ant28 »

iamjs wrote: post #47
hananova wrote: post #46

[flagged]

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

[dead]

Re: Building a Procedural Hex Map with Wave Function Collapse

#75

Post by orbital-decay »

vintermann wrote: post #71

It'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. B…

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

Re: Building a Procedural Hex Map with Wave Function Collapse

#76

Post by antonvs »

vintermann wrote: post #71

It'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. B…

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

Re: Building a Procedural Hex Map with Wave Function Collapse

#77

Post by VorpalWay »

vintermann wrote: post #71

It'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. B…

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

Re: Building a Procedural Hex Map with Wave Function Collapse

#78

Post by jcalx »

linkdd wrote: post #57

This is not Wave Function Collapse. This is a constraint solver. The goal of the original algorithm ( 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).

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

[1] https://github.com/mxgmn/WaveFunctionCollapse

Re: Building a Procedural Hex Map with Wave Function Collapse

#79

Post by bhaak »

vintermann wrote: post #71

It'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. B…

That's a general problem with procedurally generated content.

Remember that wave function collapse focuses on local optimization. The algorithm can’t take a step back and look at the whole map. That’s why you won’t get a sensible road network. Rivers are only slightly better when the follow height gradients.

What you can do, and this is also a general advice for procgen, is to mix in some templates before WCF runs. Often, a bit of post-processing is needed as well.

The templates can be hand-designed, or generated with simpler procgen code. Place a few towns on the map, connect them with roads, and then let WFC fill in the gaps to create a more interesting landscape.

Re: Building a Procedural Hex Map with Wave Function Collapse

#80

Post by danbruc »

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

Post reply on HN