Wave-Function-Collapse
Straight out of quantum mechanics, Wave Function Collapse (WFC) is an algorithm for procedural generation of images. This repository features two approaches to the WFC: the Tiled Model (Coding Challenge 171) and the Overlapping Model (Coding Challenge #186). Both implementations are available in JavaScript (p5.js) and ported to Processing (Java).
Coding Challenges
- Coding Challenge #171: Wave Function Collapse
- Coding Challenge #186: WFC Overlapping Model (Available now exclusively on Nebula!)
Archived Raw Footage
- 🔴 Wave Function Collapse Tiled Model Live Stream #1
- 🔴 Wave Function Collapse Tiled Model Live Stream #2
- 🔴 Wave Function Collapse Tiled Model Live Stream #3
- 🔴 Wave Function Collapse Overlapping Model Live Stream #1
- 🔴 Wave Function Collapse Overlapping Model Live Stream #2
Overview
Wave Function Collapse is a constraint-satisfaction algorithm inspired by quantum mechanics. At a high level, you have:
- Tiles (or “patterns”) that can appear in each cell.
- Adjacency rules describing which tiles can appear next to each other.
- Entropy that helps decide which cell to collapse (choose a tile for) next.
- Propagation to eliminate invalid tiles from neighbors as constraints tighten.
Completed
- Implementation of Tile Model (Challenge 171)
- Implementation of Overlapping Model (Challenge 186)
- Processing (Java) ports for both models
Corrections / Additional Features
- Additional edge cases for tiles 4 and 5 (Tiled Model).
- Computed Property Names (Tiled Model) Issue #35
- Backtracking for conflict resolution.
Community Contributions and Improvements
- TileGrid Helper Class by @jonnytest1 A generic grid layout approach using p5.js vectors, making it easier to unify directional logic and reference valid neighboring positions.
- Grid Update Optimization: Pull Request #40 introduces a more efficient method for updating grid cells by propagating changes only to affected cells, which improves performance and accuracy. The drawing process is also optimized, allowing multiple updates per tick, speeding up the overall process.
- Using Piskel to create a source image
- Highly optimized version supporting both single-image and pre-tiled source images A detailed write-up of how the changes were done and why can be found in its own readme here
- An optimised overlaping model using queues (instead of recurcion) and backtracking to avoid paradoxes. Version @alin256. The version also adds some GUI improvements.