Building a High-Performance Wave Function Collapse Solver for three.js

Resources
, , ,
1

Building a High-Performance Wave Function Collapse Solver for three.js

Hi everyone,

I’m here after this pleasant exchange of ideas with @agargaro.

I’ve been working on a highly optimized Wave Function Collapse (WFC) solver, tailored for use with three.js, especially for procedural content generation inside WebGL apps.

I thought I’d share the full technical breakdown of the optimization journey — from naive code to ultra-fast performance!

WFC is a surprisingly simple concept. You can think of it like a fancy version of Sudoku.

Rather than explaining all the details myself, I’ll point you to some people who do a much better job at it:

Step 1: Naive Implementation

The initial prototype was textbook WFC:

  • Grid = 2D array of tile option arrays.

  • Propagation = full array scans with push/pop/shift operations.

  • Collapse picking = linear scan over all cells to find the lowest entropy.

Problems:

  • Massive memory churn (array slicing, object creation)

  • Grids over 50×50 took minutes to collapse

  • Completely impractical for real-time use

Step 2: Full Typed Array Rewrite

buffers_everywhere
buffers_everywhere735×500 70.5 KB

First big improvement: Buffers everywhere!

  • Replaced dynamic arrays with preallocated Uint8Array, Uint16Array, etc.

  • Option sets encoded as fixed-size buffers.

  • No temporary objects or per-frame GC pressure.

  • Operations done via direct index math (grid[i] instead of nested arrays).

Result:

Minutes → ~30 seconds for a 100×100 grid.

WFC2DBuffer
WFC2DBuffer1920×1458 104 KB

Step 3: Bitmask Encoding for Options

Next bottleneck: tile compatibility checks.

Previously:

Each neighbor would iterate over its allowed tiles, checking compatibility manually.

New system:

  • Each tile is represented as a bitmask.

  • Possible tiles per cell = a bitfield.

  • Neighbor constraints = precomputed bitfield compatibility matrices.

  • Collapse & propagation = simple bitwise ANDs and ORs.

Benefits:

  • Tile constraint checks are constant time.

  • Propagation becomes just bit ops.

  • Massive memory savings: 1 bit per tile instead of 1+ objects.

Result:

~30 seconds → ~2–3 seconds.

WFCOptionsBuffer
WFCOptionsBuffer1920×1458 115 KB

Step 4: Min-Heap for Entropy Picking

In WFC, you must find the cell with the fewest options (lowest entropy) at each collapse step.

Original method:

Linear scan (O(n)) over all grid cells.

Optimized method:

  • Maintain a Min-Heap (binary heap) storing cells sorted by entropy.

  • When a cell’s options shrink, update its position (O(log n) heapify).

  • Picking the next collapse cell becomes effectively O(1).

Heap Details:

  • Implemented using Typed Arrays (buffers everywhere!)

  • Stores entropy and cell index pairs compactly

  • Separate heap position tracking for fast updates

Result:

Seconds → Hundreds of milliseconds for big grids.

WFCMinHeapBuffer
WFCMinHeapBuffer1920×1458 119 KB

Step 5: Circular Stack for Propagation Queue

Propagation originally used recursion and array .shift()/.unshift(), creating call stack overhead and allocations.

Optimized propagation system:

  • Circular Stack Buffer using a fixed-size Uint32Array

  • Head/tail pointers wrap around the buffer

  • Constant-time push/pop, no shifting

  • No recursion = no call stack growth

Propagation is now:

  • Zero allocations

  • Linear in the number of affected cells

  • Constant memory usage

Result:

Solver runtime cut even further — now fitting almost fully inside a single render frame (even on medium-sized grids)!

Work in Progress

To aid debugging and tuning:

  • Building a tile edges editor to define tile relations and constraints.

  • Building a canvas-based WFC visualizer:

  • Configurable grid size, seed, cell size

  • Real-time collapse display

  • Click-to-force-collapse cells

  • Live logs and solver timing logs

Current Status & Next Steps

  • :white_check_mark: 2D WFC solver finished (*almost)

  • :white_check_mark: Reasonable real-time collapse even for large grids

  • :soon_arrow: 2D Renderer with THREE.Points and texture atlases

  • :soon_arrow: 2.5D Renderer (still using THREE.Points)

  • :soon_arrow: Full 3D WFC variant using BatchedMesh and layered texture atlases (thanks again to @agargaro and @gkjohnson)

  • :soon_arrow: Backtracking for better contradiction handling

  • :soon_arrow: Web workers with transferable and shared arrays

  • :soon_arrow: Explore the overlay model

Closing Thoughts

This was an intense but super rewarding project.

Key takeaways:

  • Avoid memory churn: preallocate everything early

  • Think bitwise: bitmasks are a huge win for option management

  • Move expensive operations (like entropy picking) from O(n) → O(log n) structures

I’ll be sharing my advancements here as I continue optimizing and extending procedural generation for three.js!

7 Likes