起因

我想要写一个项目叫python迷宫游戏，需求是玩家能和机器对抗率先走出迷宫，至少要有两个等级的电脑。

慢慢来，首先迷宫游戏需要有一个迷宫并展示出来，这便是这篇博客的目的

假设迷宫使用0表示点，1表示墙，那么下面的代码主要使用深度优先搜索遍历所有的0

不过在下面的代码并不是这样的，比如在下面的代码(0, 0)表示点，两个点(0, 0)和(0, 1)的连线表示墙，这是因为plt.plot([x1, x2], [y1, y2], color="black")可以轻易画出两个点之间的连线

下面我会介绍我的每一块代码，首先导入需要的库

import sys
import matplotlib.pyplot as plt
from random import randint

sys.setrecursionlimit(height * width)是设置栈的最大深度防止递归写错占用太多内存
self.visited用来记录哪个点已经遍历了
self.edges用来记录要用到的墙，在一开始初始化时会把每个点与他周围的所有点连接生成墙的列表初始化，之后会利用规则删掉不需要的墙，然后就是成品地图了使用plt绘制即可

class Maze(object):
	def __init__(self, height, width):
		sys.setrecursionlimit(height * width)
		self.HEIGHT = height #设置迷宫高
		self.WIDTH = width #设置迷宫宽
		self.visited = []
		self.edges = set()

	# 这个方法用来初始化点的列表
	def initVisitedList(self):
		for y in range(self.HEIGHT):
			line = []
			for x in range(self.WIDTH):
				line.append(False)
			self.visited.append(line)

下面两个方法用来初始化墙的列表，尝试把(0, 0)带入get_edges(self,x, y)很容易就能知道是初始化点旁边的哪4条边

	def get_edges(self,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 result

	def initEdgeList(self):
		for x in range(self.WIDTH):
			for y in range(self.HEIGHT):
				cellEdges = self.get_edges(x, y)
				for edge in cellEdges:
					self.edges.add(edge)

这三个方法是为下面的一个方法准备的，看不懂可以先往下看
shuffle(self, dX, dY)目的是随机指定点往哪一边走（墙）
isValidPosition(self,x, y)用来判断点是否在self.visited中
getCommonEdge()用来判断应该删除哪一条边

	def shuffle(self, dX, dY):
		for t in range(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]

	def isValidPosition(self,x, y):
		if x < 0 or x >= self.WIDTH:
			return False
		elif y < 0 or y >= self.HEIGHT:
			return False
		else:
			return True

	def getCommonEdge(self, cell1_x, cell1_y, cell2_x, cell2_y):
		edges1 = self.get_edges(cell1_x, cell1_y)
		edges2 = set(self.get_edges(cell2_x, cell2_y))
		for edge in edges1:
			if edge in edges2:
				return edge
		return None

这个是最主要的逻辑，它用来得到成品的迷宫地图。它的输入DFS(self, X, Y, edgeList, visited)应该是这样的self.DFS(0, 0, self.edges, self.visited)，self.edges是初始化后的边，self.visited是初始化后用来记录某个点是否被遍历过的列表

dX``dY共同代表了一个点上下左右4个方向，比如(1, 1)带入代码后的结果是(1, 0)``(1, 2)``(0, 1)``(2, 1)

	def DFS(self, X, Y, edgeList, visited):
		dX = [0, 0, -1, 1]
		dY = [-1, 1, 0, 0]
		self.shuffle(dX, dY)
		for i in range(len(dX)):
			nextX = X + dX[i]
			nextY = Y + dY[i]
			if self.isValidPosition(nextX, nextY):
				if not visited[nextY][nextX]:
					visited[nextY][nextX] = True
					# 删除某一条线
					commonEdge = self.getCommonEdge(X, Y, nextX, nextY)
					if commonEdge in edgeList:
						edgeList.remove(commonEdge)
					# 使用深度优先搜索遍历每一个点
					self.DFS(nextX, nextY, edgeList, visited)

把drawLine(self,x1, y1, x2, y2)方法带入下面的逻辑就可以画出迷宫图像了其中self.edges是经过DFS方法后得到的删除掉一些边后的列表

	def drawLine(self,x1, y1, x2, y2):
		plt.plot([x1, x2], [y1, y2], color="black")
	for edge in self.edges:
			self.drawLine(edge[0], edge[1], edge[2], edge[3])

我使用了generate_maze(self)整合了前面所有的方法以画出图片，这里只展示部分代码，因为我担心老师说我是抄的，完整的代码在这里plt_generate_maze

其实DFS得到的并不是完全的成品，它没有出口和入口，这一点也是在generate_maze中删掉两条线来完成的

	def generate_maze(self):
		plt.axis('equal')
		plt.title('Maze')
		#删除的代码部分在这里

		plt.show()

在之后只要调用类设置迷宫宽高，再调用generate_maze方法就可以了
假如宽设置为60，高设置为40，迷宫图是这样的。
image