1
\$\begingroup\$

I've been looking into the Wave Function Collapse algorithm and was wondering if there is a way to make it (appear) deterministic regardless of starting position.

I can see how this is trivial if the starting position remains the same. We can simply always collapse the tile with the lowest entropy and use a seeded pseudo random number generator or a noise function to decide which is next whenever there isn't a clear winner.

Now what would be the best solution if I wanted to procedurally generate a world around the player? Say I generate the world in chunks. If a player moves far enough away distant chunks get unloaded and new chunks are generated. This works perfectly fine until the player starts to backtrack. Since tiles depend on their neighbors, a revisited chunk might very well look completely different if approach from a different direction.

I can think of two possible solutions:

a) Always generate the world from a set starting position.

This doesn't seem feasible in big worlds, as it would require more resources the further away from the starting position the player is.

b) Only generate chunks once and then save them.

I don't really like this approach, because it could potentially require a lot of disk space. It's also not really deterministic, because the order in which the player explores the world would still influence what individual chunks look like.

Is there a solution I'm overlooking or is this simply not possible because of how the algorithm works? Keep in mind that I don't care if the algorithm itself is actually deterministic regardless of starting position. The result just has to appear that way, so that already visited chunks can be recreated unchanged.

\$\endgroup\$
1
\$\begingroup\$

One solution is to decouple each chunk from its neighbours.

Let's suppose you have nxn chunks, with a 1-tile wide border strip between them, forming a grid lattice.

We'll generate the corners of this grid first, then use the neighbouring corner information to generate the border edges, then use the completed border frame to fill the chunk.

So, starting with the corners. You know you have a corner at every pair (i * (n+1), j * (n+1)) where i and j are integers.

Run this coordinate through a hash function, and use the resulting scrambled bits to select a tile to place here. You can also fold your world seed into the hash to get different corner patterns for different seeds.

This way, the tile selected at each corner depends only on its position and the world seed, not its neighbours or the order in which they were generated. You can use other generation strategies here too, say if you want to create large scale structure to your world, you could sample a noise function at each corner to decide whether it's sea or lowland or mountain, rather than selecting them in an uncorrelated random fashion.

So, we now have the 4 corners of the chunk we want to generate picked out. Next we generate the edges.

First, seed a random number generator with the coordinates of the middle tile in this edge (and your world seed). We'll use that for all the random choices ahead, so they depend only on the edge's position in the grid, not the history of what you generated before.

Take the 1 x (n+2) rectangle of tiles spanning from one corner to its next neighbour, and run a modified wave function collapse on that strip. This modified version will match only neighbours to the left and right, and ignore neighbours above and below (or vice versa when generating the vertical edges).

You might need to constrain the tiles you can select at/near the corners just to make sure you can't create a situation that's impossible to fill in later, like....

A     B

C     ?

where A is the corner of a chunk, A & B are valid neighbours, A & C are valid neighbours, but no tile exists that can match with a B above and a C to the left. If your tileset is reasonably permissive then this situation shouldn't require major constraints to avoid.

After repeating this process for each edge surrounding our chunk, we have neighbours on all sides, and we're ready to fill it in.

Again we'll spin up a seeded random number generator with the coordinates of the middle of this chunk, so we don't leak previous generator state into our subsequent choices. Then we'll run the big wave function collapse pass on this inner square, using the border of already-collapsed neighbours we have on all four sides.

Since the interior depends only on the edges, and the edges depend only on the corners, and the corners depend only on position, we'll generate the same corners/edges/chunk interior in a given location, no matter what order we generated them in.

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