mst-based random maze generator

random_maze.py

#!/usr/bin/python3

import random

# dimensions should be odd and >= 5
W = 25
H = 25

q = []
m = []

for y in range(H):
    l = []
    for x in range(W):
	l.append(' ')
    m.append(l)

q.append((1, 1, 1, 3))
q.append((1, 1, 3, 1))
while len(q) > 0:
    (x1, y1, x2, y2) = q.pop(random.randrange(len(q)))
    if m[y2][x2] != ' ':
	continue
    m[y1][x1] = '#'
    m[int((y1 + y2) / 2)][int((x1 + x2) / 2)] = '#'
    m[y2][x2] = '#'
    if x2 > 1:
	q.append((x2, y2, x2 - 2, y2))
    if y2 > 1:
	q.append((x2, y2, x2, y2 - 2))
    if x2 < W - 2:
	q.append((x2, y2, x2 + 2, y2))
    if y2 < H - 2:
	q.append((x2, y2, x2, y2 + 2))

for y in range(H):
    for x in range(W):
	print(m[x][y],end='')
    print()