depth first search - Python maze generator explanation -

welcome. can explain me happens in code? know how work (it comes http://rosettacode.org/wiki/maze_generation#python).

from random import shuffle, randrange def make_maze(w = 16, h = 8):     vis = [[0] * w + [1] _ in range(h)] + [[1] * (w + 1)]     ver = [["|  "] * w + ['|'] _ in range(h)] + [[]]     hor = [["+--"] * w + ['+'] _ 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)         (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))     (a, b) in zip(hor, ver):         print(''.join(a + ['\n'] + b))  make_maze() 

i know nothing maze generation, got curious how piece of code works. here insights:

these 2 lines print maze:

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

so happens if put these lines right after 3 lines define vis, ver , hor? this:

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

you can put these 2 lines right before recursive call walk(xx,yy) , see steps of maze evolution:

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |     |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |     |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |     |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |     |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |     |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |     |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+  +  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |     |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |     |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+  +  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+  +  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |     |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |     |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+  +  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+  +  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |     |  |  |  |  |  |  |  |  |  |  |  | +--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |     |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+  +  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+  +  +  +--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |     |  |  |  |  |  |  |  |  |  |  |  | +--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+  +--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+  [...] 

now let's focus on walk(x,y). name , printed output suggest, function walks around maze, removing walls in random fashion build path.

this call:

walk(randrange(w), randrange(h)) 

initializes walk in random location within maze. every cell in grid visited once; visited cells marked in vis.

this line initializes array 4 neighbors of current cell:

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

these visited in random order (thanks shuffle(d))

and these 2 lines ones remove walls maze path being built:

# remove horizontal wall, "+--" turns "+  " if xx == x: hor[max(y, yy)][x] = "+  "     # remove vertical wall, "|"   turns "   " if yy == y: ver[y][max(x, xx)] = "   "    

there more algorithm (see jongware's comment), far understanding particular piece of code goes, these kind of things can do.