This code generates a maze randomly using the method "deep-sea search" and then draws it on the screen using ASCII art. An example of output would be:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | |
+ + +--+--+--+--+--+ + + + + + + + +--+
| | | | | | | | | | | |
+ + + + + + +--+ +--+ + + +--+--+--+ +
| | | | | | | | | |
+ +--+--+--+ +--+ +--+ +--+ +--+--+--+ + +
| | | | | | | | |
+ +--+ +--+ + + + +--+ + + +--+--+--+ +
| | | | | | | | | | |
+--+--+--+ + + +--+--+ + + + + + +--+--+
| | | | | | | | |
+ + +--+--+--+--+--+--+--+ + +--+ +--+--+ +
| | | | | | | | | |
+ +--+ + +--+ +--+ + + +--+--+--+ + + +
| | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
To understand the code, we will divide it into two parts: the generation of the labyrinth and its drawing on the screen.
Drawing
I’ll start with the drawing. Here’s the same code, only without the generation functions:
# Define a função para criar o labirinto. Parâmetros:
# w - largura do labirinto (i.e. número de colunas); padrão: 16
# h = altura do labirinto (i.e. número de linhas); padrão: 8
def make_maze(w = 16, h = 8):
First he creates two lists, hor and ver, one to draw the lines of the labyrinth (i.e. the horizontal walls) and the other to draw the columns (the vertical walls).
ver = [["| "] * w + ['|'] for _ in range(h)] + [[]]
This line will produce something like | | | | | | | (in the right width)
hor = [["+--"] * w + ['+'] for _ in range(h + 1)]
And this line will produce something like +--+--+--+--+--+--+--+--+ (ditto)
for (a, b) in zip(hor, ver):
print(''.join(a + ['\n'] + b))
Combining the two, the result is something like:
+--+--+--+-...-+---+
| | | | ... | |
Which, repeated several times, will produce the final output:
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| | | | | | | | | | | | | | | | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
List comprehensions
Ok, but how are the lines created? To understand this, let’s look at the list understanding that created each of them. I’ll start with the hor which is simpler:
hor = [["+--"] * w + ['+'] for _ in range(h + 1)]
Here a list is being created, and assigned to the variable hor:
hor = [ ]
That heron list h+1 elements:
for _ in range(h + 1)
And each element will be the string "+--" repeated w times:
["+--"] * w
Followed by string +:
+ ['+']
That is, at the end of the day hor is a list with this format:
hor = [
["+--","+--","+--","+--",...,"+--","+"],
["+--","+--","+--","+--",...,"+--","+"],
["+--","+--","+--","+--",...,"+--","+"],
...
["+--","+--","+--","+--",...,"+--","+"]
]
It’s easy to see that every line is one +--+--+--+--+. And how there are h+1 lines, the first will be "at the top" of the maze, the last "underneath", and the others between one cell and another.
The definition of ver is similar:
ver = [["| "] * w + ['|'] for _ in range(h)] + [[]]
The first part is a list understanding very similar to hor:
[["| "] * w + ['|'] for _ in range(h)]
The difference is she only has h lines, and not h+1 as hor. To make both lists the same size, an additional element is concatenated to it:
+ [[]]
In the end, ver will be a list of this format:
ver = [
["| ","| ","| ","| ",...,"| ","|"],
["| ","| ","| ","| ",...,"| ","|"],
["| ","| ","| ","| ",...,"| ","|"],
...
["| ","| ","| ","| ",...,"| ","|"],
[]
]
zip
Now that we have a list to print the rows and columns, we need to merge them so that the drawing looks like a grid. The idea is to print a line of hor, after a ver, one of hor, one of ver, etc, until the entire grid has been drawn.
for (a, b) in zip(hor, ver):
What the function zip is to match each element of hor with an element of ver; it’s like you’re making a for a in hor and a for b in ver at the same time (warning: this is quite different of a for within the other). The number of times this for will run is equal to the size of the smallest list. As both have the same size - h+1 - then that’s the number of times that the for will be executed.
print(''.join(a + ['\n'] + b))
This line prints an element of hor, a line break, and an element of ver. To understand this, consider the following:
a is a list of:
["+--","+--","+--","+--",...,"+--","+"]
a + ['\n'] will simply put a line break at the end of a:
["+--","+--","+--","+--",...,"+--","+","\n"]
That + b will concatenate b to that list. b is an element of ver, so that the result will be:
["+--","+--",...,"+--","+","\n","| ","| ",...,"| ","|"]
''.join(lista) will create a string with each element of the list, introducing a '' between one element and another. The result in this case is equivalent to concatenating each of the strings in the list:
"+--+--...+--+\n| | ...| |"
When printing this string on the screen using the print, the result will be that previously mentioned pattern:
+--+--+--+-...-+---+
| | | | ... | |
Which repeated once for each line will result in the complete grid (note that on the last line there is no | | | --- | | remaining; this is because the last element of ver is empty as shown earlier).
Generation of the labyrinth
If you run only the lines explained above (plus function call - make_maze() - with or without parameters controlling height and width) you will see a homogeneous grid. It’s as if you have several small rooms, with no connection between them. How to turn this grid into a maze?
The depth search algorithm works as follows: each of the rooms starts marked "not visited". This corresponds to the value 0 assigned to each variable item vis:
vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
This list comprehension is quite similar to those seen earlier, so I’m not going to explain it in detail. Just realize that the end result will be the way:
vis = [
[0,0,0,...,0,0,1],
[0,0,0,...,0,0,1],
[0,0,0,...,0,0,1],
...
[0,0,0,...,0,0,1],
[1,1,1,...,1,1,1]
]
That is the same as all the visited cells, and the same surrounded by a row and column where everything is visited (the outer limits of the labyrinth). Normally you would use a starting line with everything 1 and an initial column in the same way (to represent the upper and left walls), but this code is taking advantage of the fact that in Python:
lista[-1]
is equivalent to:
lista[len(lista)-1]
So that if you try to access an element with index -1 He’ll "turn around" and take the last element instead. That is, it is as if the rectangle of zeros is surrounded by all sides with a rectangle of ones.
In an ideal labyrinth, there should only be a single path between any pairs of cells. In this way, any cell is chosen as "origin" and tries to reach all others from it:
# Serão usadas as funções "suffle" (embaralhar)
# e "randrange" (sortear número aleatório em um intervalo)
from random import shuffle, randrange
...
# Define uma função para visitar uma célula ainda não visitada
def walk(x, y):
...
# E usa-a para visitar uma célula aleatória em [0,0,w,h)
walk(randrange(w), randrange(h))
Recursion
The function walk is a recursive function: after visiting a cell she tries to visit all the adjacent cells, only returning after they have also been visited. How this is done through other calls to walk, just call it once as shown earlier to ensure that the program does not stop until the entire grid is visited (i.e. the variable vis contains only a few).
def walk(x, y):
First, the current cell is marked as "visited" (because we are visiting it at this time):
vis[y][x] = 1
Then all cells adjacent to it are listed. This corresponds to cells in the same column but a row above or below, or same row but a column to the right or left:
d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
So this list is scrambled, so the visiting order is random:
shuffle(d)
After that each one of them is visited. Then it is decided:
for (xx, yy) in d:
If the cell had already been visited before, does nothing else:
if vis[yy][xx]: continue
This means that either this cell is outside the labyrinth (i.e. it is beyond its limits, that row and column where everything is 1) or that there is already a way linking it to the source (more on this later).
Otherwise, this cell needs to be added to the maze. This is done by "breaking the wall" that separates the current cell (x,y) of the adjacent cell:
if xx == x: hor[max(y, yy)][x] = "+ "
If she’s on a different line, it turns the +-- in +, opening a "hole" in the horizontal wall.
if yy == y: ver[y][max(x, xx)] = " "
If she’s in a different column, it turns the | in
In both cases, the max is used to ensure that the affected cell (is it hor or ver) corresponds to the boundary between one cell and another:
- in the case of one above and the other below, it is the line between one cell and the other, which corresponds to the largest of them (since the first line is simply the top of the labyrinth);
- in case the two are side by side, is the largest column of their row, the one that contains the dividing wall between one cell and the other (because again, the first column is simply the left wall of the labyrinth).
Then visit this cell that has just been incorporated into the labyrinth:
walk(xx, yy)
The fact that she was visited before Visiting the other adjacent cells is what characterizes a "deep search" - as opposed to a "wide search" (if you first visited all adjacent cells, then made the recursive call on each one). The consequence of this is that the algorithm goes "digging a tunnel" from the point of origin as far as it can go, but always making sure that this tunnel does not form a cycle (i.e. if the cell to be dug is already part of the labyrinth, do not knock down the wall, leave it as it is).
Complete code
The complete code, commented in a "healthy" way (neither too much nor too little) would be then:
from random import shuffle, randrange
def make_maze(w = 16, h = 8):
""" Cria um labirinto aleatório e o desenha na tela em ASCII Art
Parâmetros:
w - o número de colunas do labirinto (padrão: 16)
h - o número de linhas do labirinto (padrão: 8)
"""
# Matriz de células visitadas (0 = não visitada, 1 = visitada)
# Delimitada por uma linha/coluna com todos visitados (fronteira)
# Sofre overflow nos índices negativos
vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
# Linhas contendo as células e linhas entre-células
# Inicia-se com todas as células disjuntas (paredes entre todas elas)
ver = [["| "] * w + ['|'] for _ in range(h)] + [[]]
hor = [["+--"] * w + ['+'] for _ in range(h + 1)]
def walk(x, y):
""" Visita uma célula e todas as suas células adjacentes,
em profundidade, unindo-as ao labirinto corrente.
"""
vis[y][x] = 1
d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]
shuffle(d)
for (xx, yy) in d:
if vis[yy][xx]: continue
# Remove a parede entre células
if xx == x: hor[max(y, yy)][x] = "+ "
if yy == y: ver[y][max(x, xx)] = " "
walk(xx, yy)
# Visita a célula de origem
walk(randrange(w), randrange(h))
# Imprime o resultado na tela
for (a, b) in zip(hor, ver):
print(''.join(a + ['\n'] + b))
make_maze()
Thanks, it helped a lot, I took the code in Rosetta and unfortunately it was not commented and was hard to understand how it worked, your explanation clarified a lot, sorry I took so long to answer, I really got a little busy to enter xD
– Albion