origem:
No ano passado (primeiro semestre do ensino médio), eu gostava de escrever pequenos jogos, então queria tentar escrever um labirinto.
Efeitos do programa:
Pressione espaço para exibir o caminho:
Processo de pensamento:
O labirinto consiste em grades, exigindo apenas um caminho da entrada da saída.
Depois de pensar em várias estruturas de dados, parece que as árvores são mais adequadas, com apenas um caminho do nó raiz para cada nó infantil. Supondo que a entrada seja o nó raiz e a saída seja um nó infantil na árvore, o caminho do nó raiz para o nó infantil é definitivamente único.
Portanto, se uma árvore puder ser construída para cobrir todas as grades, um labirinto poderá ser criado.
Além disso, é necessário que os nós pais e filho da árvore sejam grades adjacentes na interface.
Ao exibir a interface, se as bordas compartilhadas entre o nó pai e o nó filho não forem desenhadas e outras bordas forem desenhadas, um labirinto poderá ser desenhado.
Então pensei em como implementar uma árvore assim.
As duas primeiras perguntas:
1. Como as árvores representam?
2. Como construir esta árvore?
1. Como as árvores representam?
Supondo que essa árvore seja implementada como escrever uma árvore binária, cada nó da árvore precisa armazenar uma coordenada (x, y) para representar uma grade e quatro ponteiros devem ser armazenados. Alguns ponteiros estão vazios, outros não estão vazios e os ponteiros que não estão vazios para os nós filhos, e os nós filhos salvam as coordenadas da grade vizinha. O maior problema de fazer isso é que é impossível determinar se todas as grades estão na árvore. Talvez uma matriz bidimensional também seja usada como uma matriz de sinalizador.
Suponha que você use uma matriz bidimensional para representar a grade do labirinto. Cada elemento da matriz armazena uma referência ao nó pai, que também pode formar uma árvore virtual. Portanto, uma matriz bidimensional de n*n representa n*n grades, e cada elemento de matriz (treliça) tem uma referência ao nó pai. Além disso, para obter facilmente as coordenadas da grade, as informações de coordenadas também devem ser salvas.
2. Como construir esta árvore?
Primeiro, selecione uma grade como o nó raiz. Para fazer a forma do labirinto aleatório o suficiente, escolhi gerar aleatoriamente uma coordenada como o nó raiz. De fato, também não há problema em escolher uma coordenada que seja determinada.
Então, como adicionar nós a esta árvore?
Eu fiz muitos desvios aqui. No começo, pensei em um algoritmo que parece ser semelhante ao retorno agora (não conhecia o algoritmo de retrocesso naquele momento ...), mas a complexidade do tempo é muito alta. Talvez quando o labirinto seja de 64*64, o algoritmo não produzirá nenhum resultado.
Em seguida, um método de pesquisa em profundidade de varredura também está voltando. Cada vez que digito, encontro um nó na árvore atual para ver se a grade vizinha está na árvore. Se não estiver na árvore, adicione a grade vizinha à árvore. Se já estiver na árvore, olhe para a próxima grade vizinha. Se todas as grades vizinhas do nó estiverem na árvore, encontre o próximo nó e continue a mesma operação. Além disso, para tornar o labirinto gerado aleatoriamente, a posição inicial da varredura é apenas aleatória. No entanto, os caminhos no labirinto gerado por esse método nem sempre são profundos o suficiente para ter o efeito tortuoso e aprofundado que eu desejo. Afinal, é um método semelhante à pesquisa de amplitude. Além disso, isso sempre parece confiar na força bruta, e o algoritmo não é inteligente e conciso o suficiente.
Finalmente, finalmente pensei em usar pesquisas detalhadas. . Provavelmente porque aprendi a estrutura de dados há um ano e não a pratiquei muito, nunca pensei nesse primeiro método que deveria pensar. .
Selecione aleatoriamente uma grade como o nó raiz, comece e pesquise em profundidade e abra uma maneira até que não haja caminho, retire um passo, mude de outra maneira e depois caminhe para não ir, dê um passo para trás, mude outro ... esse ciclo continua até que não haja caminho. . . Na verdade, ainda está voltando.
No programa, o processo a seguir é (consulte a função CreateMaze () no código para obter detalhes):
Selecione aleatoriamente uma grade como nó raiz e empurre -a para a pilha.
Em seguida, execute o seguinte loop quando a pilha não estiver vazia:
Pegue uma grade, coloque sua bandeira intree como 1 e depois empurre todas as suas grades vizinhas que não estão na árvore na pilha (histórias aleatoriamente) e deixe o pai dessas grades vizinhas apontar para a grade.
Depois de resolver esses dois problemas, o restante do desenho de labirintos, exibindo caminhos e bolas em movimento são relativamente simples.
Código
pacote labirinto; importar java.awt.color; importar java.awt.graphics; importar java.awt.event.keyadapter; importar java.awt.event.keyevent; import java.util.portom; import java.ut.tack.stack; import.javane.jAxtion; importandom; importa java.ut.stack.stack; import.javax.jAxtion.jftion; importação; importação; imports; javax.swing.jpanel; classe Lattice {estático final int intee = 1; estático final int notintree = 0; private int x = -1; private int y = -1; private int sinalizador = notintiTree; Pai da rede privada = nulo; Lattice público (int xx, int yy) {x = xx; y = yy; } public int getx () {return x; } public int gety () {return y; } public int getFlag () {retornar sinalizador; } public Lattice getfather () {Return Pai; } public void Setfather (Lattice f) {pai = f; } public void setFlag (int f) {flag = f; } public string tostring () {return new string ("(" + x + "," + y + ")/n"); }} classe pública Maze estende JPanel {private estático final serialversionuid = -8300339045454852626l; privado int num, largura, preenchimento; // largura a largura e altura de cada rede de treliça privada da grade [] [] labirinto; Privado Int Ballx, Bally; private boolean drawPath = false; Maze (int m, int wi, int p) {num = m; largura = wi; preenchimento = p; labirinto = nova rede [num] [num]; for (int i = 0; i <= num- 1; i ++) para (int j = 0; j <= num- 1; j ++) labirinto [i] [j] = nova rede (i, j); createMaze (); setKeyListener (); this.setFocusable (true); } private void init () {for (int i = 0; i <= num- 1; i ++) para (int j = 0; j <= num- 1; j ++) {Maze [i] [j] .setfather (null); labirinto [i] [j] .setflag (treliça.Notintree); } ballx = 0; bally = 0; drawPath = false; createMaze (); // setKeyListener (); this.setFocusable (true); repintar (); } public int getCenterx (int x) {return preenchimento + x * width + width / 2; } public int getCentery (int y) {return preenchimento + y * width + width / 2; } public int getCenterx (Lattice p) {return preenchimento + p.gety () * width + width / 2; } public int getCentery (Lattice p) {return predding + p.getx () * width + width / 2; } private void checkInwin () {if (ballx == num- 1 && bally == num- 1) {joptionpane.showMessagedialog (null, "você ganha!", "Você saiu do labirinto.", JoptionPane.Plain_Message); init (); }} Sincronizada private void move (int c) {int tx = ballx, ty = bally; // System.out.println (c); switch (c) {case keyevent.vk_left: ty--; quebrar; case keyevent.vk_right: ty ++; quebrar; case keyevent.vk_up: tx--; quebrar; case keyevent.vk_down: tx ++; quebrar; case keyevent.vk_space: if (drawPath == true) {drawPath = false; } else {drawPath = true; } quebrar; Padrão:} if (! isoutofborder (tx, ty) && (Maze [tx] [ty] .getfather () == Maze [ballx] [Bally] || bally = ty; }} private void setKeyListener () {this.addkeyListener (new KeyAdapter () {public void keyPressed (KeyEvent e) {int c = e.getKeyCode (); move (c); repont (); checkInwin ();}}); } private boolean isoutofborder (treliça 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)? Verdadeiro: falso; } malha privada [] getNeis (Lattice p) {final int [] adiciona = {-1, 0, 1, 0, -1}; // a ordem é superior, direita, esquerda, if (isouTofborder (p)) {return null; } Lattice [] ps = nova rede [4]; // A ordem é superior, direita, esquerda, int xt; int yt; for (int i = 0; i <= 3; i ++) {xt = p.getx ()+adiciona [i]; yt = p.gety () + adiciona [i + 1]; if (isoutofborder (xt, yt)) continuar; ps [i] = labirinto [xt] [yt]; } retornar ps; } private void CreateMaze () {aleatória Random = new Random (); int rx = Math.abs (aleatoriamente.nextInt ()) % num; int ry = Math.abs (aleatom.nextInt ()) % num; Stack <Lattice> s = nova pilha <Lattice> (); Lattice p = labirinto [rx] [ry]; Lattice neis [] = nulo; S.Push (P); while (! p.setFlag (Lattice.Intree); neis = getNeis (P); int ran = Math.abs (aleatoriamente.nextInt ()) % 4; for (int a = 0; a <= 3; a ++) {ran ++; correu %= 4; if (neis [ran] == null || neis [ran] .getflag () == Lattice.intree) continue; s.push (neis [ran]); Neis [Ran] .Setfather (P); }} // changefather (labirinto [0] [0], nulo); } troca privada de void (treliça P, treliça f) {if (p.getfather () == null) {p.setfather (f); retornar; } else {changefather (p.getfather (), p); }} Void privado clearfence (int i, int j, int fx, int fy, gráficos g) {int sx = preenchimento + ((j> fy? j: fy) * largura), sy = preenchimento + (i wush> fx? i: fx) * largura), dx = (i == fx? sx + width), dyn = fx) * largura), dx = (i == fx? sx + width), dyn), (i / fx? if (sx! = dx) {sx ++; dx--; } else {sy ++; dy--; } G.Drawline (SX, SY, DX, DY); } Void PaintComponent protegido (gráficos g) {super.paintcomponent (g); for (int i = 0; i <= num; i ++) {g.drawline (preenchimento + i * largura, preenchimento, preenchimento + i * largura, preenchimento + num * largura); } para (int j = 0; j <= num; j ++) {g.drawline (preenchimento, preenchimento + j * largura, preenchimento + num * largura, preenchimento + j * width); } g.setColor (this.getbackground ()); for (int i = num-1; i> = 0; i-) {for (int j = num-1; j> = 0; j--) {treliça f = labirinto [i] [j] .getfather (); if (f! = null) {int fx = f.getx (), fy = f.gety (); clearfence (i, j, fx, fy, g); }}} g.drawline (preenchimento, preenchimento + 1, preenchimento, preenchimento + largura - 1); int last = preenchimento + num * width; G.Drawline (Last, Last - 1, Last, Last - Width + 1); g.setColor (color.red); G.FILLOVAL (GetCenterx (Bally) - Width / 3, GetCentery (Ballx) - Width / 3, Width / 2, Width / 2); if (drawPath == true) drawPath (g); } private void drawPath (gráficos g) {color path_color = color.orange, bots_path_color = color.pink; if (drawPath == true) g.setColor (path_color); else g.setColor (this.getbackground ()); Lattice p = labirinto [NUM - 1] [NUM - 1]; while (p.getfather ()! = null) {p.setFlag (2); p = p.getfather (); } g.FilOVAL (getCenterx (p) - largura / 3, getCentery (p) - largura / 3, largura / 2, largura / 2); p = labirinto [0] [0]; while (p.getfather ()! = null) {if (p.getflag () == 2) {p.setFlag (3); g.setColor (bots_path_color); } G.Drawline (getCenterx (p), getCentery (p), getCenterx (p.getfather ()), getCentery (p.getfather ())); p = p.getfather (); } g.setColor (path_color); p = labirinto [num - 1] [num - 1]; while (p.getfather ()! = null) {if (p.getflag () == 3) quebra; 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, largura = 600, preenchimento = 20, lx = 200, ly = 100; Jpanel p = novo labirinto (n, (largura - preenchimento - preenchimento) / n, preenchimento); JFRame Frame = new JFrame ("Maze (mostre ou oculte caminhos por barra de espaço)"); frame.getContentPane (). Add (p); frame.setDefaultCloseoperation (jframe.exit_on_close); frame.SetSize (largura + preenchimento, largura + preenchimento + preenchimento); frame.setLocation (lx, ly); frame.setVisible (true); }}