7 stable releases
3.1.6 | Dec 5, 2022 |
---|---|
3.0.0 | Nov 30, 2022 |
#826 in Algorithms
Used in wavefc-cli
67KB
1.5K
SLoC
Wave Function Collapse
Character Map Demo
Overview
A home-grown implementation of the Wave Function Collapse algorithm written in Rust.
At its core, this function is designed to take in a sample input, of any kind, and create a new output based on that. The Wave
engine behind the algorithm has been designed to operate on bits and bitsets. This enables it to run against any two-dimensional, grid-based input: Character maps, images, video-game levels, sudoku puzzles, etc. The only requirement is that an adapter be written to support the given format. Currently, the program has only been written to support a character map text input. Though, an adapter for images is currently underway.
This project is subject to the MIT license as described in the license.txt
file.
Quick Setup
For those who are unfamiliar with Rust and just want to build the project from source, you're in the right spot. To get started, install the Rust toolchain over at rustup.rs.
Once you've successfully installed the toolchain, simply navigate into the source directory. Presumably you have already cloned this from the repo or downloaded it. Once in the directory, simply run cargo b --release
to build the project. To actually run the project, use cargo r --release -- <ARGS>
.
This isn't a tutorial for the Rust language or Cargo. So please check out their excellent resources and documentation over at rust-lang.org.
Discussion
By default, the CLI uses the sea, land, coast example as Robert Heaton describes in his blog post on the algorithm. This can be seen in the character map demo above. I think this way of introducing the algorithm makes a lot of sense. It's easy to understand and grasp in a practical way. It's based off the sample.txt
source file in the wavefc
crate. It's embedded at compile-time into the program to provide this functionality, though the size is beyond negligible.
The CLI and core logic have been separated into two packages in the source: wavefc-cli
and wavefc
. To create your own custom adapters and write your own CLI, I recommend using the wavefc-cli
source as a template and then building off of the wavefc
types from there. During development, I personally found it beneficial to build and run in --release
mode in Cargo. The build time difference between the two is negligible, and the actual collapse is much quicker in this optimized mode.
The program requires that a width and height be provided to size the output from. Feel free to play around with these values to create differently shaped outputs. Please note that the larger the size of the output, the longer the function generally takes, as the chances for it to contradict itself increase. Theoretically, if the output size specified is lower than or equal to the sample's size, there exists a valid result. The output size specified must be a product of the tile size. Tile sizes are explored in the next paragraph.
Trying a relatively large tile size compared to a tiny sample:
In the version 1 and version 2 of wavefc
, only the simple-tiled model was implemented for the algorithm. This severely limited its "creative" capabilities, creating rather dull outputs. In the current version of the algorithm, the overlapping-tiled model is used. This produces much better outputs and also more quickly in certain cases. Though, this model generally takes longer than the simple-tiled model. Luckily, the new overlapping logic is simply a more advanced superset of the original approach. This means that by specifying the tile size to be 1, you are essentially using the simple-tiled model.
The way the algorithm chooses which tile (superposition) to collapse next is based on the Shannon Entropy of a particular location. This is calculated using the probabilities of each of the possible values occurence in the original sample. These are all taken together to form the collective entropy for a given superposition.
The wavefc
library is currently single-threaded, given the sequential nature of the algorithm. However, I do recognize that a lot of performance optimizations could be made by sprinkling in some multi-threading. This is a long-term goal for the project, at the moment. I'm eyeing rayon
pretty frequently for this specific project.
The CLI has a whole host of flags to tweak the program's settings. There are too many to cover in detail, and doing so would be frivilous regardless. However, by using the clap
library, the help flag is supported to show a list of all available flags.
Using this Project in your Code
This project is available in two packages on crates.io: wavefc
and wavefc-cli
. If you just want to give the program a go, wavefc-cli
is probably your best bet to install. If you want to use this algorithm in your own code, adding wavefc
to your Cargo.toml
should suffice. As an alternative, you can use this project by manually copying its source or including it in a Cargo workspace.
A good place to start getting familiar with the source is wavefc/src/lib.rs
, which holds the majority of the actual Wave
code. To include this code in Rust, use the prelude with use wavefc::prelude::*;
.
Copyright © Zachary Morden 2022
Dependencies
~0.6–1MB
~18K SLoC