Analyse des Markov Junior Algorithmus am Beispiel der Generierung von Labyrinthen

Abstract

Die prozedurale Generierung ist heutzutage vielseitig verwendet, da die automatische Generierung von In-halten viel Zeit und Aufwand erspart. Sie ist ein stetig wachsender Bereich. Darunter gibt es den neuen Markov Junior Algorithmus von Maxim Gumin. Dieser erzeugt Rastergrafiken, welche durch das Grundprinzip der visuellen Ersetzungsregeln generiert werden. Eine Ersetzungsregel beinhaltet ein Eingabemuster, welches durch das entsprechende Ausgabemuster der Regel im Raster ersetzt wird. Diese Arbeit beschäftigt sich damit, den Markov Junior Algorithmus näher darzustellen und zu analysieren. Dafür wird in dieser Arbeit ein neuer Ansatz zur Generierung von perfekten Labyrinthen mit dem Markov Junior Algorithmus entwickelt. Ein perfektes Labyrinth hat keine geschlossenen Kreise oder unerreichbaren Stellen. Der Ansatz legt den Fokus auf die Kontrollierbarkeit gewisser Eigenschaften, wie den Verlauf des Lösungsweges und der Anzahl an direkten Abzweigungen vom Lösungsweg. Dabei wird dies durch einen modularen Ansatz gelöst, welcher zuerst den Lösungsweg, dann die Abzweigungspunkte vom Lösungsweg und zuletzt die restlichen Wege generiert. Das Ergebnis zeigt, dass der Markov Junior Algorithmus perfekte Labyrinthe generieren kann und zudem die Kontrolle über die genannten Eigenschaften erlaubt. Der Markov Junior Algorithmus beweist sich zudem als ein mächtiges Tool zur prozeduralen Generierung von simplen bis mittel komplexen Grafiken, bei dem durch wenig Code viel dargestellt werden kann. Jedoch hat die Umsetzung des Ansatzes gezeigt, dass Markov Junior durch Einschränkungen, wie z. B. das Fehlen von Variablen und die schnelle Unübersichtlichkeit der Ersetzungsregeln, eine erhöhte Komplexität aufweist.

Procedural content generation is widely used today as the automatic generation of content saves a lot of time and effort. It is a steadily growing field. Among its innovations is the new Markov Junior algorithm by Maxim Gumin. This algorithm generates grid graphics, which are produced based on the fundamental principle of visual rewrite rules. A rewrite rule includes an input pattern, which is replaced in the grid by the corresponding output pattern of the rule. This work aims to present and analyze the Markov Junior algorithm in more detail. To achieve this, a new approach to generating perfect mazes using the Markov Junior algorithm is developed. A perfect maze has no loops or unreachable areas. The approach focuses on the controllability of certain properties, such as the course of the solution path and the number of direct branches from the solution path. This is achieved through a modular approach that first generates the solution path, then the branching points from the solution path, and finally the remaining paths. The results show that the Markov Junior algorithm can generate perfect mazes and also allows control over the mentioned properties. Furthermore, the Markov Junior algorithm proves to be a powerful tool for the procedural content generation of simple to moderately complex graphics, where a lot can be depicted with little code. However, the implementation of the approach has shown that Markov Junior exhibits increased complexity due to limitations such as the lack of variables and the rapid lack of clarity of the rewrite rules.