Eine zufällig generierte Karte für mein Dungeonprojekt wäre eine tolle Sache! In diesem Video zeige ich Dir, wie Du ein Zufallslabyrinth in C64 BASIC erzeugen kannst. Das Prinzip lässt sich aber natürlich auch auf jede andere Programmiersprache wie C++, C#, Java, oder Python übertragen.
Zwei Arten von Wanddefinitionen in Labyrinthen
Es wird davon ausgegangen, das die Kartenfelder als Blöcke definiert sind, also an einer Koordinate entweder eine Wand, oder ein Gang sein kann. Eine andere Möglichkeit wäre die Koordinaten alle als Gang zu definieren und die Wände zwischen den Feldern einzuziehen, dieses Verfahren kommt bei diesem Algorithmus allerdings nicht zum Tragen.
Außerdem soll man den Kartenrand verlassen können: Überschreitet man die Nordgrenze der Karte, betritt man automatisch die Karte wieder im Süden und umgekehrt, gleiches gilt natürlich auch für die Ost-West Richtung.
Der Algorithmus zum erstellen des Zufallslabyrinths
Zuerst wird festgelegt, welche Größe die Labyrinth-Karte haben soll, anschließend wird ein zufälliger Punkt, irgendwo auf dieser Karte bestimmt. Dieser Punkt wird auf einem Stack gespeichert, wir merken ihn uns also. Wir werden uns auf der Karte nun in einem Zweierraster bewegen um die Gänge anzulegen. Dabei werden immer zwei Gangfelder in eine Richtung „gegraben“.
Als nächstes wird also eine zufällige Richtung bestimmt in die sich das Gangsystem ausbreiten soll. Ist zwei Felder in dieser Richtung ein Wandfeld, erweitern wir den Gang dorthin, indem wir die beiden Felder in Gangfelder umwandeln. Außerdem wird nun auch das neu bestimmte Feld auf der Karte gemerkt, indem es auf den Stack gespeichert wird und eine neue Richtung wird bestimmt.
Ist auf der ermittelten Position in der zufällig bestimmten Richtung schon ein Gangfeld, kann das Labyrinth in diese Richtung nicht weiter ausgeweitet werden und eine andere Richtung wird versucht. Können die Gänge von dieser Stelle aus in keine andere Richtung mehr erweitert werden hat man eine Sackgasse erreicht. Das aktuelle Feld wird vom Stack entfernt und die vorherige Position wird erneut untersucht.
Ein evtl. von dort aus in eine andere Richtung erreichbares Feld wir dann wieder, wie oben beschrieben, zur Expansion des Gangsystems benutzt. Geht es in keine Richtung weiter wird auch dieses Feld vom Stack entfernt und das vorherige untersucht…
Diese Prozedur wird so lange fortgesetzt, bis nur noch ein Feld, das erste das wir per Zufall bestimmt haben, auf dem Stack liegt und es von da aus in keine Richtung weiter geht. Dann ist die Karte Vollständig!
Die Realisierung in BASIC
Ich habe den Algorithmus auf dem C64 als Subroutine in Basic umgesetzt, so das ich sie von verschiedenen Positionen in meinem Programm aus aufrufen, und Karten erzeugen lassen kann. Die Kartendaten werden in einem zahlen-basierten, mehrdimensionalen Array, bzw. einer Feld-variable, wie ein Array in C64 BASIC auch genannt wird, gespeichert. Die beiden Dimensionen der Feldvariable geben dabei die X und Y Koordinate an, eine dort gespeicherte 1 bedeutet, das an der Position ein Gang ist, eine 0 zeigt an, das sich dort ein Wandfeld befindet. Hier ein Beispiel:
K(5,8) = 1Das obige Beispiel bedeutet das sich auf den Kartenkoordinaten X5/Y8 ein Gangfeld befindet.
Die eigentliche Umsetzung des oben beschriebenen Algorithmus gestaltete sich als nicht allzu kompliziert. Der erste Entwurf passte in 22 Zeilen.
Weitere Optimierungen des Programms
Im folgendem Video habe ich ein paar Optimierungen am Code vorgenommen und hilfreiche Tips aus der Community umgesetzt. Einer davon bezog sich auf den hohen Speicherverbrauch der Kartendaten.
Speicherverbrauch der Labyrinth Karte optimieren
Im dem im Video oben gezeigten Entwurf habe ich mit einem Fließkommazahlen Array gearbeitet. Dies frisst eine Menge Speicher, von dem der C64 bekanntermaßen nur eine sehr begrenzte Menge zur Verfügung hat. Eine Karte mit den Außmaßen von 64×64 Feldern führte bereits zu einem „OUT OF MEMORY ERROR“.
Definiert man das Array bei der Dimensionierung mit DIM als Ganzzahlenvariable, so reserviert der C64 pro möglichem Wert statt 5 Bytes nun nur noch 2 Bytes, was deutlich weniger ist. Eine deutliche Einsparung also.
Des Weiteren habe ich im ersten Programm die Dimensionen zu hoch angelegt. Der Index eines Arrays beginnt, wie üblich in der Programmierung, bei 0. Wird in C64 BASIC eine Feldvariable dimensioniert gibt man nicht die Anzahl möglicher Feldinhalte an, sondern den maximalen Index:
DIM A%(10)Die Feld-Variable A% wird auf 11 mögliche Inhalte dimensioniert (Index 0-10), nicht auf 10 mögliche Werte!
Mehr zum Speicherbedarf von Feldvariablen und deren Dimensionierung erfahrt Ihr in diesem C64-Wiki Artikel zu Variablen (Felder und Arrays)!
Im Algorithmus selbst habe ich auch noch ein paar kleine Änderungen getätigt, beispielsweise wird die Richtungsangabe nun auch als Zahlenwert vorgehalten.
Viel Spaß!