# Multi-Maze Generator using Depth-first Search
# Multi-Maze: Maze w/ multiple paths to solve
# http://en.wikipedia.org/wiki/Maze_generation_algorithm
# FB - 20121214
import random
from PIL import Image
imgx = 600; imgy = 600
image = Image.new("RGB", (imgx, imgy))
pixels = image.load()
m = random.randint(1, 10) # of maze paths
mx = 60; my = 60 # width and height of the maze
maze = [[0 for x in range(mx)] for y in range(my)]
dx = [0, 1, 0, -1]; dy = [-1, 0, 1, 0] # 4 directions to move in the maze
stack = [] # array of stacks
color = [(0, 0, 0)] # RGB colors maze paths
for i in range(m):
    while True:
        kx = random.randint(0, mx - 1); ky = random.randint(0, my - 1)
        if maze[ky][kx] == 0: break
    stack.append([(kx, ky)])
    maze[ky][kx] = i + 1
    color.append((random.randint(0, 255),
                  random.randint(0, 255),
                  random.randint(0, 255)))

cont = True # continue
while cont:
    cont = False
    for p in range(m):
        if len(stack[p]) > 0:
            cont = True # continue as long as there is a non-empty stack
            (cx, cy) = stack[p][-1]
            # find a new cell to add
            nlst = [] # list of available neighbors
            for i in range(4):
                nx = cx + dx[i]; ny = cy + dy[i]
                if nx >= 0 and nx < mx and ny >= 0 and ny < my:
                    if maze[ny][nx] == 0:
                        # of occupied neighbors must be 1
                        ctr = 0
                        for j in range(4):
                            ex = nx + dx[j]; ey = ny + dy[j]
                            if ex >= 0 and ex < mx and ey >= 0 and ey < my:
                                if maze[ey][ex] == p + 1: ctr += 1
                        if ctr == 1: nlst.append(i)
            # if 1 or more neighbors available then randomly select one and add
            if len(nlst) > 0:
                ir = nlst[random.randint(0, len(nlst) - 1)]
                cx += dx[ir]; cy += dy[ir]
                maze[cy][cx] = p + 1
                stack[p].append((cx, cy))
            else: stack[p].pop()

for ky in range(imgy):
    for kx in range(imgx):
        pixels[kx, ky] = color[maze[my * ky / imgy][mx * kx / imgx]]
image.save(str(m) + "Maze_" + str(mx) + "x" + str(my) + ".png", "PNG")