Python生成迷宫

算法简介:

1. 生成一张网格，把网格里面的所有边都存进一个列表edgeList里面.

2. 从(0, 0)开始，做DFS。每次DFS的时候，随机地选择四周一个没有走过的格子，凿墙过去，把道路打通。凿墙的时候，把edgeList列表中相对应的那堵墙删除掉。

3. 将剩下的没有凿开过的墙画出来，就是一个完整的迷宫了。

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()