Einfache Implementierung eines Labyrinth Erzeugungsverfahren (random DFS)

Question

In einem Interview fragten meine Interviewer mir diese Frage:

eine Funktion entwickelt ein zufälliges Labyrinth zu erzeugen

Dies ist ein ziemlich schwierig Frage in 30min zu lösen, wenn Sie diese Frage vorher nicht gelöst haben. Im Internet gibt es viele Lösungen, aber keine scheint einfach. Das Verfahren sollte diese Einschränkung beachten:

• sollte die Größe des Labyrinths (ein Quadrat Labyrinth NxN)
• es nur Wände und Pfad bestehen akzeptieren soll
• , um es einfach, geht der Algorithmus Döns t brauchen, um den Eintrag und den Ausgang

zu setzen Ich werde die Antwort mit der Lösung veröffentlichen, so dass andere Leute diese Frage finden können.

Beispiel eines erzeugten maze:

. # # . # . . . . . 
. . . . . . # # # . 
# . # # # # . . . . 
. # . . . . # . # . 
. # . # # . # . # . 
. # . # . . # . . # 
. . . # . # . # . . 
. # . # . . . # # . 
# . . . # . # . . . 
. . # . # . . . # . 

Answer 1

Eine einfache randomisierte DFS verwendet werden kann, um das Labyrinth zu erzeugen. Um ein vollständiges walled Labyrinth zu starten ist auf die Größe von NxN initialisiert, dann durchquert diese Funktion das Labyrinth und verleiht er einen Weg, wenn possibile:

function generateMaze(&$maze, $point) { 
    $dirs = [ 
     [0,-1], 
     [1,0], 
     [0,1], 
     [-1,0], 
    ]; 

    shuffle($dirs); 

    foreach($dirs as $dir) { 
     $newPoint = [$point[0] + $dir[0], $point[1] + $dir[1]]; 

     if (isGoodPath($maze, $newPoint)) { 
      $maze[$newPoint[0]][$newPoint[1]] = '.'; 
      generateMaze($maze, $newPoint); 
     } 
    } 

    return $maze; 
} 

Der Schlüssel zur Lösung dieses eine gute Implementierung der Funktion ist isGoodPath() diese Funktion nur wenn überprüft der neue Pfad ist im Inneren des Labyrinths und wenn wir die Wände entfernen (dh wir nicht zwei parallel neben „freien“ Weg haben kann)

können Sie die vollständige Umsetzung laufen hier: https://ideone.com/oufifB

Ein 25x25 Labyrinth :

# . . # . . . # . . . . . # . . . . . . . # . # . 
. # . # # # . . . # # # . . # # . # # # . . . . . 
. # . . . . # . # . . . # . . . # . . . . # . # . 
. . # # # . # . . # . # # # # . . . # # . # . . # 
. # . . # . . # . # . . # . # # # # . . # . # . . 
. . # . # # . # . . # . . . . . . # . # . . . # . 
# . . . . # . . # . . # . # . # # . . . . # # . . 
. . # # . . # . . # . # . # . . . . # # . . # . # 
. # . . # . # . # . . # . . # # . # . . # . # . . 
. . . # . . # . . . # . . # . # . # . # . . . # . 
# # . # . # . # # # . # # . . . . # . # . # # . . 
. . . # . . . . . . . . # . # # # # . . . # # . # 
# # # . . # # # # . # . . . # . . . . # # . . . # 
. . . # # . . . . # # . # . # . # # # # # . # # . 
. # . . . . # # . # . . # . # . . . . # . . # . . 
. . # . # # . . . . # # # . . # # # # . . # # # . 
# . . # . . . # # . . . . # . # . . . . # . # # . 
. # . . # . # . # # . # . . . # . # # # . . . . . 
. . # . . # . . . . # . # # . # . # . . # # . # . 
# . . # . . . # # . # . . . . # . . # . . . . # . 
. . # . . # # . # . . # # . # . # . . # . # # . . 
# . . . # . . . . # . . . # . . # # . # . # . # # 
# # . # . . # . # . # # . # # . . . . # . . . . . 
# . . . # # # . . . # # . . # # . # # . # # # # . 
. . # . . . . . # . . . # . . . . . . . . . . . . 

Wenn Sie ein "hübscheres" Labyrinth möchten, können Sie einfach ganze Wände zum Rand des Labyrinths hinzufügen