Recentemente, muitas vezes assisto meus colegas de classe jogando um jogo de labirinto na sala de computadores. É bastante interessante. Também uso o Java para escrever um algoritmo para implementar geração aleatória de labirintos. De fato, é um algoritmo de travessia de profundidade para um gráfico. A idéia básica é que todos os pontos do labirinto têm quatro paredes e depois.
1. Inicie o acesso de qualquer ponto (meu algoritmo é fixado para começar a partir do ponto (0,0)) e visite uma das quatro direções aleatórias (toda vez que você acessa um ponto acessível, remova a parede nessa direção desse ponto) e o ponto acessado continua a acessá -lo nessa direção.
2. Cada ponto visitado é identificado como acessado. Quando um ponto acessa uma certa direção, primeiro determinaremos se o ponto acessado foi acessado ou toca o limite. Se todas as quatro direções do ponto foram acessadas ou não conseguirem acessar, retorne ao ponto anterior. O ponto anterior continua o processo.
Após o Traversal dessa maneira, pode -se confirmar que cada ponto foi visitado. Além disso, como a direção de cada acesso é aleatória, muitas situações de travessia diferentes serão formadas. Ao mesmo tempo, o caminho entre cada dois pontos é único, que forma um labirinto diferente, e há apenas um caminho único desde o ponto de partida até o ponto final. Isso é determinado pelas características do algoritmo de travessia de profundidade do gráfico. Na implementação do algoritmo, o principal é usar a pilha. Na primeira vez, pressione o primeiro ponto na pilha. Toda vez que um ponto é acessado, o ponto é empurrado para dentro da pilha, acessamos aleatoriamente o ponto na parte superior da pilha em quatro direções, acessamos o novo ponto e depois pressionamos o novo ponto. Depois que as quatro direções deste ponto estiverem inacessíveis, deixe o ponto retirar da pilha e depois acessar as quatro direções do ponto no topo do topo da pilha e assim por diante. Até todos os pontos da saída da pilha, nossa travessia será bem -sucedida. Este é um processo recursivo. Esse algoritmo pode ser implementado naturalmente por métodos recursivos. No entanto, faço isso aqui, mas implementi -lo manualmente com uma matriz como a pilha. Haha ~~ depois de dizer tanto, não sei se o que quero expressar é expresso. No entanto, sinto que meu design de código específico não está bem escrito e ainda existem muitos lugares onde há uma falta de melhoria e otimização. É apenas para ser um exercício de algoritmo. A seguir, são apresentados os códigos principais das duas classes principais. Quanto ao código da camada de apresentação, não os publicarei porque esses são muito triviais.
Aqui está a renderização:
Classe Maze:
// Autor: zhongzw // E -mail: [email protected] pacote cn.zhongzw.model; importar java.util.arraylist; importar java.util.random; classe pública Mazemodel {private int width = 0; private int altura = 0; private Random RND = new Random (); public Mazemodel () {this.width = 50; // largura do labirinto isto.Height = 50; // altura do labirinto} public int getwidth () {return width; } public void setWidth (int width) {this.width = width; } public int getHeight () {return Hight; } public void sethight (int alting) {this.Height = altura; } public mazemodel (int width, int altura) {super (); this.width = width; this.Height = altura; } public ArrayList <MazePoint> getMaze () {ArrayList <MazePoint> MAZE = new ArrayList <MazePoint> (); for (int h = 0; h <altura; h ++) {for (int w = 0; w <largura; w ++) {ponto de MazePoint = new MazePoint (w, h); Maze.add (Point); }} retornar createMaze (labirinto); } Private ArrayList <MazePoint> createMaze (ArrayList <MazePoint> Maze) {int top = 0; int x = 0; int y = 0; ArrayList <MazePoint> equipe = new ArrayList <MazePoint> (); Team.add (Maze.get (x + y * largura)); while (top> = 0) {int [] val = new int [] {-1, -1, -1, -1}; int times = 0; bandeira booleana = false; Mazepoint pt = (Mazepoint) equipe.get (topo); x = pt.getx (); y = pt.gety (); pt.visted = true; RO1: while (vezes <4) {int dir = rnd.nextint (4); if (val [dir] == dir) continuar; else val [dir] = dir; switch (dir) {case 0: // esquerda if ((x - 1)> = 0 && Maze.get (x - 1 + y * width) .visted == false) {Maze.get (x + y * largura) .Setleft (); Maze.get (x - 1 + y * largura) .Setright (); Team.add (Maze.get (x - 1 + y * largura)); top ++; bandeira = true; quebrar ro1; } quebrar; Caso 1: // direita if ((x + 1) <width && Maze.get (x + 1 + y * width) .visted == false) {Maze.get (x + y * width) .Setright (); Maze.get (x + 1 + y * largura) .setLeft (); Team.add (Maze.get (x + 1 + y * largura)); top ++; bandeira = true; quebrar ro1; } quebrar; Caso 2: // if ((y - 1)> = 0 && maze.get (x + (y - 1) * largura) .visted == false) {Maze.get (x + y * width) .setup (); Maze.get (x + (y - 1) * largura) .SetDown (); Team.add (Maze.get (x + (y - 1) * largura)); top ++; bandeira = true; quebrar ro1; } quebrar; Caso 3: // abaixo se ((y + 1) <altura && maze.get (x + (y + 1) * largura) .visted == false) {Maze.get (x + y * width) .SetDown (); Maze.get (x + (y + 1) * largura) .setup (); Team.add (Maze.get (x + (y + 1) * largura)); top ++; bandeira = true; quebrar ro1; } quebrar; } vezes += 1; } if (! flag) {Team.Remove (topo); topo -= 1; }} retorna labirinto; }}
labirinto
// Autor: zhongzw // E -mail: [email protected] pacote cn.zhongzw.model; importar java.util.*; importar java.lang.*; classe pública MazePoint {private int esquerd = 0; private int certo = 0; private int up = 0; privado int down = 0; privado int x; private int y; Public Boolean testemunhou; public mazepoint (int x, int y) {this.x = x; this.y = y; } public int getLeft () {return à esquerda; } 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 se setTown () {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; }}
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.