算法简介:
生成一张网格，把网格里面的所有边都存进一个列表edgeList里面.
从(0, 0)开始，做DFS。每次DFS的时候，随机地选择四周一个没有走过的格子，凿墙过去，把道路打通。凿墙的时候，把edgeList列表中相对应的那堵墙删除掉。
将剩下的没有凿开过的墙画出来，就是一个完整的迷宫了。
import sysimport matplotlib.pyplotas pltfrom randomimport randint WIDTH=60 HEIGHT=40 sys.setrecursionlimit(WIDTH* HEIGHT)definitVisitedList(): visited=[]for yinrange(HEIGHT): line=[]for xinrange(WIDTH): line.append(False) visited.append(line)return visiteddefdrawLine(x1, y1, x2, y2): plt.plot([x1, x2],[y1, y2], color="black")defremoveLine(x1, y1, x2, y2): plt.plot([x1, x2],[y1, y2], color="white")defget_edges(x, y): result=[] result.append((x, y, x, y+1)) result.append((x+1, y, x+1, y+1)) result.append((x, y, x+1, y)) result.append((x, y+1, x+1, y+1))return resultdefdrawCell(x, y): edges= get_edges(x, y)for itemin edges: drawLine(item[0], item[1], item[2], item[3])defgetCommonEdge(cell1_x, cell1_y, cell2_x, cell2_y): edges1= get_edges(cell1_x, cell1_y) edges2=set(get_edges(cell2_x, cell2_y))for edgein edges1:if edgein edges2:return edgereturnNonedefinitEdgeList(): edges=set()for xinrange(WIDTH):for yinrange(HEIGHT): cellEdges= get_edges(x, y)for edgein cellEdges: edges.add(edge)return edgesdefisValidPosition(x, y):if x<0or x>= WIDTH:returnFalseelif y<0or y>= HEIGHT:returnFalseelse:returnTruedefshuffle(dX, dY):for tinrange(4): i= randint(0,3) j= randint(0,3) dX[i], dX[j]= dX[j], dX[i] dY[i], dY[j]= dY[j], dY[i]defDFS(X, Y, edgeList, visited): dX=[0,0,-1,1] dY=[-1,1,0,0] shuffle(dX, dY)for iinrange(len(dX)): nextX= X+ dX[i] nextY= Y+ dY[i]if isValidPosition(nextX, nextY):ifnot visited[nextY][nextX]: visited[nextY][nextX]=True commonEdge= getCommonEdge(X, Y, nextX, nextY)if commonEdgein edgeList: edgeList.remove(commonEdge) DFS(nextX, nextY, edgeList, visited) plt.axis('equal') plt.title('Maze') edgeList= initEdgeList() visited= initVisitedList() DFS(0,0, edgeList, visited) edgeList.remove((0,0,0,1)) edgeList.remove((WIDTH, HEIGHT-1, WIDTH, HEIGHT))for edgein edgeList: drawLine(edge[0], edge[1], edge[2], edge[3]) plt.show()