Wave function collapse algorithm with OpenMP

Implementation of wave function collapse algorithm (WFC, model synthesis) in C++ using basic libraries and OpenMP library for parallelization on CPU.

Program consists of parts:

• real problem $\rightarrow$ abstract problem (e.g. convert image with pattern to numbers and adjacency rules)
• abstract problem $\rightarrow$ abstract solution (fill board with numbers with contraints)
• abstract solution $\rightarrow$ real solution (e.g. convert numbers to output image)

Prerequisites

• build-essential (Make, g++)
• OpenMP
• C++ libraries - STL, SDL2, OpenMP

Compilation

Quick compilation:

make

With g++ parallelized:

g++ -O3 -fopenmp -DNUM_THREADS=16 `sdl2-config --libs` -lSDL2_image -o $(BUILD_DIR)/main main.cpp

With g++ sequential:

g++ -O3 `sdl2-config --libs` -lSDL2_image -o $(BUILD_DIR)/main main.cpp

Benchmarks

Run benchmarks (needs global setup in python/benchmark.py):

python ./python/benchmark.py

Example results (with two sequential algorithm implementation):

Note

Sequential algorithm uses recursive propagation which turned out to be very slow. Sequential with no propagation uses same method as parallel algorithm without going through checkerboard patterns one by one. OpenMP simulations have number of threads in the brackets. Performed with input pattern bricks with no rotations and with periodic condition on edges.

Examples

Input	Output
pipes setup (performed programatically)

Unfinished features

• resetting of states when seed needs lot of backtracking
• custom benchmark file