迷宫生成算法总结

我就是我 2023-07-03 02:33 34阅读 0赞

最近闲来无事想做一个质量高一点的进阶版的迷宫小游戏，首先就要先生成最基础的迷宫地图，因此学习并整理了一下迷宫生成算法。由于python更容易实现这些算法，因此首先使用pyhon将各种生成算法整理一遍，之后再用Qt或者javascript重写一遍，再加上可视化。

**目前已经使用python实现了一个简单的可玩版本，可在[迷宫游戏python实现][python]查看。**

大概了解了一下，生成迷宫的算法主要有三种思路，其中最小生成树算法又可以分为选点法（prim）和选边法（kruskal）：

*  随机深度优先算法
 *  递归分割算法(TODO)
 *  随机prim最小生成树算法
 *  \*kruskal最小生成树算法（使用并查集实现）

> ❓ **BrainStorm**：能否编程生成圆形的迷宫？如下图所示，如果有读者有思路，欢迎留言讨论。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70]

话不多说，进入正文。

## 1 随机深度优先算法 ##

之所以叫做**随机**深度优先算法，是因为传统的深度优先算法中已经确定了遍历上下左右四个方向的顺序，因此每次生成的地图都是一样的，而且特别简单。为了增加地图的随机性，需要在每次遍历上下左右四个方向的时候先将四个方向随机打乱再进行遍历。先看看随机深度优先算法生成的地图，如果dfs起点随机选择（我这选择的是终点旁边的点作为dfs的起点）效果还是不错的，结果如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 1]  
在这里总结几个我在编程实现的过程中遇到的小问题：

1.  如果设置了迷宫的起点start（我设置的是左上角）和终点dest（我设置的是右下角），建议将深度优先遍历函数的起点设置为dest，将递归结束的条件设置为到达start。这样的好处是：能够增加游戏的难度，具体原因自行体会。
2.  将迷宫的长宽（包括边框）设置为奇数，每次往前遍历前进的距离为2而不是1，这样能确保生成的地图更加美观。如果设置每次前进的步长为1，生成的地图可能如下图所示：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 2]

python3的源代码为：

import numpy as np
    import time
    import random
    import copy
    
    class Maze(object):
    	def __init__(self, width = 11, height = 11):
    		# 迷宫最小长宽为5
    		assert width >= 5 and height >= 5, "Length of width or height must be larger than 5."
    		
    		# 确保迷宫的长和宽均为奇数
    		self.width = (width // 2) * 2 + 1
    		self.height = (height // 2) * 2 + 1
    		self.start = [1, 0]
    		self.destination = [self.height - 2, self.width - 1]
    		self.matrix = None
    
    	def print_matrix(self):
    		for i in range(self.height):
    			for j in range(self.width):
    				if self.matrix[i][j] == -1:
    					print('□', end = '')
    				elif self.matrix[i][j] == 0:
    					print('  ', end = '')
    				elif self.matrix[i][j] == 1:
    					print('■', end = '')
    			print('')
    
    	def generate_matrix_dfs(self):
    		# 地图初始化，并将出口和入口处的值设置为0
    		self.matrix = -np.ones((self.height, self.width))
    		self.matrix[self.start[0], self.start[1]] = 0
    		self.matrix[self.destination[0], self.destination[1]] = 0
    
    		visit_flag = [[0 for i in range(self.width)] for j in range(self.height)]
    
    		def check(row, col, row_, col_):
    			temp_sum = 0
    			for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
    				temp_sum += self.matrix[row_ + d[0]][col_ + d[1]]
    			return temp_sum <= -3
    
    		def dfs(row, col):
    			visit_flag[row][col] = 1
    			self.matrix[row][col] = 0
    			if row == self.start[0] and col == self.start[1] + 1:
    				return
    
    			directions = [[0, 2], [0, -2], [2, 0], [-2, 0]]
    			random.shuffle(directions)
    			for d in directions:
    				row_, col_ = row + d[0], col + d[1]
    				if row_ > 0 and row_ < self.height - 1 and col_ > 0 and col_ < self.width - 1 and visit_flag[row_][col_] == 0 and check(row, col, row_, col_):
    					if row == row_:
    						visit_flag[row][min(col, col_) + 1] = 1
    						self.matrix[row][min(col, col_) + 1] = 0
    					else:
    						visit_flag[min(row, row_) + 1][col] = 1
    						self.matrix[min(row, row_) + 1][col] = 0
    					dfs(row_, col_)
    
    		dfs(self.destination[0], self.destination[1] - 1)
    		self.matrix[self.start[0], self.start[1] + 1] = 0
    
    # 这里的长和宽设置的是50，但是实际生成的迷宫长宽会是51		
    maze = Maze(50, 50)
    maze.generate_matrix_dfs()
    maze.print_matrix()

## 2 递归分割算法 ##

// TODO

## 3 随机prim最小生成树算法 ##

随机prim最小生成树算法就是使用最小生成树的思想，将所有的奇数点（横纵坐标均为奇数的点）连成一个连通分量，而且每相邻的两个点之间的距离都为1，因此这个方法也可以看作是一种特殊的**随机广度优先算法**。

初始情况下，将除了四个边界之外的所有的位置初始化为0（空），然后从奇数点开始使用随机prim算法生成迷宫地图。由于思想类似广度优先，因此从起点到终点之间的路径比较简单（相比于使用随机深度优先算法生成的地图），很容易找到答案。运行结果如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 3]

python3的源代码为：

class Maze(object):
    	def __init__(self, width = 11, height = 11):
    		assert width >= 5 and height >= 5, "Length of width or height must be larger than 5."
    
    		self.width = (width // 2) * 2 + 1
    		self.height = (height // 2) * 2 + 1
    		self.start = [1, 0]
    		self.destination = [self.height - 2, self.width - 1]
    		self.matrix = None
    
    
    	def print_matrix(self):
    		for i in range(self.height):
    			for j in range(self.width):
    				if self.matrix[i][j] == -1:
    					print('□', end = '')
    				elif self.matrix[i][j] == 0:
    					print('  ', end = '')
    				elif self.matrix[i][j] == 1:
    					print('■', end = '')
    			print('')
    
    	# 虽然说是prim算法，但是我感觉更像随机广度优先算法
    	def generate_matrix_prim(self):
    		# 地图初始化，并将出口和入口处的值设置为0
    		self.matrix = -np.ones((self.height, self.width))
    
    		def check(row, col):
    			temp_sum = 0
    			for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
    				temp_sum += self.matrix[row + d[0]][col + d[1]]
    			return temp_sum < -3
    			
    		queue = []
    		row, col = (np.random.randint(1, self.height - 1) // 2) * 2 + 1, (np.random.randint(1, self.width - 1) // 2) * 2 + 1
    		queue.append((row, col, -1, -1))
    		while len(queue) != 0:
    			row, col, r_, c_ = queue.pop(np.random.randint(0, len(queue)))
    			if check(row, col):
    				self.matrix[row, col] = 0
    				if r_ != -1 and row == r_:
    					self.matrix[row][min(col, c_) + 1] = 0
    				elif r_ != -1 and col == c_:
    					self.matrix[min(row, r_) + 1][col] = 0
    				for d in [[0, 2], [0, -2], [2, 0], [-2, 0]]:
    					row_, col_ = row + d[0], col + d[1]
    					if row_ > 0 and row_ < self.height - 1 and col_ > 0 and col_ < self.width - 1 and self.matrix[row_][col_] == -1:
    						queue.append((row_, col_, row, col))
    
    		self.matrix[self.start[0], self.start[1]] = 0
    		self.matrix[self.destination[0], self.destination[1]] = 0
    
    
    maze = Maze(51, 51)
    maze.generate_matrix_prim()
    maze.print_matrix()

## 4 \*kruskal最小生成树算法 ##

kruskal最小生成树算法和prim类似，由于相邻的两个点之间的距离都是1，因此退化成随机选边法。初始化的时候首先将所有的奇数点的值设置为-1（墙壁），对于共有 n ∗ n n\*n n∗n个奇数点的图而言，共需要选择 n 2 − 1 n^2-1 n2−1个可连接的边。在需要判断连通图的个数的时候，并查集是最好用的，因此这里使用并查集实现。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 4]

python3代码

import numpy as np
    import time
    import random
    import copy
    
    class UnionSet(object):
    	"""
    	并查集
    	"""
    	def __init__(self, arr):
    		self.parent = {
        pos: pos for pos in arr}
    		self.count = len(arr)
    
    	def find(self, root):
    		if root == self.parent[root]:
    			return root
    		return self.find(self.parent[root])
    
    	def union(self, root1, root2):
    		self.parent[self.find(root1)] = self.find(root2)
    
    
    class Maze(object):
    	"""
    	迷宫生成类
    	"""
    	def __init__(self, width = 11, height = 11):
    		assert width >= 5 and height >= 5, "Length of width or height must be larger than 5."
    
    		self.width = (width // 2) * 2 + 1
    		self.height = (height // 2) * 2 + 1
    		self.start = [1, 0]
    		self.destination = [self.height - 2, self.width - 1]
    		self.matrix = None
    
    	def print_matrix(self):
    		for i in range(self.height):
    			for j in range(self.width):
    				if self.matrix[i][j] == -1:
    					print('□', end = '')
    				elif self.matrix[i][j] == 0:
    					print('  ', end = '')
    				elif self.matrix[i][j] == 1:
    					print('■', end = '')
    			print('')
    
    	# 最小生成树算法-kruskal（选边法）思想生成迷宫地图，这种实现方法最复杂。
    	def generate_matrix_kruskal(self):
    		# 地图初始化，并将出口和入口处的值设置为0
    		self.matrix = -np.ones((self.height, self.width))
    
    		def check(row, col):
    			ans, counter = [], 0
    			for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
    				row_, col_ = row + d[0], col + d[1]
    				if row_ > 0 and row_ < self.height - 1 and col_ > 0 and col_ < self.width - 1 and self.matrix[row_, col_] == -1:
    					ans.append([d[0] * 2, d[1] * 2])
    					counter += 1
    			if counter <= 1:
    				return []
    			return ans
    
    		nodes = set()
    		row = 1
    		while row < self.height:
    			col = 1
    			while col < self.width:
    				self.matrix[row, col] = 0
    				nodes.add((row, col))
    				col += 2
    			row += 2
    
    		unionset = UnionSet(nodes)
    		while unionset.count > 1:
    			row, col = nodes.pop()
    			directions = check(row, col)
    			if len(directions):
    				random.shuffle(directions)
    				for d in directions:
    					row_, col_ = row + d[0], col + d[1]
    					if unionset.find((row, col)) == unionset.find((row_, col_)):
    						continue
    					nodes.add((row, col))
    					unionset.count -= 1
    					unionset.union((row, col), (row_, col_))
    
    					if row == row_:
    						self.matrix[row][min(col, col_) + 1] = 0
    					else:
    						self.matrix[min(row, row_) + 1][col] = 0
    					break
    
    		self.matrix[self.start[0], self.start[1]] = 0
    		self.matrix[self.destination[0], self.destination[1]] = 0
    
    
    if __name__ == '__main__':
    	maze = Maze(51, 51)
    	maze.generate_matrix_kruskal()
    	maze.print_matrix()

## \*迷宫自动寻路-dfs ##

使用深度优先搜索寻路，我知道这肯定是最烂的迷宫寻路算法，但是性能可以接受，因此就先用这个吧~

# 迷宫寻路算法dfs
    	def find_path_dfs(self):
    		visited = [[0 for i in range(self.width)] for j in range(self.height)]
    
    		def dfs(path):
    			visited[path[-1][0]][path[-1][1]] = 1
    			if path[-1][0] == self.destination[0] and path[-1][1] == self.destination[1] - 1:
    				for pos in path:
    					self.matrix[pos[0]][pos[1]] = 1
    				return
    			for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
    				row_, col_ = path[-1][0] + d[0], path[-1][1] + d[1]
    				if row_ > 0 and row_ < self.height - 1 and col_ > 0 and col_ < self.width - 1 and visited[row_][col_] == 0 and self.matrix[row_][col_] == 0:
    					dfs(path + [[row_, col_]])
    
    		dfs([[self.start[0], self.start[1]]])

测试结果如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 5]

万事俱备，只欠东风！接下来就做可视化界面了，本篇完。

[python]: https://blog.csdn.net/qq_26822029/article/details/104132022
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200201140801986.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200131104515668.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200131105012432.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200131181553913.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200131215851804.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200131220606949.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2ODIyMDI5,size_16,color_FFFFFF,t_70