So codieren Sie Ihren eigenen prozeduralen Dungeon-Kartengenerator mithilfe des Random-Walk-Algorithmus

Da sich die Technologie weiterentwickelt und Spielinhalte algorithmischer generiert werden, ist es nicht schwer, sich die Erstellung einer lebensechten Simulation mit einzigartigen Erfahrungen für jeden Spieler vorzustellen.

Technologische Durchbrüche, Geduld und verfeinerte Fähigkeiten werden uns dorthin bringen, aber der erste Schritt besteht darin, die Erzeugung prozeduraler Inhalte zu verstehen .

Obwohl es viele sofort einsatzbereite Lösungen für die Kartengenerierung gibt, lernen Sie in diesem Lernprogramm, Ihren eigenen zweidimensionalen Dungeon-Kartengenerator mithilfe von JavaScript von Grund auf neu zu erstellen.

Es gibt viele zweidimensionale Kartentypen, die alle die folgenden Eigenschaften aufweisen:

1. Zugängliche und unzugängliche Bereiche (Tunnel und Wände).

2. Eine verbundene Route, auf der der Spieler navigieren kann.

Der Algorithmus in diesem Tutorial basiert auf dem Random-Walk-Algorithmus, einer der einfachsten Lösungen für die Kartengenerierung.

Nach dem Erstellen einer gitterartigen Karte von Wänden beginnt dieser Algorithmus an einer zufälligen Stelle auf der Karte. Es werden immer wieder Tunnel gebaut und zufällige Kurven gefahren, um die gewünschte Anzahl von Tunneln zu vervollständigen.

Um eine Demo anzuzeigen, öffnen Sie das folgende CodePen-Projekt, klicken Sie auf die Karte, um eine neue Karte zu erstellen, und ändern Sie die folgenden Werte:

  1. Abmessungen: Breite und Höhe der Karte.
  2. MaxTunnels: Die größte Anzahl von Umdrehungen, die der Algorithmus beim Erstellen der Karte ausführen kann.
  3. MaxLength: Die größte Länge jedes Tunnels, den der Algorithmus vor einer horizontalen oder vertikalen Kurve auswählt .

Hinweis: Je größer der maxTurn im Vergleich zu den Abmessungen ist, desto dichter wird die Karte. Je größer die maxLength im Vergleich zu den Abmessungen ist, desto „tunnel-y“ sieht sie aus.

Lassen Sie uns als Nächstes den Algorithmus zur Kartengenerierung durchgehen, um zu sehen, wie er funktioniert:

  1. Erstellt eine zweidimensionale Karte von Wänden
  2. Wählt einen zufälligen Startpunkt auf der Karte
  3. Während die Anzahl der Tunnel nicht Null ist
  4. Wählt eine zufällige Länge aus der maximal zulässigen Länge
  5. Wählt eine zufällige Richtung zum Drehen (rechts, links, oben, unten)
  6. Zeichnet einen Tunnel in diese Richtung und vermeidet dabei die Kanten der Karte
  7. Verringert die Anzahl der Tunnel und wiederholt die while-Schleife
  8. Gibt die Karte mit den Änderungen zurück

Diese Schleife wird fortgesetzt, bis die Anzahl der Tunnel Null ist.

Der Algorithmus im Code

Da die Karte aus Tunnel- und Wandzellen besteht, können wir sie als Nullen und Einsen in einem zweidimensionalen Array wie folgt beschreiben:

map = [[1,1,1,1,0], [1,0,0,0,0], [1,0,1,1,1], [1,0,0,0,1], [1,1,1,0,1]]

Da sich jede Zelle in einem zweidimensionalen Array befindet, können wir auf ihren Wert zugreifen, indem wir ihre Zeile und Spalte kennen, z. B. map [row] [column].

Bevor Sie den Algorithmus schreiben, benötigen Sie eine Hilfsfunktion, die ein Zeichen und eine Dimension als Argumente verwendet und ein zweidimensionales Array zurückgibt.

createArray(num, dimensions) { var array = []; for (var i = 0; i < dimensions; i++) { array.push([]); for (var j = 0; j < dimensions; j++) { array[i].push(num); } } return array; } 

Um den Random-Walk-Algorithmus zu implementieren, legen Sie die Abmessungen der Karte (Breite und Höhe), die maxTunnelsVariable und die maxLengthVariable fest.

createMap(){ let dimensions = 5, maxTunnels = 3, maxLength = 3; 

Erstellen Sie als Nächstes ein zweidimensionales Array mit der vordefinierten Hilfsfunktion (zweidimensionales Array von Einsen).

let map = createArray(1, dimensions);

Richten Sie eine zufällige Spalte und eine zufällige Zeile ein, um einen zufälligen Startpunkt für den ersten Tunnel zu erstellen.

let currentRow = Math.floor(Math.random() * dimensions), currentColumn = Math.floor(Math.random() * dimensions);

Um die Komplexität diagonaler Kurven zu vermeiden, muss der Algorithmus die horizontale und vertikale Richtung angeben. Jede Zelle befindet sich in einem zweidimensionalen Array und kann anhand ihrer Zeile und Spalte identifiziert werden. Aus diesem Grund können die Richtungen als Subtraktionen von und / oder Additionen zu den Spalten- und Zeilennummern definiert werden.

Um beispielsweise zu einer Zelle um die Zelle [2] [2] zu gelangen, können Sie die folgenden Vorgänge ausführen:

  • um nach oben zu gehen , subtrahiere 1 von seiner Zeile [1] [2]
  • Um nach unten zu gehen , füge 1 zu seiner Reihe hinzu [3] [2]
  • Um nach rechts zu gehen , füge 1 zu seiner Spalte hinzu [2] [3]
  • um nach links zu gehen , subtrahiere 1 von seiner Spalte [2] [1]

Die folgende Karte veranschaulicht diese Vorgänge:

Stellen Sie die directionsVariable nun auf die folgenden Werte ein, aus denen der Algorithmus auswählen wird, bevor Sie jeden Tunnel erstellen:

let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

Schließlich initiieren randomDirectionVariable, um einen zufälligen Wert aus dem Richtungsarray zu speichern, und setzen Sie die lastDirectionVariable auf ein leeres Array, das das ältere enthältrandomDirectionWert.

Hinweis: Das lastDirectionArray ist in der ersten Schleife leer, da kein älterer randomDirectionWert vorhanden ist.

let lastDirection = [], randomDirection;

Stellen Sie als Nächstes sicher, dass maxTunnelnicht Null ist und die Abmessungen und maxLengthWerte empfangen wurden. Suchen Sie weiter nach zufälligen Richtungen, bis Sie eine finden, die nicht umgekehrt oder identisch ist lastDirection. Diese do while-Schleife verhindert, dass der kürzlich gezeichnete Tunnel überschrieben oder zwei Tunnel hintereinander gezeichnet werden.

Wenn Sie lastTurnbeispielsweise [0, 1] sind, verhindert die do while-Schleife, dass sich die Funktion vorwärts bewegt, bis randomDirectionein Wert festgelegt wird, der nicht [0, 1] oder umgekehrt [0, -1] ist.

do { randomDirection = directions[Math.floor(Math.random() * directions.length)]; } while ((randomDirection[0] === -lastDirection[0] && randomDirection[1] === -lastDirection[1]) || (randomDirection[0] === lastDirection[0] && randomDirection[1] === lastDirection[1])); 

In der do while-Schleife gibt es zwei Hauptbedingungen, die durch ein || geteilt werden (ODER) Zeichen. Der erste Teil der Bedingung besteht ebenfalls aus zwei Bedingungen. Die erste überprüft , ob das randomDirection‚s erste Element ist die Umkehrung des lastDirection‘ s ersten Elements. Der zweite prüft, ob der randomDirectionzweite Gegenstand der Rückseite des lastTurnzweiten Gegenstands ist.

Um zu veranschaulichen, ob der Wert lastDirection[0,1] und randomDirection[0, -1] ist, prüft der erste Teil der Bedingung, ob randomDirection[0] === - lastDirection[0]), was 0 === - 0 entspricht. und ist wahr.

Then, it checks if (randomDirection[1] === — lastDirection[1]) which equates to (-1 === -1) and is also true. Since both conditions are true, the algorithm goes back to find another randomDirection.

The second part of the condition checks if the first and second values of both arrays are the same.

After choosing a randomDirection that satisfies the conditions, set a variable to randomly choose a length from maxLength. Set tunnelLength variable to zero to server as an iterator.

let randomLength = Math.ceil(Math.random() * maxLength), tunnelLength = 0;

Make a tunnel by turning the value of cells from one to zero while the tunnelLength is smaller than randomLength. If within the loop the tunnel hits the edges of the map, the loop should break.

while (tunnelLength < randomLength) { if(((currentRow === 0) && (randomDirection[0] === -1))|| ((currentColumn === 0) && (randomDirection[1] === -1))|| ((currentRow === dimensions — 1) && (randomDirection[0] ===1))|| ((currentColumn === dimensions — 1) && (randomDirection[1] === 1))) { break; }

Else set the current cell of the map to zero using currentRow and currentColumn. Add the values in the randomDirection array by setting currentRow and currentColumn where they need to be in the upcoming iteration of the loop. Now, increment the tunnelLength iterator.

else{ map[currentRow][currentColumn] = 0; currentRow += randomDirection[0]; currentColumn += randomDirection[1]; tunnelLength++; } } 

After the loop makes a tunnel or breaks by hitting an edge of the map, check if the tunnel is at least one block long. If so, set the lastDirection to the randomDirection and decrement maxTunnels and go back to make another tunnel with another randomDirection.

if (tunnelLength) { lastDirection = randomDirection; maxTunnels--; } 

This IF statement prevents the for loop that hit the edge of the map and did not make a tunnel of at least one cell to decrement the maxTunnel and change the lastDirection. When that happens, the algorithm goes to find another randomDirection to continue.

When it finishes drawing tunnels and maxTunnels is zero, return the resulting map with all its turns and tunnels.

} return map; };

You can see the complete algorithm in the following snippet:

Congratulations for reading through this tutorial. You are now well-equipped to make your own map generator or improve upon this version. Check out the project on CodePen and on GitHub as a react application.

Thanks for reading! If you liked this story, don't forget to share it on social media.

Special thanks to Tom  for co-writing this article.