Exhaustive Backtracking in Hierarchical Wave Function Collapse for Procedural Music Generation
P.P. Varga Pál Patrik (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Rafa Bidarra – Mentor (TU Delft - Computer Graphics and Visualisation)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Wave Function Collapse (WFC) is among the most well-known and beloved procedural content generation algorithms. WFC solvers can be understood as a specific type of constraint solver, and as such, backtracking is an integral part of exploring the space of possible solutions. Recent advancements were inspired by this algorithm to model procedural music generation, using a hierarchy of many canvases, each with its own semantic domain within music composition (sections, chords, melody). In the model, due to the structural dependencies between canvases, constraints that involve cells from different canvases make exhaustive backtracking a challenge. Existing backtracking methods only consider a single set of variables, but if a specific value on one canvas can affect the entire structure of another canvas, we need more elaborate ways to deal with conflicts.
This paper presents the basic principles that backtracking models for this hierarchy should abide by, and additional guidelines for evaluating them. Two approaches are proposed, and their runtime efficiencies are compared. Depth-first traversal of the canvas hierarchy results in significantly shorter runtimes than its breadth-first counterpart.