生成迷宫图

http://code.activestate.com/recipes/578356-random-maze-generator/

https://en.wikipedia.org/wiki/Maze_generation_algorithm

想实现A*算法和BFS比较验证正确性,所以想构造数据来跑测试,迷宫图是比较好的例子。 Wikipedia上给出了很多种生成迷宫图的算法。

下面是一份生成迷宫图的代码,大致思路是使用DFS进行探路,所有检查过的地方都标记”可以访问“。 这份代码只能指定初始点,没有办法指定结束点,结束点可以在所有到达过的”可以访问“点上任意选择。 因为每次只需要扩展一个节点,所以使用显式的栈也非常简单。

为了不产生回路这样的情况,在扩展下一个节点的时候,会看这个节点是否只有1个可以访问的节点。 代码最后还利用PIL生成了图像,我觉得为了好看,应该白色的地方是”可以访问节点“,而黑色地方是障碍物。

# Random Maze Generator using Depth-first Search
# http://en.wikipedia.org/wiki/Maze_generation_algorithm
# FB - 20121214
import random
from PIL import Image
imgx = 500; imgy = 500
image = Image.new("RGB", (imgx, imgy))
pixels = image.load()
mx = 100; my = 100 # 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
color = [(0,0, 0), (255, 255, 255)] # RGB colors of the maze
# start the maze from a random cell
# stack = [(random.randint(0, mx - 1), random.randint(0, my - 1))]
stack = [(0, 0)]

while len(stack) > 0:
    (cx, cy) = stack[-1]
    maze[cy][cx] = 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] == 1: ctr += 1
                if ctr == 1: nlst.append(i)
    # if 1 or more neighbors available then randomly select one and move
    if len(nlst) > 0:
        ir = nlst[random.randint(0, len(nlst) - 1)]
        cx += dx[ir]; cy += dy[ir]
        stack.append((cx, cy))
    else: stack.pop()

# 翻转颜色,白色是可以访问节点,黑色是不可以访问节点。
for x in maze:
    x = [(1-v) for v in x]

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

GenMaze100x100.png