0
\$\begingroup\$

I'm using Wave Function Collapse to generate a tilemap, and I'm trying to come up with a way to maintain a contiguous area during generation. As an example: ensuring all "walkable" tiles are contiguous such that no "walkable" tile is blocked off from another. An acceptable outcome would also be ensuring there is a contiguous path between two (or more) designated tiles. I'm thinking there may be some way to determine how likely any given tile is to bisect a contiguous area and integrate that into the entropy calculation, but I'm not sure how I would determine that.

\$\endgroup\$
2
\$\begingroup\$

This is something that Wave Function Collapse as an algorithm is notoriously bad at doing. Because it's always making local decisions based on immediate neighbours, it's difficult to make any global guarantees.

At the level of individual tile neighbours, the tiles in the middle or at the edge of one giant open area look pretty much the same as the tiles in the middle or at the edge of two small open areas that don't connect together.

Oskar Stålberg talks about how he solved this problem in Bad North about halfway through this video. He associates with each tile some connectivity information about which neighbouring tiles can be walked to from its center point. As new tiles are collapsed, he adds them to a "navigable island" based on these connections to already-collapsed tiles. When choosing which of several tile options to collapse to, he favours options that would expand the navigable island.

This can work, especially for small maps like Bad North's islands that are expected to be mostly walkable, just at different heights, with a possibly serpentine path between them.

But if you want a map where the walkable area is more restricted, you might find this heuristic pushes too hard toward big walkable areas and not enough other stuff. Or, if your generator ever starts to collapse from two separate places (say if you have a map entrance and exit), then this heuristic might not be enough to ensure the two get connected to each other. It might grow a walkable island around each at such different altitudes/materials such that there's no tile that can join them where they meet. There's not much you can do about that kind of contradiction other than restart.

Another approach is to seed your map with a different algorithm that guarantees connectivity, then fill in the rest with WFC.

For example, you could choose a set of points on your map and generate paths between them. You could use say A* with randomized costs so that it takes a more organic wander between them, rather than always a straight line. For each grid cell in the A* paths, mark which neighbouring cells it needs to connect with.

Then run your WFC pass. For each marked cell, exclude from its initial superposition of options any tile that doesn't connect to the neighbours marked in the A* pass. Then proceed with the collapse. You've now guaranteed that any successful collapse from this starting state will have at least the A* paths you chose as walkable connections between your chosen points — though it could also have additional paths beyond these.

You can then forbid selection of walkable tiles for any cell that has other options and is not adjacent to an already collapsed walkable tile, to prevent other islands of walkability from sprouting up randomly, away from the connected network.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.