1
\$\begingroup\$

I am discovering the techniques of procedural generation. I struggle understanding on the usage of those two techniques:

  • Wave Function Collapse
  • Marching Squares

As I understand, both can be used to populate neighbourhood of a tile based on rules.

In the case of a game map editor where a user can "paint" a dungeon. When would you use one versus the other?

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

Conventional auto-tiling strategies aim to simplify the selection of individual tiles where two different terrain types adjoin, using rules that are local and deterministic:

  • Local: only the tiles/edges/corners immediately adjacent to the one being selected can affect the decision, so the features it controls are small and don't have much internal structure.

  • Deterministic: the same choice is made every time, predictably. If you have three surrounding grass tiles and one dirt, then the only tile that fits such a gap is the dirt-grass-dead-end, which is guaranteed to be selected. So it doesn't surprise or create/invent/propose anything "creative" on its own.

    (This one can be bent sometimes: if we have two or more functionally-equivalent variants - like two grasses that can cover the same shapes, with slightly different weed patterns, the auto-tiler might include a coin flip to select one of the two randomly, to break up the obvious repetition.)

This means the level designer still has to manually choose where they want each terrain type, and what shapes it should form. "I want a 2-tile wide dirt road here, that turns 90 degrees left here, at a 5-tile wide river of water, and..."

The auto-tiling logic just replaces the tedium of selecting the grass-dirt 90-degree-left-outside-corner tile or the grass-dirt-90-degree-left-inside-corner tile or the grass-dirt-straight-vertical tile, letting the designer freely paint their intended terrain layout without stopping to swap selected tiles constantly.

These rules (of which there are many variants) are very simple and predictable to use, reason about, and implement - typically using simple bitmasking and indexing. For this reason they're pretty ubiquitous in tile-based game tools as a standard feature.

In these cases, the algorithm doesn't really "invent" anything creative itself. It just executes the designer's stated intention, within the limits of the tiles it has to work with.


Wave Function Collapse is a much newer algorithm, that's still finding novel and experimental uses. It allows you to fill in large chunks of tiles, even whole maps, using probability weights inspired by quantum states. That means it's:

  • Non-Local: the state of a tile at one side of the map could influence the state of a tile at the far end of the map. Say you paint a river mouth at coastline, and WFC fills-in a path for that river all the way to the opposite edge of the map.

  • Non-Deterministic/Unpredictable: the set of possible ways to fill in the space might be very large indeed, and we often want to use WFC to explore those options, by letting it run with different seeds and produce different outcomes. The choices it makes can sometimes be very surprising, or look similar to creative problem-solving.

Workflows for interacting with wave function collapse systems are not as standardized, but they often involve a degree of "co-creation": the level designer sets up the tiles for the parts of the level they care about, "I need an entrance here and a treasure room there," and then delegates to the algorithm the responsibility to propose one or more different ways to join these elements and fill in the connecting areas, from which they then choose the one they like, or modify it and re-run the algorithm to adapt to their change.

WFC can even run without a designer in the loop at runtime, drawing on a set of examples and constraints provided in advance to procedurally generate new levels, as seen in the game Bad North for example.

So the two approaches - although they both deal with automatic tile selection - serve very different roles in level creation. Auto-tiling is more like a convenient paintbrush, that flows smoothly and leaves an attractive edge as the artist paints on their canvas. Wave function collapse is more like an artist's assistant, to whom the creator can delegate chunks of their workload, while having slightly less direct control of the precise outcome.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for your time and this solid answer. \$\endgroup\$ – dagatsoin May 14 '20 at 13:59
  • \$\begingroup\$ If I observe the WFC solver. When it times to collapse a tile. Can we say it acts as a conventional auto tiling. Aka, choose the tile to store in function of local neighbourhood? \$\endgroup\$ – dagatsoin May 14 '20 at 14:06
  • \$\begingroup\$ Not quite. Each tile has a probability distribution over all of the possible tiles. When you collapse that tile, it chooses one specific tile using a weighted random selection over that probability distribution. But that information itself was populated in a non-local way. Say your tileset only contains transitions from dirt to grass left-to-right, not right-to-left. Whether grass has a non-zero probability for this tile might have been influenced by a dirt tile that's been placed on the far right side of the map, or a grass tile on the far left side - not just its immediate neighbours. \$\endgroup\$ – DMGregory May 14 '20 at 14:48

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.