Recientemente, a menudo veo a mis compañeros de clase jugando un juego de laberinto en la sala de computadoras. Es bastante interesante. También uso Java para escribir un algoritmo para implementar la generación aleatoria de laberintos. De hecho, es un algoritmo de recorrido de profundidad para un gráfico. La idea básica es que cada punto del laberinto tiene cuatro paredes, y luego.
1. Comience el acceso desde cualquier punto (mi algoritmo se fija para comenzar desde el punto (0,0)) y visite una aleatoria de las cuatro direcciones (cada vez que accede a un punto accesible, retire la pared en esa dirección de ese punto), y el punto de acceso continúa accediendo a ella en esta dirección.
2. Cada punto visitado se identifica como se accede. Cuando un punto accede a una determinada dirección, primero determinaremos si se ha accedido al punto de acceso o toca el límite. Si se ha accedido a las cuatro instrucciones del punto o no pueden acceder, regrese al punto anterior. El punto anterior continúa el proceso.
Después del recorrido de esta manera, se puede confirmar que se ha visitado cada punto. Además, dado que la dirección de cada acceso es aleatoria, se formarán muchas situaciones de recorrido diferentes. Al mismo tiempo, el camino entre cada dos puntos es único, que forma un laberinto diferente, y solo hay un camino único desde el punto de inicio hasta el punto final. Esto está determinado por las características del algoritmo transversal de profundidad del gráfico. En la implementación del algoritmo, lo principal es usar la pila. La primera vez, primero presione el primer punto en la pila. Cada vez que se accede a un punto, el punto se empuja a la pila, luego accedemos al azar al punto en la parte superior de la pila en cuatro direcciones, accede al nuevo punto y luego presionamos el nuevo punto. Una vez que las cuatro direcciones de este punto son inaccesibles, deje que el punto se retire de la pila y luego acceda a las cuatro direcciones del punto en la parte superior de la pila, y así sucesivamente. Hasta que todos los puntos en la salida de la pila, nuestro recorrido tendrá éxito. Este es un proceso recursivo. Este algoritmo puede implementarse naturalmente mediante métodos recursivos. Sin embargo, hago esto aquí, pero lo implemento manualmente con una matriz como pila. Jaja ~~ Después de decir tanto, no sé si se expresa lo que quiero expresar. Sin embargo, creo que mi diseño de código específico no está bien escrito, y todavía hay muchos lugares donde hay una falta de mejora y optimización. Es solo para ser un ejercicio de algoritmo. Los siguientes son los códigos centrales de las dos clases clave. En cuanto al código de la capa de presentación, no los publicaré porque son muy triviales.
Aquí está la representación:
Clase de laberinto:
// Autor: Zhongzw // Correo electrónico: [email protected] Paquete CN.ZhongZW.Model; import java.util.arrayList; import java.util.random; clase pública Mazemodel {private int width = 0; Private int altura = 0; RND aleatorio privado = new Random (); public Mazemodel () {this.width = 50; // ancho de laberinto this.Height = 50; // altura de laberinto} public int getWidth () {return width; } public void setWidth (int width) {this.width = width; } public int getheight () {altura de retorno; } public void setheight (int altura) {this.height = altura; } public Mazemodel (int ancho, int altura) {super (); this.width = ancho; this.Height = altura; } Public ArrayList <MazePoint> getMaze () {ArrayList <MazePoint> Maze = New ArrayList <MazePoint> (); para (int h = 0; h <altura; h ++) {for (int w = 0; w <width; w ++) {mazePoint Point = new MazePoint (w, h); laberinto.add (punto); }} return createMaze (laberinto); } 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 * ancho)); while (top> = 0) {int [] val = new int [] {-1, -1, -1, -1}; intimes = 0; bandera booleana = falso; MazePoint PT = (MazePoint) Team.get (arriba); x = pt.getx (); y = pt.gety (); pt.visted = true; RO1: while (Times <4) {int dir = rnd.nextint (4); if (val [dir] == dir) continuar; más val [dir] = dir; switch (dir) {case 0: // izquierda if ((x - 1)> = 0 && maze.get (x - 1 + y * ancho) .visted == falso) {maze.get (x + y * width) .setleft (); Maze.get (x - 1 + y * ancho) .setRight (); Team.add (Maze.get (x - 1 + y * ancho)); superior ++; bandera = verdadero; romper RO1; } romper; Caso 1: // derecho if ((x + 1) <width && maze.get (x + 1 + y * ancho) .visted == false) {maze.get (x + y * width) .setRight (); Maze.get (x + 1 + y * ancho) .setleft (); Team.add (Maze.get (x + 1 + y * ancho)); superior ++; bandera = verdadero; romper RO1; } romper; caso 2: // if ((y - 1)> = 0 && maze.get (x + (y - 1) * ancho) .visted == false) {maze.get (x + y * width) .setup (); Maze.get (x + (y - 1) * ancho) .setdown (); Team.add (Maze.get (x + (y - 1) * ancho)); superior ++; bandera = verdadero; romper RO1; } romper; Caso 3: // abajo if ((y + 1) <Height && Maze.get (x + (y + 1) * ancho) .visted == false) {maze.get (x + y * width) .setdown (); Maze.get (x + (y + 1) * ancho) .setup (); Team.add (Maze.get (x + (y + 1) * ancho)); superior ++; bandera = verdadero; romper RO1; } romper; } tiempos += 1; } if (! flag) {team.remove (arriba); arriba -= 1; }} return Maze; }}
laberinto
// Autor: Zhongzw // Correo electrónico: [email protected] Paquete CN.ZhongZW.Model; import java.util.*; import java.lang.*; clase pública mazePoint {private int izquierdó con = 0; Private int Right = 0; privado int up = 0; Private int down = 0; privado int x; privado int y; Booleano público testigo; public MazePoint (int x, int y) {this.x = x; this.y = y; } public int getleft () {return a la izquierda; } public void setleft () {this.left = 1; } public int getRight () {return Right; } 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; }}
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.