Hierarchical WFC

Implementation of the Wave Function collapse algorithm using novel approaches to chunking, with additional preliminary research into combined Hierarchical and Semantic extensions located on the 3d branch.

Usage

2D Chunking

The 2D chunking implementation can generate outputs using both standard (Generate Single) and chunked generation (Generate Chunked) as well as options for configuring generation:

Option	Description
`Tileset`	The tileset used, tilesets with names of the format `<...> x y` (IE: `Village 3 2`) use the overlapping model and will likely require increasing `chunk_settings.size` and `chunk_settings.discard` options to generate.
`seed`	Seed used for generation when `random_seed` is disabled.
`graph_settings`	Controls for output size, `perodic` option constrains opposite edges to produce a result that can tile.
`deterministic`	Enable variant of the chunking algorithm that is guaranteed to be deterministic.
`multithreaded`	Use multiple threads when using chunked generation.
`chunk_settings.size`	Size of chunks.
`chunk_settings.overlap`	Additional padding added to size of chunk, chunks generate and write this extra padding to the world to propagate information between chunks.
`chunk_settings.discard`	Extra padding added after `ovelap` that is generated but not written to the world, ensures that valid generation exists after the chunk edge.
`chunk_settings.merging`	Approach used when extracting and merging chunks, `Mixed` is optimal, other options for debugging purposes.
`wfc_settings.backtracking`	Enable backtracking, the algorithm will backtrack and try different options instead of failing. `restarts_left` sets the maximum number of times the algorithm can backtrack. Change which heuristic is used when backtracking with the `heuristics` field.
`wfc_settings.entropy`	Method used to calculate tile entropy when choosing which cell to collapse. When using tilesets with weights `Shannon` should be prefered, `TileCount` is fastest.
`wfc_settings.progress_updates`	Set to `Some` with a timeout (such as `0.05` seconds) to show the generation progress live. Useful for visulising backtracking.
`wfc_settings.timeout`	Optional timeout, generation fails after this time is elapsed.
`draw_gizmos`	Show debbuging gizmos such as chunk boundaries.

3D Hierarchical Prototypes

Both multipass and chunking are built using the same components, for 3D navigation:

Orbit: Mouse3 or Alt + Mouse1
Pan: Shift + Mouse3 or Shift + Alt + Mouse1 The UI panels on the right are used to expose settings for each prototype.

For multipass prototype:

The Layout panel contains controls to start generation and change output size.
The Regenerate Region panel can select and regenerate a region.
The Replay panel can be used to view a replay of the generation order. Start by hiding all and expanding and replaying a pass.

For the chunking prototype:

The Debug Settings panel controls what parts of the output are generated and shown.
When focused, the Player Placeholder will show a draggable gizmo that loads and unload chunks in the specified radius. Similar to how a player might load chunks in a real game.
The Load Chunks can send events to manually load chunks, groups of chunks, or reset the world.

Compiling and Running

To compile and run first install rust.

The 2D implementation of WFC with our chunking approaches can be built and run with:

$ cargo run --release

The 3D prototypes located on the 3d branch can be built and run with:

$ cargo run --bin multipass --release
$ cargo run --bin chunking --release

Development was done on the nightly channel and tested with rustc 1.75.0-nightly (bf9a1c8a1 2023-10-08)

To switch rust to the nightly toolchain use:

$ rustup default nightly

Benchmarks

The main branch of the repo contains benchmarks located in the benches folder, python data processing code, raw data (benches/data), and figures (benches/output). To run the benchmarks, first install rust, then the benchmarks can be run from the root directory of the project with:

cargo bench --bench stats
cargo bench --bench chunking
cargo bench --bench failure_rate
cargo bench --bench backtracking