Iterative Partial Match (IPM) vs Wave Function Collapse (WFC) for procedural content generation.

WARNING: It has come to my attention that the particular implementation of WFC that I tested seems to have some issues. In particular it sometimes does not finish where other implementation do finish, and it may also as a result have slower runtime per completion. I need to redo this entire comparison in a follow-up post.

WFC is handy for quickly generating believable levels and other content in games, but it does have some limitations. My new algorithm, IPM, provides a different trade off and succeeds in some areas where WFC does not.

Generally speaking. WFC output looks "clean" and IPM output looks "organic". That can be good or bad depending on the situation.

On hard tile sets (which are hard either because there are many tiles, few legal ways for tiles to match eachother or because tiles are very large) WFC frequently failes to generate any output or will generate output that is repetitive (because it can only make legal matches of a small subset of the difficult tiles). So for these difficult situations WFC is slower, may not work at all, or the output may be unusable.

WFC advantages:

• 100% accurately honors input tiles. ✅
• Preserves alignment, repeating pattern output looks "correct". ✅
• Preserves existing navigability of input tiles. ✅
• Preserves tile edge matches, allowing "chunky" tile artifacts in game to mesh properly. ✅
• Fast for simple tiles. ✅
• Generates creative combinations and output within the tile constraints. ✅

WFC disadvantages (take with a grain of salt, need to retest with official implementation):

• Frequently fails for larger tile sizes. ❌
• Frequently fails for complex tiles. ❌
• Frequently fails on large output sizes. ❌
• Much slower for complex tiles. ❌
• Tends to overuse the "easy" tiles within complex tile sets, creating repetitive output. ❌

IPM advantages:

• Works with any tile set. ✅
• Works with any tile size. ✅
• Works with any output size. ✅
• Fast for small/simple inputs/outputs. ✅
• Much faster than WFC for large/complex inputs/outputs. ✅
• Generates creative combinations and output within the tile constraints. ✅
• Maintains high pixel variety, tile variety and reasonably high tile match accuracy. ✅

IPM disadvantages:

• Does not 100% match input tiles. ❌
• Does not preserve alignment, repeating pattern output can look "wrong". ❌
• Only partially preserves existing navigability of input tiles. ❌
• Does not preserves tile edge matches, "chunky" tile artifacts in game will frequently not mesh properly. ❌

Direct comparisons (take with a grain of salt, need to retest with official implementation)

I'm providing 17 comparisons. 15 are from WFC's samples and 2 are from IPM and try to represent complex world generation.

Image hamlet.png Tile size: 3 Tile rotations: all. Output size: 50 Input tiles wrap around: false Periodic tiles: false Mirror tiles horizontally: false Source: IPM

Average time to get 1 finish: 1720ms. ❌ Finished 25/100 times. ❌ Result is unusable. ❌

Run time: 901ms. ✅ Always finishes. ✅ Result is useable. ✅

Image hamlet8b.png Tile size: 3 Tile rotations: all. Output size: 100 Input tiles wrap around: false Periodic tiles: false Mirror tiles horizontally: false Source: IPM

Average time to get 1 finish: 40898ms. ❌ Finished 11/100 times. ❌ Result is unusable. ❌

Run time: 8384ms. ✅ Always finishes. ✅ Result is useable. ✅

Image Cave.png Tile size: 3 Tile rotations: all. Output size: 50 Input tiles wrap around: false Periodic tiles: false Mirror tiles horizontally: false Source: WFC Samples

Average time to get 1 finish: 82ms. ❌ Finished 33/100 times. ❌ Result is useable. ✅

Run time: 25ms. ✅ Always finishes. ✅ Result is useable. ✅

Image 3Bricks.png Tile size: 3 Tile rotations: none. Output size: 50 Input tiles wrap around: false Periodic tiles: true Mirror tiles horizontally: true Source: WFC Samples

Average time to get 1 finish: 325ms. ❌ Finished 71/100 times. ❌ Consistent alignment looks correct. ✅ Result is useable. ✅

Run time: 288ms. ✅ Always finishes. ✅ Result is unusable. ❌

Image Fabric.png Tile size: 3 Tile rotations: all. Output size: 50 Input tiles wrap around: true Periodic tiles: false Mirror tiles horizontally: false Source: WFC Samples

Finished 0/100 times. ❌ (the official implementation actually works, i need to retest all of this)

Run time: 35ms. ✅ Always finishes. ✅ Maybe usable result, depends on your intention. �

Image Less Rooms.png Tile size: 3 Tile rotations: all. Output size: 50 Input tiles wrap around: true Periodic tiles: false Mirror tiles horizontally: false Source: WFC Samples

Average time to get 1 finish: 38ms. ✅ Finished 97/100 times. ✅ Result is useable. ✅

Run time: 56ms. ❌ Always finishes. ✅ Result is useable. ✅

Image Less Rooms.png Tile size: 4 Tile rotations: all. Output size: 50 Input tiles wrap around: true Periodic tiles: false Mirror tiles horizontally: false Source: WFC Samples

Finished 0/100 times. ❌ (take with a grain of salt, need to retest with official implementation)

Run time: 406ms. ✅ Always finishes. ✅ Result is useable. ✅

Image Maze.png Tile size: 3 Tile rotations: all. Output size: 50 Input tiles wrap around: true Periodic tiles: false Mirror tiles horizontally: false Source: WFC Samples

Average time to get 1 finish 82ms. ❌ Finished 100/100 times. ✅ Result is useable. ✅

Run time: 33ms. ✅ Always finishes. ✅ Result is useable. ✅

Image Skew 2.png Tile size: 3 Tile rotations: all. Output size: 50 Input tiles wrap around: true Periodic tiles: false Mirror tiles horizontally: false Source: WFC Samples

Average time to get 1 finish 54ms. ❌ Finished 49/100 times. ❌ Result is useable. ✅

Run time: 41ms. ✅ Always finishes. ✅ Result is useable. ✅

Image Skew 2.png Tile size: 4 Tile rotations: all. Output size: 50 Input tiles wrap around: true Periodic tiles: false Mirror tiles horizontally: false Source: WFC Samples

Average time to get 1 finish 4286ms. ❌ Finished 1/100 times. ❌ Maybe usable result, depends on your intention. �

Run time: 214ms. ✅ Always finishes. ✅ Result is useable. ✅

Image Colored City.png Tile size: 3 Tile rotations: all. Output size: 50 Input tiles wrap around: true Periodic tiles: false Mirror tiles horizontally: false Source: WFC Samples

Average time to get 1 finish 34ms. ✅ Finished 76/100 times. ❌ Result is useable (a bit too simplistic to me). ✅

Run time: 99ms. ❌ Always finishes. ✅ Maybe usable result, depends on your intention. �

Image Platformer.png Tile size: 3 Tile rotations: none. Output size: 50 Input tiles wrap around: true Periodic tiles: false Mirror tiles horizontally: true Ground: -1 Source: WFC Samples

Average time to get 1 finish 36ms. ✅ Finished 100/100 times. ✅ Result is useable (a bit too simplistic to me). ✅

Run time: 66ms. ❌ Always finishes. ✅ Result is useable. ✅

Image Simple Knot.png Tile size: 3 Tile rotations: all. Output size: 50 Input tiles wrap around: true Periodic tiles: true Mirror tiles horizontally: false Source: WFC Samples

Average time to get 1 finish 28ms. ✅ Finished 86/100 times. ❌ Result is useable. ✅

Run time: 33ms. ❌ Always finishes. ✅ Maybe usable result, depends on your intention. �

Image Simple Knot.png Tile size: 3 Tile rotations: all. Output size: 50 Input tiles wrap around: true Periodic tiles: false Mirror tiles horizontally: false Source: WFC Samples

Finished 0/100 times. ❌ (the official implementation actually works, i need to retest all of this)

Run time: 36ms. ✅ Always finishes. ✅ Maybe usable result, depends on your intention. �

Image Water.png Tile size: 3 Tile rotations: none. Output size: 50 Input tiles wrap around: true Periodic tiles: true Mirror tiles horizontally: true Source: WFC Samples

Average time to get 1 finish 4ms. ✅ Finished 98/100 times. ✅ Result is useable. ✅

Run time: 11ms. ❌ Always finishes. ✅ Result is useable. ✅

Image Lake.png Tile size: 3 Tile rotations: all. Output size: 50 Input tiles wrap around: true Periodic tiles: false Mirror tiles horizontally: false Source: WFC Samples

Average time to get 1 finish 134ms. ✅ Finished 99/100 times. ✅ Result is useable. ✅

Run time: 179ms. ❌ Always finishes. ✅ Result is useable. ✅

Image Chess.png Tile size: 2 Tile rotations: none. Output size: 50 Input tiles wrap around: false Periodic tiles: true Mirror tiles horizontally: false Source: WFC Samples

Finished 0/100 times. ❌ (the official implementation actually works, i need to retest all of this)

Run time: 6ms. ✅ Always finishes. ✅ Result is useable. ✅

IPM makes possible expansive and rich generation from example images.