Herkunft:
Letztes Jahr (erstes Semester der Junior High School) schrieb ich gern kleine Spiele, also wollte ich versuchen, ein Labyrinth zu schreiben.
Programmeffekte:
Drücken Sie Platz, um den Pfad anzuzeigen:
Denkprozess:
Das Labyrinth besteht aus Gittern, die nur einen Weg vom Eingang zum Ausgang erfordern.
Nachdem Sie über verschiedene Datenstrukturen nachgedacht haben, scheint es, dass Bäume besser geeignet sind, wobei nur ein Weg vom Wurzelknoten zu jedem untergeordneten Knoten geeignet ist. Unter der Annahme, dass der Eingang der Wurzelknoten und der Ausgang ein untergeordneter Knoten im Baum ist, ist der Pfad vom Wurzelknoten zum untergeordneten Knoten definitiv eindeutig.
Wenn also ein Baum gebaut werden kann, um alle Netze abzudecken, kann ein Labyrinth erstellt werden.
Darüber hinaus ist es erforderlich, dass die übergeordneten und untergeordneten Knoten des Baumes benachbarte Gitter an der Schnittstelle sein müssen.
Wenn die Schnittstelle angezeigt wird, kann ein Labyrinth gezeichnet werden, wenn die zwischen dem übergeordneten Knoten und dem untergeordneten Knoten geteilten Kanten nicht gezogen werden und andere Kanten gezogen werden.
Dann dachte ich darüber nach, wie man einen solchen Baum implementiert.
Die ersten beiden Fragen:
1. Wie repräsentieren Bäume?
2. Wie kann man diesen Baum konstruieren?
1. Wie repräsentieren Bäume?
Unter der Annahme, dass dieser Baum wie das Schreiben eines binären Baums implementiert ist, muss jeder Baumknoten eine Koordinate (x, y) speichern, um ein Netz darzustellen, und vier Zeiger müssen gespeichert werden. Einige Zeiger sind leer, andere nicht leer, und die Zeiger, die nicht leer sind, zeigen die Kinderknoten, und die Kinderknoten retten die Koordinaten des Nachbarnetzes. Das größte Problem dabei ist, dass es unmöglich ist zu bestimmen, ob sich alle Netze im Baum befinden. Vielleicht wird auch ein zweidimensionales Array als Flag-Array verwendet.
Angenommen, Sie verwenden ein zweidimensionales Array, um das Gitter des Labyrinths darzustellen. Jedes Array -Element speichert einen Verweis auf den übergeordneten Knoten, der auch einen virtuellen Baum bilden kann. Ein zweidimensionales Array von N*n repräsentiert also N*n Gitter, und jedes Array-Element (Gitter) hat einen Verweis auf den übergeordneten Knoten. Um die Koordinaten des Netzes leicht zu erhalten, müssen auch Koordinateninformationen gespeichert werden.
2. Wie kann man diesen Baum konstruieren?
Wählen Sie zuerst ein Raster als Stammknoten aus. Um die Form des Labyrinths zufällig genug zu machen, habe ich mich entschlossen, eine Koordinate als Stammknoten zufällig zu erzeugen. Tatsächlich ist es auch in Ordnung, eine Koordinate zu wählen, die bestimmt wird.
Wie füge ich diesen Baum Knoten hinzu?
Ich habe hier viele Umwege gemacht. Zuerst dachte ich an einen Algorithmus, der jetzt dem Backtracking ähnlich zu sein scheint (ich kannte den Backtracking -Algorithmus zu dieser Zeit nicht ...), aber die Zeitkomplexität ist sehr hoch. Wenn das Labyrinth 64*64 ist, wird der Algorithmus möglicherweise keine Ergebnisse erzielt.
Dann ist auch eine Methode zur Scan -Tiefensuche zurückzuführen. Jedes Mal, wenn ich scanne, finde ich einen Knoten im aktuellen Baum, um festzustellen, ob sich sein Nachbarnetz im Baum befindet. Wenn es nicht im Baum ist, fügen Sie das Nachbarnetz zum Baum hinzu. Wenn es sich bereits im Baum befindet, schauen Sie sich das nächste Nachbarnetz an. Wenn sich alle Nachbarnetze des Knotens im Baum befinden, suchen Sie den nächsten Knoten und setzen Sie denselben Betrieb fort. Um das Labyrinth zufällig erzeugt zu machen, ist die Startposition des Scans nur zufällig. Die nach dieser Methode erzeugten Wege im Labyrinth sind jedoch immer nicht tief genug, um den gewünschten und eingehenden Effekt zu haben, den ich möchte. Schließlich ist es eine ähnliche Methode wie die Breite. Darüber hinaus scheint es immer auf brutaler Gewalt zu tun, und der Algorithmus ist nicht klug und präzise genug.
Schließlich dachte ich schließlich daran, eine ausführliche Suche zu verwenden. . Wahrscheinlich, weil ich eine Datenstruktur seit einem Jahr gelernt habe und sie nicht zu sehr geübt habe, habe ich nie an diese erste Methode gedacht, an die ich denken sollte. .
Wählen Sie zufällig ein Raster als Stammknoten aus, beginnen Sie davon und suchen Sie in der Tiefe und öffnen Sie einen Weg, bis es keine Möglichkeit gibt, einen Schritt zurückzuziehen, einen anderen Weg zu ändern und dann nicht mehr zu gehen, einen Schritt zurückzutreten, einen anderen zu ändern ... Dieser Zyklus geht weiter, bis keine Möglichkeit zu gehen ist. . . Tatsächlich ist es immer noch zurück.
Im Programm ist der folgende Vorgang (siehe die Funktion createMaze () im Code für Details):
Wählen Sie zufällig ein Raster als Stammknoten aus und drücken Sie es in den Stapel.
Führen Sie dann die folgende Schleife aus, wenn der Stapel nicht leer ist:
Nehmen Sie ein Raster heraus, setzen Sie seine Intree -Flagge auf 1 und schieben Sie alle seine Nachbarnetze, die nicht im Baum sind, in den Stapel (Geschichten zufällig) und lassen Sie den Vater dieser Nachbarnetze auf das Raster zeigen.
Nach der Lösung dieser beiden Probleme sind der Rest der Labyrinthe, die Anzeige von Pfaden und bewegliche Kugeln relativ einfach.
Code
Paket -Maze; Import Java.awt.Color; Import Java.awt.graphics; Import Java.awt.event.Keyadapter; javax.swing.jpanel; Klasse -Gitter {statische endgültige intree = 1; statische endgültige int notintree = 0; private int x = -1; private int y = -1; private int flag = notintree; privates Gitter Vater = Null; public gitter (int xx, int yy) {x = xx; y = yy; } public int getX () {return x; } public int gety () {return y; } public int getflag () {return flag; } public gitter getFather () {return father; } public void setfather (Gitter f) {father = f; } public void setflag (int f) {flag = f; } public String toString () {return New String ("(" + x + "," + y + ")/n"); }} public Class Maze erweitert JPanel {private statische endgültige lange Serialversionuid = -8300339045454852626L; Private int num, Breite, Polsterung; // Breite die Breite und Höhe jedes Gitters Private Gitter [] [] Labyrinth; Privat int Ballx, Bally; privat boolean DrawPath = Falsch; Maze (int m, int wi, int p) {num = m; width = wi; Polster = P; Maze = neues Gitter [num] [num]; für (int i = 0; i <= num- 1; i ++) für (int j = 0; j <= num- 1; j ++) labyrinth [i] [j] = neues Gitter (i, j); CreateMaze (); setKeyListener (); this.setfocuSable (true); } private void init () {für (int i = 0; i <= num- 1; i ++) für (int j = 0; j <= num- 1; j ++) {Maze [i] [j] .setFather (null); Maze [i] [j] .setflag (gitter.notintree); } ballx = 0; Bally = 0; DrawPath = falsch; CreateMaze (); // setKeyListener (); this.setfocuSable (true); Repaint (); } public int getCenterx (int x) {return padding + x * width + width / 2; } public int GetCenter (int y) {return padding + y * width + width / 2; } public int getCenterx (Gitter p) {return padding + p.gety () * width + width / 2; } public int getCentery (Gitter p) {return padding + p.getX () * Breite + Breite / 2; } private void checkiswin () {if (ballx == num- 1 && bally == num- 1) {joptionpane.showMessagedialog (null, "du gewinnst!", "Du bist aus dem Labyrinth ausgewiesen.", JoptionPane.plain_message); init (); }} synchronisierte private void move (int c) {int tx = ballx, ty = bally; // system.out.println (c); Switch (c) {case keyEvent.vk_left: ty--; brechen; case keyEvent.vk_right: ty ++; brechen; case keyEvent.vk_up: tx--; brechen; case keyEvent.vk_down: tx ++; brechen; case keyEvent.vk_space: if (DrawPath == true) {DrawPath = false; } else {DrawPath = true; } brechen; Standard:} if (! isoutOfBorder (tx, ty) && (Maze [tx] [ty] .Getfather () == Maze [Ballx] [Bally] || Maze [Ballx] [bally] .Getfather () == Maze [tx] [ty]) {ballx = tx; Bally = ty; }} private void setKeyListener () {this.addKeyListener (neuer KeyAdapter () {public void keypressed (keyEvent e) {int c = e.getKeyCode (); Move (c); repaint (); checkiswin ();}}); } private boolean isoutOfBorder (Gitter p) {return isoutOfBorder (p.getX (), p.gety ()); } private boolean isoutOfBorder (int x, int y) {return (x> num - 1 || y> num - 1 || x <0 || y <0)? wahr: falsch; } private Gitter [] getneis (Gitter p) {Final int [] fügt = {-1, 0, 1, 0, -1}; // Die Reihenfolge ist oberen, rechts, links, if (isoutOfBorder (p)) {return null; } Gitter [] ps = neues Gitter [4]; // Die Reihenfolge ist oberen, rechts, links, int XT; int yt; für (int i = 0; i <= 3; i ++) {xt = p.getX ()+fügt [i] hinzu; yt = p.gety () + fügt [i + 1] hinzu; if (isoutOfBorder (XT, yt)) fortsetzen; PS [i] = Maze [XT] [yt]; } return ps; } private void CreateMaze () {random randomy = new randal (); int rx = math.abs (random.nextint ()) % num; int ry = math.abs (random.nextint ()) % num; Stack <Pon <Pon <Pon <Pon <-Glattice> Gitter p = Maze [rx] [ry]; Gitter neis [] = null; S.Push (p); while (! P.SetFlag (Gitter.inTree); neis = getneis (p); int ran = math.abs (random.nextint ()) % 4; für (int a = 0; a <= 3; a ++) {ran ++; Ran %= 4; if (neis [ran] == null || neis [ran] .getFlag () == gitter.inTree) Weiter; S.Push (Neis [Ran]); Neis [Ran] .SetFather (P); }} // ändern (Maze [0] [0], null); } Private void ChangeFather (Gitter P, Gitter f) {if (p.getFather () == null) {P.SetFather (f); zurückkehren; } else {ChangeFather (p.getFather (), p); } · if (sx! = dx) {sx ++; dx--; } else {sy ++; Dy--; } g.drawline (sx, sy, dx, dy); } Protected void PaintComponent (Grafik g) {Super.PaintComponent (g); für (int i = 0; i <= num; i ++) {g.drawline (padding + i * width, padding, polsting + i * width, padding + num * width); } für (int j = 0; j <= num; j ++) {g.drawline (padding, padding + j * width, padding + num * width, padding + j * width); } G.SetColor (this.getbackground ()); für (int i = num-1; i> = 0; i--) {für (int j = num-1; j> = 0; j-) {gitter f = maby [i] [j] .GetFather (); if (f! = null) {int fx = f.getX (), fy = f.gety (); Clearfence (i, j, fx, fy, g); }}} g.drawline (Polsterung, Polsterung + 1, Polsterung, Polster + Breite - 1); int last = padding + num * width; g.drawline (letztes, letztes - 1, letztes, letztes - Breite + 1); G.SetColor (color.red); G.Filloval (GetCenterx (Bally) - Breite / 3, GetCentery (Ballx) - Breite / 3, Breite / 2, Breite / 2); if (DrawPath == True) DrawPath (g); } private void DrawPath (Graphics g) {color path_color = color.orange, botath_color = color.pink; if (DrawPath == true) G.SetColor (path_color); sonst G.SetColor (this.getbackground ()); Gitter p = Maze [num - 1] [num - 1]; while (p.getFather ()! = null) {P.Setflag (2); p = p.getFather (); } g.filloval (GetCenterx (p) - Breite / 3, GetCentery (P) - Breite / 3, Breite / 2, Breite / 2); P = Maze [0] [0]; while (p.getFather ()! = null) {if (p.getFlag () == 2) {P.Setflag (3); G.SetColor (Both_Path_Color); } g.drawline (GetCenterx (P), GetCentery (P), GetCenterx (p.getFather ()), GetCentery (p.getFather ()); p = p.getFather (); } g.setColor (path_color); p = Maze [num - 1] [num - 1]; while (p.getFather ()! = null) {if (p.getFlag () == 3) break; G.Drawline (GetCenterx (P), GetCentery (P), GetCenterx (p.getFather ()), GetCentery (p.getFather ()); p = p.getFather (); }} public static void main (String [] args) {endgültig int n = 30, width = 600, padding = 20, lx = 200, ly = 100; Jpanel P = neues Maze (N, (Breite - Polster - Polster) / N, Polsterung); JFrame Fram = new JFrame ("Maze (SHAUBEMENDE UND VERSCHAUSEN SCHWEISUNGEN)"); Frame.GetContentPane (). add (p); Frame.SetDefaultCloseOperation (jframe.exit_on_close); Frame.SetSize (Breite + Polsterung, Breite + Polsterung + Polsterung); Frame.SetLocation (LX, LY); Frame.SetVisible (True); }}