Vor kurzem beobachte ich oft, wie meine Klassenkameraden im Computerraum ein Labyrinthspiel spielen. Es ist ziemlich interessant. Ich benutze auch Java, um einen Algorithmus zur Implementierung der zufälligen Generation von Labyrinthen zu schreiben. Tatsächlich handelt es sich um einen Tiefen-ersten-Traversal-Algorithmus für ein Diagramm. Die Grundidee ist, dass jeder Punkt im Labyrinth vier Wände hat, und dann.
1. Starten Sie den Zugriff aus jedem Punkt (mein Algorithmus wird so festgelegt, dass er von Punkt (0,0) beginnt) und besuchen Sie eine zufällige der vier Richtungen (jedes Mal, wenn Sie auf einen zugänglichen Punkt zugreifen, entfernen Sie die Wand in diese Richtung dieses Punktes), und der zugegriffene Punkt greift weiterhin in dieser Richtung darauf zu.
2. Jeder besuchte Punkt wird als zugegriffen identifiziert. Wenn ein Punkt auf eine bestimmte Richtung zugreift, werden wir zunächst feststellen, ob auf den zugegriffenen Punkt zugegriffen wurde oder die Grenze berührt. Wenn auf alle vier Richtungen des Punktes zugegriffen wurden oder nicht zugreifen können, kehren Sie zum vorherigen Punkt zurück. Der vorherige Punkt setzt den Prozess fort.
Nach dem Traversal auf diese Weise kann bestätigt werden, dass jeder Punkt besucht wurde. Da die Richtung jedes Zugangs zufällig ist, werden viele verschiedene Traversalsituationen gebildet. Gleichzeitig ist der Pfad zwischen den beiden zwei Punkten eindeutig, was ein anderes Labyrinth bildet, und es gibt nur einen einzigartigen Pfad vom Anfang bis zum Endpunkt. Dies wird durch die Eigenschaften des Tiefenquellenalgorithmus des Diagramms bestimmt. Bei der Implementierung des Algorithmus ist die Hauptsache, den Stapel zu verwenden. Drücken Sie zum ersten Mal zunächst den ersten Punkt in den Stapel. Jedes Mal, wenn ein Punkt zugegriffen wird, wird der Punkt in den Stapel gedrückt, dann zugreifen wir in vier Richtungen zufällig auf den Punkt oben im Stapel, drücken auf den neuen Punkt und dann auf den neuen Punkt ein. Sobald die vier Richtungen dieses Punktes nicht zugänglich sind, lassen Sie den Punkt aus dem Stapel zurückziehen und dann auf die vier Anweisungen des Punktes an der Spitze des Stapels und so weiter zugreifen. Bis alle Punkte im Stapelausgang werden unser Traversal erfolgreich sein. Dies ist ein rekursiver Prozess. Dieser Algorithmus kann natürlich durch rekursive Methoden implementiert werden. Ich mache das jedoch hier, implementiere es aber manuell mit einem Array als Stapel. Haha ~~ Nachdem ich so viel gesagt habe, weiß ich nicht, ob das, was ich ausdrücken möchte, zum Ausdruck gebracht wird. Ich bin jedoch der Meinung, dass mein spezifisches Codedesign nicht gut geschrieben ist, und es gibt immer noch viele Orte, an denen es mangelnde Verbesserungen und Optimierung gibt. Es ist nur eine Algorithmusübung. Im Folgenden sind die Kerncodes der beiden Schlüsselklassen aufgeführt. Was den Code der Präsentationsschicht betrifft, werde ich sie nicht veröffentlichen, weil diese sehr trivial sind.
Hier ist das Rendering:
Labyrinthklasse:
// Autor: ZhongZw // E -Mail: [email protected] Paket cn.zhongzw.model; Import Java.util.ArrayList; import Java.util.random; öffentliche Klasse Mazemodel {private int width = 0; Private int Höhe = 0; private random rnd = new random (); public mazemodel () {this.width = 50; // Labyrinthbreite this.height = 50; // Maze -Höhe} public int getWidth () {Rückkehr Breite; } public void setwidth (int width) {this.width = width; } public int getheight () {return Height; } public void setheight (int Höhe) {this.height = Höhe; } public mazemodel (int width, int height) {super (); this.width = width; this.height = Höhe; } public arrayList <Mazepoint> getMaze () {ArrayList <MazePoint> maze = new ArrayList <MazePoint> (); für (int H = 0; H <Höhe; H ++) {für (int w = 0; Maze.Add (Punkt); }} return CreateMaze (Maze); } private arrayList <Mazepoint> CreateMaze (ArrayList <MazePoint> Maze) {int top = 0; int x = 0; int y = 0; ArrayList <MazePoint> Team = new ArrayList <MazePoint> (); Team.Add (Maze.get (x + y * Breite)); while (top> = 0) {int [] val = new int [] {-1, -1, -1, -1}; int times = 0; boolesche Flagge = Falsch; Mazepoint pt = (Mazepoint) Team.get (top); x = pt.getX (); y = pt.gety (); pt.visted = true; RO1: während (Zeiten <4) {int dir = rnd.Nextint (4); if (val [dir] == Dir) Weiter; sonst Val [Dir] = Dir; Switch (dir) {case 0: // links if (x - 1)> = 0 && maza.get (x - 1 + y * width). Maze.get (x - 1 + y * Breite) .setRight (); Team.Add (Maze.get (x - 1 + y * Breite)); Top ++; Flag = wahr; RO1 brechen; } brechen; Fall 1: // rechts if ((x + 1) <width && mazaze.get (x + 1 + y * width). Maze.get (x + 1 + y * Breite) .setLeft (); Team.Add (Maze.get (x + 1 + y * Breite)); Top ++; Flag = wahr; RO1 brechen; } brechen; Fall 2: // if ((y - 1)> = 0 && mabe.get (x + (y - 1) * width). Maze.get (x + (y - 1) * Breite) .setdown (); Team.Add (Maze.get (x + (y - 1) * Breite)); Top ++; Flag = wahr; RO1 brechen; } brechen; Fall 3: // unten if if ((y + 1) <Höhe && Maze.get (x + (y + 1) * width). Maze.get (x + (y + 1) * Breite) .setUp (); Team.Add (Maze.get (x + (y + 1) * Breite)); Top ++; Flag = wahr; RO1 brechen; } brechen; } Zeiten += 1; } if (! flag) {team.remove (top); ober -= 1; }} return Maze; }}
Labyrinth
// Autor: ZhongZw // E -Mail: [email protected] Paket cn.zhongzw.model; import Java.util.*; Java.lang importieren.*; öffentliche Klasse MazePoint {private int links = 0; private int rechts = 0; private int up = 0; private int down = 0; Privat int x; privat int y; öffentlicher Booleschen Zeuge; public MazePoint (int x, int y) {this.x = x; this.y = y; } public int getleft () {return links; } public void setleft () {this.left = 1; } public int getright () {return rechts; } public void setright () {this.right = 1; } public int getup () {return up; } public void setup () {this.up = 1; } public int getdown () {return down; } public void setdown () {this.down = 1; } public int getX () {return x; } public void setx (int x) {this.x = x; } public int gety () {return y; } public void sety (int y) {this.y = y; }}
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.