origen:
El año pasado (primer semestre de la escuela secundaria), me gustó escribir pequeños juegos, así que quería intentar escribir un laberinto.
Efectos del programa:
Presione el espacio para mostrar la ruta:
Proceso de pensamiento:
El laberinto consiste en cuadrículas, que requieren solo un camino desde la entrada a la salida.
Después de pensar en varias estructuras de datos, parece que los árboles son más adecuados, con solo una ruta desde el nodo raíz hasta cada nodo infantil. Suponiendo que la entrada es el nodo raíz y la salida es un nodo infantil en el árbol, entonces la ruta desde el nodo raíz hasta el nodo secundario es definitivamente único.
Entonces, si se puede construir un árbol para cubrir todas las cuadrículas, se puede crear un laberinto.
Además, se requiere que los nodos padre e hijos del árbol sean cuadrículas adyacentes en la interfaz.
Al mostrar la interfaz, si no se dibujan los bordes compartidos entre el nodo principal y el nodo secundario, y se dibujan otros bordes, se puede dibujar un laberinto.
Entonces pensé en cómo implementar un árbol de este tipo.
Las dos primeras preguntas:
1. ¿Cómo representan los árboles?
2. ¿Cómo construir este árbol?
1. ¿Cómo representan los árboles?
Suponiendo que este árbol se implementa como escribir un árbol binario, cada nodo de árbol necesita almacenar una coordenada (x, y) para representar una cuadrícula, y se deben almacenar cuatro punteros. Algunos punteros están vacíos, otros no están vacíos, y los punteros que no están vacíos apuntan a los nodos infantiles, y los nodos infantiles salvan las coordenadas de la cuadrícula vecina. El mayor problema para hacer esto es que es imposible determinar si todas las cuadrículas están en el árbol. Tal vez una matriz bidimensional también se usa como una matriz de bandera.
Supongamos que usa una matriz bidimensional para representar la cuadrícula del laberinto. Cada elemento de matriz almacena una referencia al nodo principal, que también puede formar un árbol virtual. Entonces, una matriz bidimensional de N*n representa N*n cuadrículas, y cada elemento de matriz (celosía) tiene una referencia al nodo principal. Además, para obtener fácilmente las coordenadas de la cuadrícula, también se debe guardar la información de las coordenadas.
2. ¿Cómo construir este árbol?
Primero seleccione una cuadrícula como nodo raíz. Para hacer que la forma del laberinto lo sea lo suficientemente aleatoria, elegí generar aleatoriamente una coordenada como nodo raíz. De hecho, también está bien elegir una coordenada determinada.
Entonces, ¿cómo agregar nodos a este árbol?
Tomé muchos desvíos aquí. Al principio pensé en un algoritmo que parece ser similar al retroceso ahora (no sabía el algoritmo de retroceso en ese momento ...), pero la complejidad del tiempo es muy alta. Quizás cuando el laberinto sea 64*64, el algoritmo no producirá ningún resultado.
Luego, un método de búsqueda de profundidad de escaneo también es retroceder. Cada vez que escaneo, encuentro un nodo en el árbol actual para ver si su cuadrícula vecina está en el árbol. Si no está en el árbol, agregue la cuadrícula vecina al árbol. Si ya está en el árbol, mire la próxima cuadrícula vecina. Si todas las cuadrículas vecinas del nodo están en el árbol, encuentre el siguiente nodo y continúe la misma operación. Además, para que el laberinto se genere aleatoriamente, la posición de inicio del escaneo es simplemente aleatoria. Sin embargo, los caminos en el laberinto generado por este método siempre no son lo suficientemente profundos como para tener el efecto tortuoso y profundo que quiero. Después de todo, es un método similar a la búsqueda de amplitud. Además, hacer esto siempre parece depender de la fuerza bruta, y el algoritmo no es lo suficientemente inteligente y conciso.
Finalmente, finalmente pensé en usar una búsqueda en profundidad. . Probablemente porque he aprendido la estructura de datos durante un año y no la he practicado demasiado, nunca he pensado en este primer método que debería pensar. .
Seleccione aleatoriamente una cuadrícula como el nodo raíz, comience desde él y busque en profundidad, y abra una forma hasta que no haya camino por recorrer, retire un paso, cambie de otra manera y luego camine a ninguna manera, dar un paso atrás, cambiar otro ... este ciclo continúa hasta que no haya camino por recorrer. . . De hecho, todavía está retrocediendo.
En el programa, el siguiente proceso es (consulte la función CreateMaze () en el código para más detalles):
Seleccione aleatoriamente una cuadrícula como el nodo raíz y empújalo en la pila.
Luego ejecute el siguiente bucle cuando la pila no esté vacía:
Saque una cuadrícula, coloque su bandera de Introe en 1, luego empuje todas sus cuadrículas vecinas que no están en el árbol hacia la pila (historias al azar), y deje que el padre de estas cuadrículas vecinos apunte a la cuadrícula.
Después de resolver estos dos problemas, el resto del dibujo de los laberintos, la visualización de rutas y las bolas en movimiento son relativamente simples.
Código
MAZA DE PAQUETES; import java.awt.color; import java.awt.graphics; import java.awt.event.keyAdapter; import java.awt.event.keyevent; import java.util.random; import java.util.stack; import javax.swing.jframe; import javax.swing.Jope; javax.swing.jpanel; class Lattice {static final int intree = 1; estático final int noTinTree = 0; private int x = -1; private int y = -1; Private int Flag = NotIntree; Padre de celosía privada = nulo; Public Lattice (int xx, int yy) {x = xx; y = yy; } public int getx () {return x; } public int gety () {return y; } public int getFlag () {return flag; } Public Lattice GetFather () {Return Padre; } public void setfather (lattice f) {padre = f; } public void setflag (int f) {flag = f; } public string toString () {return new String ("(" + x + "," + y + ")/n"); }} El laberinto de clase pública se extiende jpanel {privado estático final long serialversionUid = -8300339045454852626l; Private int Private int Ballx, Bally; shardpath privado booleano = falso; Maze (int m, int wi, int p) {num = m; ancho = wi; relleno = P; laberinto = nueva celosía [num] [num]; para (int i = 0; i <= num- 1; i ++) para (int j = 0; j <= num- 1; j ++) laberinto [i] [j] = nueva red (i, j); createMaze (); setKeylistener (); this.setFocusable (verdadero); } private void init () {for (int i = 0; i <= num- 1; i ++) para (int j = 0; j <= num- 1; j ++) {laberinto [i] [j] .setfather (null); laberinto [i] [j] .setFlag (Lattice.notintree); } ballx = 0; bally = 0; DrawPath = falso; createMaze (); // setKeylistener (); this.setFocusable (verdadero); repintado (); } public int getCenterx (int x) {return Padding + x * ancho + ancho / 2; } public int } public int getCenterx (Lattice P) {return Padding + p.gety () * ancho + ancho / 2; } public int } private void checkiswin () {if (ballx == num- 1 && bally == num- 1) {joptionPane.ShowMessEdialog (nulo, "¡Ganas!", "Saliste del laberinto", JoptionPane.Plain_Message); init (); }} movimiento sincronizado privado vacío (int c) {int tx = ballx, ty = bally; // System.out.println (c); switch (c) {case keyEvent.vk_left: ty--; romper; Caso KeyEvent.vk_right: Ty ++; romper; Caso KeyEvent.vk_up: TX--; romper; caso KeyEvent.vk_down: TX ++; romper; Caso KeyEvent.vk_space: if (drawPath == true) {drawPath = false; } else {drawPath = true; } romper; Valor predeterminado:} if (! IsoUtofBorder (tx, ty) && (maze [tx] [ty] .getFather () == Maze [Ballx] [Bally] || Maze [Ballx] [Bally] .getFather () == Maze [TX] [Ty]) {Ballx = tx; bally = ty; }} private void setKeListener () {this.AddkeyListener (new KeyAdapter () {public void keyPressed (keyEvent e) {int c = e.getKeyCode (); Move (c); repint (); checkiswin ();}}); } boolean privado isoutofborder (Lattice P) {return isouToFborder (p.getx (), p.gety ()); } boolean privado isoutofborder (int x, int y) {return (x> num - 1 || y> num - 1 || x <0 || y <0)? verdadero: falso; } Lattice privado [] getNeis (Lattice P) {final int [] adds = {-1, 0, 1, 0, -1}; // El orden es superior, derecha, izquierda, if (isoutofborder (p)) {return null; } Redes [] ps = nueva red [4]; // El orden es superior, derecha, izquierda, int xt; int Yt; for (int i = 0; i <= 3; i ++) {xt = p.getx ()+agrega [i]; yt = p.gety () + agrega [i + 1]; if (isoutofborder (xt, yt)) continuar; ps [i] = Maze [xt] [yt]; } return PS; } private void createMaze () {Random Random = new Random (); int rx = math.abs (random.nextInt ()) % num; int ry = math.abs (random.nextint ()) % num; Pila <lattice> s = nueva pila <lattice> (); Lattice P = Maze [rx] [ry]; Lattice Neis [] = NULL; s.push (p); while (! s.isEmpty ()) {p = s.pop (); p.setFlag (Lattice.Intree); neis = getNeis (p); int ran = Math.abs (Random.NextInt ()) % 4; para (int a = 0; a <= 3; a ++) {ran ++; corrió %= 4; if (neis [ran] == null || neis [ran] .getFlag () == Lattice.Intree) Continuar; s.push (neis [ran]); neis [ran] .setfather (p); }} // ChangeMather (laberinto [0] [0], nulo); } private void ChangeMather (Lattice P, Lattice f) {if (p.getFather () == null) {p.setfather (f); devolver; } else {ChangeMather (p.getFather (), p); }} private void clearfence (int i, int j, int fx, int fy, gráficos g) {int sx = padding + ((j> fy? j: fy) * width), sy = padding + ((i> fx? i: fx) * width), dx = (i == fx? SX + width), dy = (i == fx? Syth); if (sx! = dx) {sx ++; dx--; } else {sy ++; dy--; } G.Drawline (SX, SY, DX, DY); } protegido void pintarComponent (Graphics g) {super.PaintComponent (g); para (int i = 0; i <= num; i ++) {g.drawline (relleno + i * ancho, relleno, relleno + i * ancho, relleno + num * ancho); } para (int j = 0; j <= num; j ++) {g.drawline (relleno, relleno + j * ancho, relleno + num * ancho, relleno + j * ancho); } G.SetColor (this.getBackground ()); for (int i = num-1; i> = 0; i--) {for (int j = num-1; j> = 0; j--) {Lattice f = Maze [i] [j] .getfather (); if (f! = null) {int fx = f.getx (), fy = f.gety (); Clearfence (i, j, fx, fy, g); }}} g.drawline (relleno, relleno + 1, relleno, relleno + ancho - 1); int último = padding + num * ancho; G.Drawline (último, último - 1, último, último - ancho + 1); G.SetColor (Color.Red); G.Filloval (GetCenterx (Bally) - ancho / 3, getCentery (ballx) - ancho / 3, ancho / 2, ancho / 2); if (drawpath == true) DrawPath (g); } private void drawpath (Graphics g) {color path_color = color.orange, bull_path_color = color.pink; if (drawPath == true) G.SetColor (Path_Color); else G.SetColor (this.getBackground ()); Vuelve p = laberinto [num - 1] [num - 1]; while (p.getFather ()! = null) {p.setFlag (2); p = p.getFather (); } g.filloval (getCenterx (p) - ancho / 3, getCentery (p) - ancho / 3, ancho / 2, ancho / 2); p = laberinto [0] [0]; while (p.getFather ()! = null) {if (p.getFlag () == 2) {p.setFlag (3); G.SetColor (BOLT_PATH_COLOR); } G.Drawline (GetCenterx (P), GetCentery (P), GetCenterx (P.GetFather ()), GetCentery (P.GetFather ())); p = p.getFather (); } G.SetColor (Path_Color); p = laberinto [num - 1] [num - 1]; while (p.getFather ()! = null) {if (p.getFlag () == 3) ruptura; G.Drawline (GetCenterx (P), GetCentery (P), GetCenterx (P.GetFather ()), GetCentery (P.GetFather ())); p = p.getFather (); }} public static void main (string [] args) {final int n = 30, ancho = 600, padding = 20, lx = 200, ly = 100; Jpanel p = nuevo laberinto (n, (ancho - relleno - relleno) / n, relleno); Jframe marco = nuevo Jframe ("Maze (mostrar u ocultar rutas por barra espacial)"); frame.getContentPane (). add (p); Frame.setDefaultCloseOperation (jframe.exit_on_close); Frame.setsize (ancho + relleno, ancho + relleno + relleno); Frame.setLocation (lx, ly); Frame.SetVisible (verdadero); }}