Solving the Tantrix board game puzzle using a template-based Wave Function Collapse approach

Abstract

Diese Bachelorarbeit wendet den Wave Function Collapse Algorithmus auf das Tantrix Brettspiel an, um automatisch Ausgabebilder zu erzeugen, die visuell den Regeln des Spiels folgen. Um dies zu erreichen, werden zunächst digitale Versionen der echten Spielsteine erzeugt, zusammen mit einer Datei, welche die erlaubten Nachbarschaftsbeziehungen der Steine beschreibt. Da die Spielsteine eine hexagonale Form haben, wird ein schon vorhandenes Framework dahingehend erweitert, dass es den WFC auch auf diese Form anwenden kann. Des Weiteren wird eine neue Funktionalität eingeführt, bei der ein Benutzer ein Bild mit einer handgemalten Form in das Programm laden kann. Der Algorithmus rekonstruiert diese Form dann mit den digitalen Steinen und füllt übrige Lücken im Bild automatisch auf. Am Ende dieser Arbeit wird die modifizierte Version des WFC Algorithmus hinsichtlich Laufzeit und Erfolgsrate evaluiert.

This bachelor thesis applies the Wave Function Collapse algorithm (WFC) to the Tantrix board game in order to automatically create output images that visually adhere to the game’s rules. To achieve this, digital representations of the game’s physical tiles are created, along with a file describing the adjacency rules for the tiles. Since the Tantrix tiles are of hexagonal shape, a preexisting framework containing a basic implementation of the WFC is expanded to support hexagonal tiles. Furthermore, an additional functionality is added to the algorithm: A user can provide an image with a hand drawn shape to the program, which is then recreated by the algorithm using the digital Tantrix tiles. Any open spaces are afterwards filled in using the normal WFC. At the end of this thesis, the performance of the modified WFC algorithm is evaluated in terms of runtime and success rate.