Onboarding: mxgmn/WaveFunctionCollapse

Generated by RepoPilot · 2026-05-05 · Source

Verdict

WAIT — Single-maintainer risk — review before adopting

• Last commit 6w ago
• 5 active contributors
• Other licensed
• ⚠ Small team — 5 top contributors
• ⚠ Single-maintainer risk — top contributor 93% of commits
• ⚠ Non-standard license (Other) — review terms
• ⚠ No CI workflows detected
• ⚠ No test directory detected

_{Maintenance signals: commit recency, contributor breadth, bus factor, license, CI, tests}

TL;DR

WaveFunctionCollapse is a C# procedural generation library/tool that synthesizes new bitmaps and tilemaps that are locally similar to a single input example image. It uses a constraint propagation algorithm inspired by quantum superposition: each output cell starts in a superposition of all possible NxN patterns found in the input (OverlappingModel.cs) or tile adjacency rules (SimpleTiledModel.cs), then collapses iteratively via lowest-Shannon-entropy observation and propagation until fully determined. Flat single-project structure: Model.cs defines the abstract base (wave array, propagation, entropy), OverlappingModel.cs and SimpleTiledModel.cs are the two concrete algorithm variants, Program.cs is the entry point that reads samples.xml to drive batch generation, and Helper.cs provides bitmap I/O utilities. Sample inputs live in samples/ and configuration is entirely in samples.xml.

Who it's for

Game developers and procedural content researchers who need to generate textures, tilemaps, or level layouts that match the 'feel' of a hand-crafted sample without manually authoring all combinations. Also useful to academics studying constraint satisfaction and procedural generation techniques.

Maturity & risk

The repo is the canonical reference implementation by the original author (mxgmn) and is widely cited (CITATION.cff present), but has minimal CI, no automated test suite, and commit activity has slowed significantly. It is best described as a stable reference implementation rather than an actively maintained production library — suitable as a learning resource or starting point, but not for drop-in production use without forking.

Single-maintainer risk is high — mxgmn is the sole author with no visible co-maintainers or CI pipeline (no .github/workflows directory). There are no unit tests in any of the four core .cs files, so regressions are undetectable without manual runs. The project has no NuGet packaging, so consuming it as a library requires copying source directly.

Active areas of work

Based on the visible repo data there is no active branch, open PR, or milestone activity — the repository appears to be in a maintenance/reference state with no recent feature work visible. The CITATION.cff and FUNDING.yml suggest the author is focused on academic recognition rather than feature development.

Get running

git clone https://github.com/mxgmn/WaveFunctionCollapse.git cd WaveFunctionCollapse

Requires .NET SDK (6+ recommended)

dotnet run

Daily commands: dotnet run

Output PNGs are written to the working directory. Tweak which samples run and their parameters inside samples.xml.

Map of the codebase

• Model.cs — Abstract base class implementing the core WFC algorithm — wave propagation, constraint solving, entropy-based observation, and backtracking — that all concrete models inherit.
• OverlappingModel.cs — Implements the overlapping (bitmap) variant of WFC, extracting NxN patterns from the input sample and encoding adjacency constraints for pixel-level generation.
• SimpleTiledModel.cs — Implements the tile-based variant of WFC, reading tile adjacency rules from XML and constructing the wave from discrete tileset pieces.
• Program.cs — Entry point that parses samples.xml, instantiates the correct model variant, runs the generation loop, and saves output bitmaps.
• samples.xml — Declarative configuration file that defines every sample run: which model to use, input image, output size, pattern size, symmetry, and iteration count.
• Helper.cs — Utility functions for bitmap I/O, color manipulation, and symmetry transforms (reflections/rotations) used across both model implementations.

Components & responsibilities

• Model (Model.cs) (C#, multi-dimensional arrays) — Abstract base implementing the Run/Observe/Propagate loop and shared wave state management
  • Failure mode: Infinite loop if contradiction detection fails; incorrect output if propagator tables are built incorrectly in subclasses
• OverlappingModel (OverlappingModel.cs) (C#, System.Drawing bitmap parsing) — Extracts pixel patterns from bitmap input and builds pixel-level overlap adjacency constraints
  • Failure mode: Wrong outputs if symmetry transforms are applied incorrectly; memory exhaustion for large N on complex inputs
• SimpleTiledModel (SimpleTiledModel.cs) (C#, XML parsing, PNG loading) — Reads tile PNGs and XML neighbor rules to build tile-adjacency constraint tables
  • Failure mode: Contradictions if XML adjacency rules are incomplete or contradictory; missing tile files cause runtime exceptions
• Program.cs — CLI orchestrator: parses config, instantiates models, manages retry loops

How to make changes

Add a new overlapping (bitmap) sample

1. Place your PNG input image in the samples/ directory (e.g. samples/MyPattern.png) (samples/MyPattern.png)
2. Add an <overlapping> entry in samples.xml referencing your image name, desired output width/height, pattern size N, and symmetry value (samples.xml)

Add a new simple-tiled tileset

1. Create a new subdirectory under tilesets/ (e.g. tilesets/MyTileset/) and place all tile PNG files inside it (tilesets/MyTileset)
2. Create tilesets/MyTileset.xml defining <tile> entries with symmetry attributes and <neighbor> adjacency constraints following the Castle.xml schema (tilesets/Castle.xml)
3. Add a <simpletiled> entry in samples.xml referencing your tileset name and desired output dimensions (samples.xml)

Implement a new model variant (e.g. 3D or hierarchical)

1. Create a new C# file (e.g. NewModel.cs) that inherits from Model, implementing the constructor to populate propagator[] with your adjacency rules (Model.cs)
2. Override the Graphics() method in your subclass to reconstruct output from the wave[] boolean array in your domain-specific format (OverlappingModel.cs)
3. Add a branch in Program.cs to parse your new model's XML tag from samples.xml and instantiate your class (Program.cs)
4. Add helper symmetry or I/O utilities specific to your model in Helper.cs if needed (Helper.cs)

Change the entropy heuristic or observation strategy

1. Locate the NextUnobservedNode() method in Model.cs that selects the cell with lowest Shannon entropy and modify the scoring formula (Model.cs)
2. Adjust the Observe() method in Model.cs to change how a pattern is chosen (e.g. weighted random vs. deterministic) when collapsing a cell (Model.cs)

Why these technologies

• C# (.NET) — Provides fast native execution for the compute-intensive wave propagation loops, strong type safety for the multi-dimensional arrays encoding the wave state, and easy bitmap I/O via System.Drawing.
• XML (samples.xml + tileset XMLs) — Human-readable declarative format for specifying generation parameters and tile adjacency rules without requiring code changes, keeping the engine data-driven.
• PNG bitmaps as input/output — Lossless format that exactly preserves pixel colors — critical for the overlapping model which must extract and compare exact NxN color patterns.

Trade-offs already made

• Single-threaded propagation loop

  • Why: The arc-consistency propagation is inherently sequential: each collapsed cell may invalidate neighbors which must be re-evaluated before proceeding.
  • Consequence: Large output grids (e.g. 256×256) can be slow; no parallelism is exploited even though independent subregions could theoretically be solved concurrently.

• Full restart on contradiction rather than backtracking

  • Why: Simplifies implementation significantly; the probability of contradiction is low enough for most inputs that retrying from scratch is practical.
  • Consequence: For highly constrained inputs (e.g. mazes), many attempts may be wasted; a proper backtracking stack would be more efficient but much more complex.

• Precomputed propagator tables at construction time

  • Why: All pattern-compatibility lookups during propagation are O(1) array accesses rather than recomputed per step, making the hot loop fast.
  • Consequence: Constructor time and memory usage scale with O(P² × 4) where P is pattern count; for large N or large inputs this becomes significant.

• Separate OverlappingModel and SimpleTiledModel classes

  • Why: The two use-cases have fundamentally different constraint representations (pixel overlap vs. explicit neighbor rules) that don't share construction logic.
  • Consequence: Some logic duplication exists and adding new model types requires inheriting from Model and re-implementing constraint building from scratch.

Non-goals (don't propose these)

• Real-time or interactive generation (batch-only CLI tool)
• 3D voxel generation (though community forks exist)
• Guaranteed termination — contradictions cause retries with no hard proof of convergence
• GPU acceleration or multi-threaded propagation
• Semantic understanding of tile content — all constraints are purely structural/visual

Traps & gotchas

System.Drawing (used for PNG I/O) requires the libgdiplus native library on Linux/macOS — on non-Windows hosts you must install it (e.g. 'brew install mono-libgdiplus' or 'apt install libgdiplus') or the run will silently crash. N=3 is typical but increasing N to 4+ causes pattern count to explode exponentially, making generation very slow or always-contradicting. The 'limit' attribute in samples.xml caps retries, not steps — if set to 0 it runs once with no retry on contradiction.

Architecture

Concepts to learn

• Shannon Entropy (as a collapse heuristic) — Model.cs selects which cell to collapse next by picking the cell with the lowest Shannon entropy over its remaining possible patterns — understanding this is essential to understanding why the algorithm avoids early contradictions.
• Arc Consistency / Constraint Propagation — After each collapse, Propagate() in Model.cs enforces arc consistency by banning patterns that violate adjacency constraints and propagating those bans through a stack — this is the computational core of WFC.
• Superposition (as a data structure) — The 'wave' array in Model.cs stores a boolean matrix [cell × pattern] representing which patterns are still possible at each cell — this superposition collapses one cell at a time, directly mirroring quantum measurement.
• Texture Synthesis by Example — OverlappingModel.cs implements a form of non-parametric texture synthesis — knowing this research context explains why NxN pattern frequency matching (the C1/C2 conditions in the README) is the correctness criterion.
• Symmetry Group (D4 / dihedral group) — OverlappingModel applies rotations and reflections (the 8 symmetries of the square) to each extracted pattern to augment training data — the 'symmetry' attribute in samples.xml controls how many of these 8 transforms are used.
• NP-hardness of Boolean Satisfiability (relevance to contradictions) — The README notes that deciding if a valid output exists is NP-hard — understanding this explains why WFC uses heuristic observation order and retry loops rather than a complete solver, and why contradictions are unavoidable in the worst case.

Related repos

• math-fehr/fast-wfc — C++ port of the same algorithm with significant performance optimizations — useful reference for understanding algorithmic bottlenecks in this C# version.
• kchapelier/wavefunctioncollapse — JavaScript port that closely mirrors this repo's API, useful for running WFC in the browser without a .NET runtime.
• ikarth/wfc_2019f — Python implementation with more experimental features (backtracking, multiple heuristics) that extends ideas from this reference repo.
• nickmccullum/algorithmic-trading-python — Unrelated — excluded intentionally.
• mxgmn/MarkovJunior — The author's follow-up project that generalizes WFC into a probabilistic rewriting language — the direct evolutionary successor to this repo.

PR ideas

To work on one of these in Claude Code or Cursor, paste: Implement the "<title>" PR idea from CLAUDE.md, working through the checklist as the task list.

Add GitHub Actions CI workflow to build and test WaveFunctionCollapse.csproj on every PR

There is a .github/ directory (currently only containing FUNDING.yml) but no CI workflow file. The project has a WaveFunctionCollapse.csproj and multiple .cs files (Model.cs, OverlappingModel.cs, SimpleTiledModel.cs, Helper.cs, Program.cs) with no automated build verification. A new contributor could add a dotnet build/run smoke-test workflow so that any future PR that breaks compilation or crashes on the bundled samples.xml examples is caught automatically.

• [ ] Create .github/workflows/ci.yml referencing the WaveFunctionCollapse.csproj build target
• [ ] Add a 'dotnet build' step targeting the .csproj file on ubuntu-latest and windows-latest runners
• [ ] Add a smoke-test step that runs 'dotnet run' with a small iteration count against a known sample entry in samples.xml (e.g. 'Chess' or 'RedDot') and asserts a zero exit code
• [ ] Pin the dotnet-version in the workflow to match the <TargetFramework> declared in WaveFunctionCollapse.csproj
• [ ] Document the new badge in README.md

Extract and unit-test the pure algorithmic core of Model.cs (Observe/Propagate/Ban) into a separate testable class

Model.cs contains the entire WFC algorithm including Observe(), Propagate(), Ban(), and Run() with no separation between I/O concerns and pure logic. Because everything lives in one class hierarchy (Model → OverlappingModel, Model → SimpleTiledModel), there are currently zero automated tests verifying correctness of the constraint-propagation logic. Splitting the propagation kernel into a standalone, dependency-free class would allow unit tests to assert invariants such as: after Ban() the corresponding wave cell is false, after a contradiction Run() returns false, and a fully-observed wave produces a valid output consistent with C1 (only patterns present in input appear in output).

• [ ] Identify the pure-logic methods in Model.cs: Ban(), Propagate(), Observe(), and the wave/compatible/sumsOfWeights arrays
• [ ] Create a new file WfcCore.cs (or WfcPropagator.cs) that extracts those methods and data structures with no Bitmap/XML/file-system dependencies
• [ ] Refactor Model.cs, OverlappingModel.cs, and SimpleTiledModel.cs to delegate to the new class rather than duplicating state
• [ ] Add a test project (WaveFunctionCollapse.Tests.csproj) with xUnit or NUnit
• [ ] Write unit tests: Ban() sets wave[node][t]=false, Propagate() after total contradiction returns false from Run(), a 1×1 output from the 'Chess' sample always equals one of the two input colors

Add a dedicated XML schema file and validation for samples.xml, and document every supported attribute in README.md

samples.xml is the single configuration file that drives all sample runs and controls attributes like 'N', 'width', 'height', 'periodicInput', 'periodic', 'symmetry', 'ground', 'heuristic', 'black', and tile-set options — but none of these attributes are formally specified anywhere. There is no XSD/schema file in the repo, so contributors adding new samples frequently get silent mis-configurations. The README references the output images but never explains what each samples.xml attribute does. A contributor could add an XSD schema and document each attribute, making the configuration surface explicit and validatable.

• [ ] Read all attributes used across every <overlapping> and <simpletiled> element in samples.xml (N, width, height, periodicInput, periodic, symmetry, ground, heuristic, black, subset, etc.)
• [ ] Create samples.xsd at the repo root defining each element and attribute with type constraints and documentation annotations

Good first issues

1. Add XML documentation comments (///) to all public methods in Model.cs and OverlappingModel.cs — currently there are none, making the codebase hard to navigate for newcomers. 2. Replace System.Drawing with ImageSharp (SixLabors.ImageSharp) in Helper.cs to eliminate the libgdiplus platform dependency and make the project work cross-platform out of the box. 3. Add a basic xUnit or NUnit test project that loads Chess.png or Knot.png, runs the overlapping model with a fixed seed, and asserts the output is non-null and the correct dimensions — currently there is zero test coverage.

Top contributors

• @mxgmn — 85 commits
• @PascalCorpsman — 2 commits
• @lamelizard — 2 commits
• @AliasFactory — 1 commits
• @Grovre — 1 commits

Recent commits

• de7d22e — nonperiodic input fix (mxgmn)
• a024995 — Merge pull request #106 from AliasFactory/add-godot-plugin (mxgmn)
• 1ff6d4d — Add Godot Fast WFC plugin to notable ports (AliasFactory)
• 910956c — net10.0, more build instructions (mxgmn)
• 74c0774 — Update README.md (mxgmn)
• a088882 — edit (mxgmn)
• eee466c — Dart port (mxgmn)
• 05847f2 — Merge pull request #93 from PascalCorpsman/patch-1 (mxgmn)
• e201a1d — Update README.md (PascalCorpsman)
• f21d365 — p5js port, Free Pascal port (mxgmn)

Security observations

WaveFunctionCollapse is a standalone bitmap/tilemap generation tool with a limited attack surface, as it is primarily

• Medium · Unsafe XML Parsing (XXE Risk) — Program.cs, SimpleTiledModel.cs (XML parsing of samples.xml and tileset XML files). The codebase parses XML configuration files (samples.xml, tilesets/Castle.xml) using C# XmlDocument or similar XML APIs. If external entity processing is enabled (which is the default in older .NET XML parsers), an attacker who can control or substitute the XML input files could exploit XML External Entity (XXE) injection to read local files, perform SSRF, or cause denial of service. Fix: Explicitly disable DTD processing and external entity resolution when parsing XML. Use XmlReaderSettings with DtdProcessing = DtdProcessing.Prohibit and XmlResolver = null. Example: var settings = new XmlReaderSettings { DtdProcessing = DtdProcessing.Prohibit, XmlResolver = null };
• Medium · Path Traversal via XML Configuration — Program.cs, OverlappingModel.cs, SimpleTiledModel.cs. File paths for sample images and tilesets are read from XML configuration files (samples.xml). If an attacker can modify or supply a malicious XML file, they could specify arbitrary file paths (e.g., ../../etc/passwd or sensitive system files) that the application would attempt to read, leading to path traversal vulnerabilities. The application likely constructs file paths directly from XML attribute values without sanitization. Fix: Validate and sanitize all file paths derived from XML configuration before use. Use Path.GetFullPath() and verify the resulting path starts with the expected base directory. Reject any paths containing '..' or absolute path indicators.
• Low · Uncontrolled Resource Consumption (DoS via Large Inputs) — Model.cs, OverlappingModel.cs, SimpleTiledModel.cs, samples.xml. The WFC algorithm allocates large arrays based on user-supplied parameters from XML (output width, height, pattern size N, etc.). Extremely large values for these parameters could cause excessive memory allocation or CPU consumption, leading to denial of service. There appears to be no upper bound validation on these parameters. Fix: Implement validation and enforce reasonable upper bounds on input parameters such as width, height, and pattern size (N) before allocating memory or starting computation. Reject configurations that exceed defined thresholds.
• Low · Insecure Random Number Generation — Model.cs, Program.cs. The WFC algorithm uses a seeded random number generator (System.Random) for procedural generation. If predictable seeds are used (e.g., fixed seeds from XML or time-based seeds without sufficient entropy), the output could be deterministically reproduced. While this is often intentional for reproducibility, it could be a concern if randomness is expected to be unpredictable in any security-sensitive context. Fix: For reproducibility this is acceptable in a generative art context. If any security-sensitive randomness is needed in future extensions, use System.Security.Cryptography.RandomNumberGenerator instead of System.Random.
• Low · No Input Validation on PNG/Bitmap Files — Helper.cs, OverlappingModel.cs, SimpleTiledModel.cs. The application reads PNG image files from the filesystem as input samples. Maliciously crafted PNG files could potentially exploit vulnerabilities in the image parsing library (System.Drawing or similar). While the risk depends on the underlying library version, there is no apparent validation of image dimensions or file integrity before processing. Fix: Validate image files before processing: check file size limits, validate dimensions are within acceptable bounds, and ensure the image parsing library is kept up to date. Consider using a sandboxed or containerized environment when processing untrusted image inputs.
• Low · Missing Dependency Version Pinning — WaveFunctionCollapse.csproj. The WaveFunctionCollapse.csproj does not appear to pin specific dependency versions for NuGet packages. This could allow supply chain attacks where a compromised or malicious package version is automatically pulled in during builds. Fix: Pin all NuGet package dependencies to specific, known-good versions. Use a lock file (packages.lock.json) and enable deterministic builds. Regularly audit dependencies for known vulnerabilities using tools like 'dotnet list package --vulnerable'.

LLM-derived; treat as a starting point, not a security audit.

Where to read next

• Open issues — current backlog
• Recent PRs — what's actively shipping
• Source on GitHub

---

Generated by RepoPilot. Verdict based on maintenance signals — see the live page for receipts. Re-run on a new commit to refresh.