Random maze generation
In this post I just want to share a simple algorithm that I used to create random mazes. The idea came from an e-mail I got, about a past competition, where one of the contestants did this exact thing: a program to generate random mazes. I saw the animation of the program working here and I deduced how to do it.
All the code can be found on GitHub, as well as an executable of the program, the animations from the beginning and end of this post, an image of a bigger maze, and this other animation:
where you can see a different style of maze; a less straight one. The maze starts in the top left red corner and ends wherever the other red square is, which need not be on the bottom right corner.
The algorithm is simple: travel randomly inside the black area without ever hitting a white path; whenever no random move can be made, start going back until you find a place where the path can branch out again. While we are creating white paths, keep updating the final position to be the farthest cell that has ever been visited.
If you can't solve any of the mazes you can always check my older maze solver!
All the code can be found on GitHub, as well as an executable of the program, the animations from the beginning and end of this post, an image of a bigger maze, and this other animation:
where you can see a different style of maze; a less straight one. The maze starts in the top left red corner and ends wherever the other red square is, which need not be on the bottom right corner.
The algorithm is simple: travel randomly inside the black area without ever hitting a white path; whenever no random move can be made, start going back until you find a place where the path can branch out again. While we are creating white paths, keep updating the final position to be the farthest cell that has ever been visited.
If you can't solve any of the mazes you can always check my older maze solver!
Neste post quero apenas dar a conhecer um algoritmo simples que usei para criar labirintos aleatórios. A ideia para fazer isto veio de um e-mail que recebi, sobre um concurso que tinha havido, onde um dos concorrentes mais bem classificados tinha feito precisamente isto: um programa para criar labirintos aleatórios. Vi a animação desse programa a correr aqui e deduzi como poderia fazer semelhante.
Pus o código no GitHub, bem como um executável, as duas animações que se podem ver no início e fim do post, a imagem de um labirinto maior que fiz e a animação aqui em baixo:
O labirinto começa no canto superior esquerdo, na célula vermelha, e acaba na outra célula vermelha que não tem de estar no canto inferior direito.
O algoritmo é simplicíssimo: vai andando aleatoriamente pela zona preta sem nunca atravessar outro caminho branco; quando não há alternativas válidas, começa a voltar para trás, por onde veio, até encontrar outro sítio onde possa bifurcar o caminho. Enquanto se criam os caminhos, marca-se também o ponto mais longe a que se chegou, que será a posição final do labirinto.
Se não conseguirem resolver o labirinto, podem sempre tentar usar o meu programa para resolver labirintos!
Pus o código no GitHub, bem como um executável, as duas animações que se podem ver no início e fim do post, a imagem de um labirinto maior que fiz e a animação aqui em baixo:
O labirinto começa no canto superior esquerdo, na célula vermelha, e acaba na outra célula vermelha que não tem de estar no canto inferior direito.
O algoritmo é simplicíssimo: vai andando aleatoriamente pela zona preta sem nunca atravessar outro caminho branco; quando não há alternativas válidas, começa a voltar para trás, por onde veio, até encontrar outro sítio onde possa bifurcar o caminho. Enquanto se criam os caminhos, marca-se também o ponto mais longe a que se chegou, que será a posição final do labirinto.
Se não conseguirem resolver o labirinto, podem sempre tentar usar o meu programa para resolver labirintos!
- RGS
