Question:

I don't know Python very well and for this fact I'm not being able to read this code properly. Could someone please post comments to make it easier to read? Preferably explaining what each line does.

from random import shuffle, randrange

def make_maze(w = 16, h = 8):
    vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]
    ver = [["|  "] * w + ['|'] for _ in range(h)] + [[]]
    hor = [["+--"] * w + ['+'] for _ in range(h + 1)]

    def walk(x, y):
        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
            if xx == x: hor[max(y, yy)][x] = "+  "
            if yy == y: ver[y][max(x, xx)] = "   "
            walk(xx, yy)

    walk(randrange(w), randrange(h))
    for (a, b) in zip(hor, ver):
        print(''.join(a + ['\n'] + b))

make_maze()

Answer:

This code randomly generates a maze using the "depth search" method and then draws it to the screen using ASCII art . An example output would be:

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |                       |     |     |        |
+  +  +--+--+--+--+--+  +  +  +  +  +  +  +  +--+
|  |  |  |           |  |  |  |  |  |     |     |
+  +  +  +  +  +  +--+  +--+  +  +  +--+--+--+  +
|     |     |  |  |     |     |  |        |     |
+  +--+--+--+  +--+  +--+  +--+  +--+--+--+  +  +
|  |           |     |     |  |  |           |  |
+  +--+  +--+  +  +  +  +--+  +  +  +--+--+--+  +
|        |  |  |  |  |     |  |  |     |        |
+--+--+--+  +  +  +--+--+  +  +  +  +  +  +--+--+
|  |           |           |  |  |  |  |        |
+  +  +--+--+--+--+--+--+--+  +  +--+  +--+--+  +
|  |     |        |        |  |     |     |  |  |
+  +--+  +  +--+  +--+  +  +  +--+--+--+  +  +  +
|           |           |                 |     |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

To understand the code, let's divide it into two parts: generating the maze and drawing it on the screen.

Design

I will start with the drawing. Here is 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 it creates two lists, hor and ver , one to draw the maze lines (ie the horizontal walls) and the other to draw the columns (the vertical walls).

    ver = [["|  "] * w + ['|'] for _ in range(h)] + [[]]

    hor = [["+--"] * w + ['+'] for _ in range(h + 1)]

And this line will produce something like +--+--+--+--+--+--+--+--+ (idem)

    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 Understandings

Okay, but how are the lines created? To understand this, let's look at the list comprehension that created each of them. I'll start with hor which is simpler:

    hor = [["+--"] * w + ['+'] for _ in range(h + 1)]

Here a list is being created, and assigned to the variable hor :

    hor = [                                         ]

This list will have h+1 elements:

                               for _ in range(h + 1)

And each element will be the string "+--" repeated w times:

           ["+--"] * w

Followed by the string + :

                       + ['+']

In other words, in the end, hor is a list with this format:

hor = [
    ["+--","+--","+--","+--",...,"+--","+"],
    ["+--","+--","+--","+--",...,"+--","+"],
    ["+--","+--","+--","+--",...,"+--","+"],
    ...
    ["+--","+--","+--","+--",...,"+--","+"]
]

It's easy to see that each line is a +--+--+--+--+ . And since there are h+1 lines, the first one will be "on top" of the maze, the last one "below", and the rest between one cell and another.

The definition of ver is similar:

    ver = [["|  "] * w + ['|'] for _ in range(h)] + [[]]

The first part is a list comprehension much like hor :

          [["|  "] * w + ['|'] for _ in range(h)]

The difference is that it only has h lines, not h+1 like hor . To make both lists the same size, an additional element is concatenated to it:

                                                  + [[]]

At the end, ver will be a list with this format:

ver = [
    ["|  ","|  ","|  ","|  ",...,"|  ","|"],
    ["|  ","|  ","|  ","|  ",...,"|  ","|"],
    ["|  ","|  ","|  ","|  ",...,"|  ","|"],
    ...
    ["|  ","|  ","|  ","|  ",...,"|  ","|"],
    []
]

zip

Now that we have a list to print the rows and columns, we need to merge them so that the design looks like a grid. The idea is to print a line of hor , then a line of ver , a line of hor , a line of ver , etc, until the entire grid has been drawn.

    for (a, b) in zip(hor, ver):

What the zip function does is pair each hor element with a ver element; it's as if you were doing a for a in hor and a for b in ver at the same time (note: this is quite different from one for inside the other). The number of times this for will run is equal to the size of the smallest list. Since they are both the same size – h+1 – then this is the number of times the for will be executed.

        print(''.join(a + ['\n'] + b))

That line prints a hor element, a line break, and a ver element. To understand this, consider the following:

a is a list like:

 ["+--","+--","+--","+--",...,"+--","+"]

a + ['\n'] will simply put a line break at the end of a :
```
 ["+--","+--","+--","+--",...,"+--","+","\n"]
```
That + b will concatenate b to that list. b is a ver element, so the result will be:
```
 ["+--","+--",...,"+--","+","\n","| ","| ",...,"| ","|"]
```
''.join(lista) will create a string with each element in the list, inserting 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 to the screen using print , the result will be the one mentioned above:
```
 +--+--+--+-...-+---+ | | | | ... | |
```
That repeated once for each row will result in the complete grid (notice that on the last row there is no | | | --- | | left; this is because the last element of the ver is empty, as shown above).

labyrinth generation

If you run just the lines explained above (plus the function call – make_maze() – with or without parameters controlling the height and width) you will see a homogeneous grid. It's as if you have several small rooms, without any connection between them. How then to transform this grid into a maze?

The depth search algorithm works like this: each of the rooms starts off marked as "unvisited". This corresponds to the value 0 assigned to each element of the vis variable:

    vis = [[0] * w + [1] for _ in range(h)] + [[1] * (w + 1)]

This list comprehension is quite similar to those we've seen before, so I won't explain it in detail. Just realize that the end result will be this 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]
]

Which is the same as all unvisited cells, and the same ones surrounded by a row and column where everything is visited (the outer limits of the maze). Normally you would use a starting line with everything 1 and a starting column the same way (to represent the top and left walls), but this code is taking advantage of the fact that in Python:

lista[-1]

it's equivalent to:

lista[len(lista)-1]

So if you try to access an element with index -1 it will "go around" and get the last element instead. That is, it is as if the rectangle of zeros is surrounded on all sides by a rectangle of ones.

In an ideal maze, there should be only one path between any pairs of cells. In this way, any cell is chosen as "source" and one tries to reach all the 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 walk function is a recursive function: after visiting a cell it tries to visit all the cells adjacent to it, only returning after they have already been visited. As this is done through other calls to walk , just call it once as shown above to ensure that the program doesn't stop until the entire grid is visited (ie the vis variable contains only ones).

def walk(x, y):

Firstly, the current cell is marked as "visited" (as we are visiting it right now):

    vis[y][x] = 1

Then all cells adjacent to it are listed. This corresponds to cells in the same column but one row above or below, or same row but one column to the right or left:

    d = [(x - 1, y), (x, y + 1), (x + 1, y), (x, y - 1)]

Then this list is shuffled so that the visit order is random:

    shuffle(d)

After that each one of them is visited. So you decide:

    for (xx, yy) in d:

If the cell had already been visited before, it does nothing else:
```
 if vis[yy][xx]: continue
```
This means that either this cell is outside the maze (ie it is beyond its limits, that row and column where everything is 1 ) or that there is already a path connecting it to the origin (more on this later).
Otherwise, that cell needs to be added to the maze. This is done by "breaking the wall" that separates the current cell ( x,y ) from the adjacent cell:
```
 if xx == x: hor[max(y, yy)][x] = "+ "
```
If it's on a different line, it turns the +-- into a + , opening a "hole" in the horizontal wall.
```
 if yy == y: ver[y][max(x, xx)] = " "
```
If it is in a different column, transform the | in , opening a hole in the vertical wall.

In both cases, max is used to ensure that the affected cell (be it hor or ver ) matches the boundary between one cell and the other:
- in case one is at the top and the other at the bottom, it is the line between one cell and the other, which therefore corresponds to the largest of them (since the first line is simply the top of the maze);
- in case the two are side by side, it is the largest column in your row, the one that contains the dividing wall between one cell and another (again, the first column is simply the left wall of the labyrinth).
Then visit this cell that has just been incorporated into the maze:
```
 walk(xx, yy)
```
The fact that it is visited before visiting the other adjacent cells is what characterizes a "depth search" – as opposed to a "width search" (if you first visited all adjacent cells, then made the recursive call on each one of them). The consequence of this is that the algorithm "tunnels" from the point of origin as far as it can go, but always making sure that this tunnel does not form a cycle (ie if the cell to be excavated is already part of the maze, do not collapse the wall, leave it as it is).

full code

The complete code, commented in a "sane" way (not too much and not too little) would then be:

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()

Post Views: 0