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 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:

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 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.

$600 \times 450$ maze

  - RGS

Popular posts from this blog

Pocket maths: how to compute averages in your head

Pt En Being able to do basic arithmetic calculations in your head is a great skill. Not because it is sexy but because it is useful in your daily life: it can help you check the change you are given when shopping, it can help you know if you will have enough money to pay for your groceries, it can help you estimate how much things cost after the discounts, etc... This often reduces to being able to sum and subtract decently; sometimes you need to make a couple of small multiplications, but that is it. More likely than not, you don't need to compute averages every day. But sometimes you just want the scoring average of your team for the past few games, or the average price per person of a given meal, or the average time you spent stuck in traffic this past week... And averages may appear nastier than simply adding or subtracting, because averages also require you to perform a division: in fact, you have to add all the numbers you want and then divide the total by ho...
Read more

Tutorial on programming a memory card game

Image
Pt En Este post vai ser um tutorial, não muito detalhado, sobre como fazer um jogo de memória com Python e pygame. O jogo que vamos implementar é um jogo comum: viramos uma série de cartas para baixo e temos que as virar duas a duas, tentando encontrar os pares. Claro que quando viramos duas cartas que não são um par, temos de as voltar de novo para baixo. Quando estou a criar um jogo, gosto de o ir desenvolvendo por etapas funcionais: partir o processo em várias fases que representem pontos nos quais eu tenho algo que posso testar. Deste modo, não só o processo se torna muito mais interessante, como posso ir controlando o aspeto do que estou a produzir. Deixo de seguida uma lista das etapas que eu pensei para este projeto; cada ponto da lista descreve a funcionalidade que o jogo já suporta: Criar um ecrã onde mostro todas as cartas dispostas, face para baixo; Clicar em cima de uma carta faz com que ela se vire para cima; Clicar na segunda carta verifica se encontrei...
Read more

Markov Decision Processes 02: how the discount factor works

Image
Pt En In this previous post I defined a Markov Decision Process and explained all of its components; now, we will be exploring what the discount factor $\gamma$ really is and how it influences the MDP. Let us start with the complete example of last post: In this MDP the states are Hungry and Thirsty (which we will represent with $H$ and $T$) and the actions are Eat and Drink (which we will represent with $E$ and $D$). The transition probabilities are specified by the numbers on top of the arrows. In the previous post we put forward that the best policy for this MDP was defined as $$\begin{cases} \pi(H) = E\\ \pi(T) = D\end{cases}$$ but I didn't really prove that. I will do that in a second, but first what are all the other possible policies? Well, recall that the policy $\pi$ is the "best strategy" to be followed, and $\pi$ is formally seen as a function from the states to the actions, i.e. $\pi: S \to A$. Because of that, we must know what $\pi(H)...
Read more