Generating (better) random mazes
< change language
In this previous post I shared some code and animations of an algorithm that created random mazes. I shared it with you and I got some feedback on Facebook, saying that even the stupidly large mazes I gave you were really easy to solve (I think this link can show you what I am talking about). So it was about time I got you some new mazes! And this time, I don't think they are as easy to solve as the old ones.
The mazes I am sharing today were created by code found in this GitHub repo. The README will tell you to run the
The way our algorithm works is really simple. It will start a random walk on the top left corner of the window. Whenever the random walk intersects itself (creating a loop), it removes the loop from the walk, and then continues. Whenever the random walk connects back to whatever part of the maze was already built, the random walk becomes a part of the maze itself and a new random walk is started somewhere else. This is a loop-erased random walk, the stepping stone of Wilson's algorithm to generate a random spanning tree of a graph, with a very nice property: it will generate any of the possible spanning trees with equal probability.
Generating any of the spanning trees uniformly means that our maze won't be biased and have only a couple of really long paths, or a bunch of very short paths. And the reason why this algorithm actually has that property is fairly intuitive: just suppose that before running the algorithm, you visit each vertex, and create an infinite random stack of directions; that is, for each vertex $v$ in the graph, you create a random sequence $\{v_i\}_i$, where each $v_i$ was selected randomly and uniformly from the direct neighbours of $v$. After you have done this for every vertex, there is an obvious way to start tracing paths in your graph: just pick a vertex and start following the directions you are given! But the thing is, following those directions might actually make you follow some loops. So before tracing the paths you are presented with, you remove all the loops that you can find on top of all the stacks you created... when that has been done, following the directions that are on top of the stacks will give you a uniformly generated random tree. Of course that to run our algorithm, we don't generate the infinite stacks in advance, we just generate the elements that are needed on-the-fly.
This algorithm creates really balanced mazes... As an example, take this maze:
Now imagine that on the top left corner I will pour a bucket of a special paint: one that gradually changes colour as it travels. The resulting (coloured) maze looks like this:
(please bear in mind that the colours used cycle back to the beginning, so it creates a continuous and infinite degradee)
Also notice that this algorithm can be painfully slow to watch, specially when it has just started. I would strongly recommend against changing the configuration
That is it! You have a small animation of the algorithm on the beginning of the post and a massive maze down there! Let me know if you manage to find your way from the top left corner to the bottom right corner! (the black and white version of that maze is here)
I would also recommend checking this link, as it has some nice animations.
The mazes I am sharing today were created by code found in this GitHub repo. The README will tell you to run the
wilson_generator.py file. You can also download the (windows) executable that is zipped inside the wilsonExe rar. (please notice that in both cases, you can use the wilsonconfig.ini file to change the size of the maze)The way our algorithm works is really simple. It will start a random walk on the top left corner of the window. Whenever the random walk intersects itself (creating a loop), it removes the loop from the walk, and then continues. Whenever the random walk connects back to whatever part of the maze was already built, the random walk becomes a part of the maze itself and a new random walk is started somewhere else. This is a loop-erased random walk, the stepping stone of Wilson's algorithm to generate a random spanning tree of a graph, with a very nice property: it will generate any of the possible spanning trees with equal probability.
Generating any of the spanning trees uniformly means that our maze won't be biased and have only a couple of really long paths, or a bunch of very short paths. And the reason why this algorithm actually has that property is fairly intuitive: just suppose that before running the algorithm, you visit each vertex, and create an infinite random stack of directions; that is, for each vertex $v$ in the graph, you create a random sequence $\{v_i\}_i$, where each $v_i$ was selected randomly and uniformly from the direct neighbours of $v$. After you have done this for every vertex, there is an obvious way to start tracing paths in your graph: just pick a vertex and start following the directions you are given! But the thing is, following those directions might actually make you follow some loops. So before tracing the paths you are presented with, you remove all the loops that you can find on top of all the stacks you created... when that has been done, following the directions that are on top of the stacks will give you a uniformly generated random tree. Of course that to run our algorithm, we don't generate the infinite stacks in advance, we just generate the elements that are needed on-the-fly.
This algorithm creates really balanced mazes... As an example, take this maze:
Also notice that this algorithm can be painfully slow to watch, specially when it has just started. I would strongly recommend against changing the configuration
save_frames = False to True, as that will slow down the algorithm for a bit... but if you must do that, point the screenshot_bin to some existing folder, so that the thousands of frames get dumped there.That is it! You have a small animation of the algorithm on the beginning of the post and a massive maze down there! Let me know if you manage to find your way from the top left corner to the bottom right corner! (the black and white version of that maze is here)
I would also recommend checking this link, as it has some nice animations.
Num post antigo eu partilhei código e algumas animações de um algoritmo que criava labirintos aleatórios. Quando partilhei algumas imagens, recebi feedback a dizer que até os labirintos grandes eram fáceis de resolver (penso que aqui encontram o feedback a que me refiro). Portanto já estava na altura de eu arranjar uma maneira melhor de gerar os labirintos! E desta vez, acho que os resultados são melhores.
Os labirintos deste post foram criados por código que está neste repositório do GitHub. O ficheiro README explica como usar o ficheiro
O modo como o algoritmo funciona é simples. Basta começar um caminho aleatório no canto superior esquerdo da janela. De cada vez que esse caminho aleatório se intersetar a si próprio (criando assim um ciclo), o algoritmo retira esse ciclo do caminho e retoma a construção do caminho aleatório. Sempre que o caminho aleatório tocar numa parte do labirinto que já estava construída, esse caminho aleatório passa a fazer parte do labirinto e começamos outro caminho aleatório noutra posição qualquer. Estes caminhos aleatórios sem ciclos são a base do algoritmo de Wilson para criar uma árvore geradora de um grafo com a seguinte propriedade: qualquer árvore geradora tem igual probabilidade de ser criada.
Como a árvore geradora é escolhida uniformemente de entre todas as árvores geradoras possíveis, em geral o nosso labirinto não tem os defeitos específicos de outros algoritmos, como só ter um par de caminhos muito longos ou ter imensos caminhos, mas todos muito curtos. Perceber porque é que o algoritmo tem esta propriedade não é completamente impossível: imaginemos que antes de começar o algoritmo, eu visitei cada vértice do grafo e criei uma pilha infinita de direções; ou seja, para cada vértice $v$ do grafo, criei uma sucessão aleatória $\{v_i\}_i$, onde cada $v_i$ é escolhido uniformemente de entre os vizinhos diretos de $v$. Depois de isto ser feito para cada vértice, há uma maneira óbvia de começar a percorrer caminhos no grafo: basta escolher um vértice e seguir as direções que me são dadas! Mas há um pequeno senão: seguir estas direções fará certamente com que encontremos ciclos. Para prevenir isto, antes de começarmos a seguir as indicações que nos são dadas, retiramos todos os ciclos que estejam a ser criados pelas direções que estão nas pilhas... quando isto tiver sido feito, podemos seguir as direções dos vários vértices e criamos assim uma árvore geradora do nosso grafo. Claro que para correr o algoritmo, não criamos pilhas infinitas à priori. Vamos calculando as direções à medida que elas são necessárias.
Os labirintos criados por este algoritmo são bastante equilibrados, no sentido de não terem poucos caminhos muito longos ou muitos caminhos bastante curtos. Na verdade, olhando para este labirinto:
Posso pensar em colori-lo de uma maneira especial: no canto superior esquerdo vou deitar um balde de tinta que muda de cor gradualmente à medida que escorre. O labirinto fica então pintado desta maneira:
(note-se que as cores da "tinta" são cíclicas, para que eu possa sempre criar uma difusão contínua e infinita)
Também gostava de avisar que este algoritmo pode ser particularmente aborrecido de ver correr, principalmente se tiver acabado de começar a correr. Não aconselho ninguém a mudar a configuração
E por agora é tudo. Há uma pequena animação do algoritmo no início deste post e um labirinto absurdamente grande no fim! Avisem-me se o completarem, encontrando um caminho do canto superior esquerdo ao canto inferior direito. (a versão a preto e branco está aqui)
Também aconselho este link que tem algumas animações giras.
Os labirintos deste post foram criados por código que está neste repositório do GitHub. O ficheiro README explica como usar o ficheiro
wilson_generator.py. Também há a opção de usarem o executável windows que está zippado dentro do ficheiro wilsonExe.rar. (em qualquer um dos casos, o ficheiro wilsonconfig.ini pode ser usado para mudar o tamanho do labirinto)O modo como o algoritmo funciona é simples. Basta começar um caminho aleatório no canto superior esquerdo da janela. De cada vez que esse caminho aleatório se intersetar a si próprio (criando assim um ciclo), o algoritmo retira esse ciclo do caminho e retoma a construção do caminho aleatório. Sempre que o caminho aleatório tocar numa parte do labirinto que já estava construída, esse caminho aleatório passa a fazer parte do labirinto e começamos outro caminho aleatório noutra posição qualquer. Estes caminhos aleatórios sem ciclos são a base do algoritmo de Wilson para criar uma árvore geradora de um grafo com a seguinte propriedade: qualquer árvore geradora tem igual probabilidade de ser criada.
Como a árvore geradora é escolhida uniformemente de entre todas as árvores geradoras possíveis, em geral o nosso labirinto não tem os defeitos específicos de outros algoritmos, como só ter um par de caminhos muito longos ou ter imensos caminhos, mas todos muito curtos. Perceber porque é que o algoritmo tem esta propriedade não é completamente impossível: imaginemos que antes de começar o algoritmo, eu visitei cada vértice do grafo e criei uma pilha infinita de direções; ou seja, para cada vértice $v$ do grafo, criei uma sucessão aleatória $\{v_i\}_i$, onde cada $v_i$ é escolhido uniformemente de entre os vizinhos diretos de $v$. Depois de isto ser feito para cada vértice, há uma maneira óbvia de começar a percorrer caminhos no grafo: basta escolher um vértice e seguir as direções que me são dadas! Mas há um pequeno senão: seguir estas direções fará certamente com que encontremos ciclos. Para prevenir isto, antes de começarmos a seguir as indicações que nos são dadas, retiramos todos os ciclos que estejam a ser criados pelas direções que estão nas pilhas... quando isto tiver sido feito, podemos seguir as direções dos vários vértices e criamos assim uma árvore geradora do nosso grafo. Claro que para correr o algoritmo, não criamos pilhas infinitas à priori. Vamos calculando as direções à medida que elas são necessárias.
Os labirintos criados por este algoritmo são bastante equilibrados, no sentido de não terem poucos caminhos muito longos ou muitos caminhos bastante curtos. Na verdade, olhando para este labirinto:
Também gostava de avisar que este algoritmo pode ser particularmente aborrecido de ver correr, principalmente se tiver acabado de começar a correr. Não aconselho ninguém a mudar a configuração
save_frames = False para True, porque isso desacelera o algoritmo ainda mais... mas se alguém quiser mesmo, então também é melhor mudar screenshot_bin para uma pasta qualquer que exista, para que as imagens sejam guardadas lá.E por agora é tudo. Há uma pequena animação do algoritmo no início deste post e um labirinto absurdamente grande no fim! Avisem-me se o completarem, encontrando um caminho do canto superior esquerdo ao canto inferior direito. (a versão a preto e branco está aqui)
Também aconselho este link que tem algumas animações giras.
$600 \times 450$ maze
- RGS
