使用prime算法生成迷宫
使用递归算法走迷宫
使用pygame做可视化展示
游戏截屏
prime算法生成迷宫
递归算法解迷宫
背景如下:
迷宫以二维数组表示,其中0为路,1为墙,玩家只能在路上行走,不能穿越墙。
由于逻辑比较简单,就直接自己实现了,主要思路如下:
1. 玩家初始位置定位在迷宫入口
if __name__ == '__main__':
# 生成迷宫与入口
size = random_maze_size()
MAZE, ENTRANCE, EXIT = generate_maze(size, size)
SOLVE_THREAD = threading.Thread(target=solve_maze, args=(MAZE, ENTRANCE, EXIT, draw_maze))
SOLVE_THREAD.start()
2. 获取玩家上下左右四个相邻位置的值和位置
# 单元格类型
# 0 - 路,1 - 墙,2-走过的路,4-死胡同,不在迷宫里或是已经走过又回退回来,说明此路不通
class CellType:
ROAD = 0
WALL = 1
WALKED = 2
DEAD = 3
def valid(maze, x, y):
if x < 0 or y < 0:
return False
if x >= len(maze) or y >= len(maze):
return False
val = maze[y][x]
if val == CellType.WALL or val == CellType.DEAD:
return False
return val, x, y
def neighbors(maze, pos):
x, y = pos
t, r, d, l = valid(maze, x, y - 1), valid(maze, x + 1, y), valid(maze, x, y + 1), valid(maze, x - 1, y)
return t, r, d, l
3. 对获取到的相邻四个位置进行处理,返回最推荐走的位置与值
# 单元格类型
# 0 - 路,1 - 墙,2-走过的路,4-死胡同,不在迷宫里或是已经走过又回退回来,说明此路不通
class CellType:
ROAD = 0
WALL = 1
WALKED = 2
DEAD = 3
def suggest_pos(cells):
arr = []
# 遍历相邻4个位置
for cell in cells:
# 如果不是False,说明是路,可能是没走过的路,也可能是走过的路,添加到数组中
if cell:
arr.append(cell[0])
# 如果是False,说明是墙或者死胡同,不再考虑
else:
arr.append(CellType.DEAD)
# 优先推荐没走过的路,根据我们CellType中的定义,没走过的路值最小,其次是走过的路
return cells[arr.index(min(arr))]
4. 对推荐的位置进行处理
如果是没走过的路,直接走,并把当前的位置标记为已走过
如果是走过的路,也走,并把当前的位置标记为死胡同,此路不通
如果没有推荐的路,游戏结束,迷宫有问题,无解
走 这个动作,就用到了递归,继续调用solve_maze方法,位置参数改为推荐的下一步的位置
重复以上步骤直到当前位置与出口位置重叠,迷宫走完,游戏结束
next_pos = suggest_pos((t, r, d, l))
if next_pos:
if next_pos[0] == CellType.WALKED:
mark_dead(maze, pos)
else:
mark_walked(maze, pos)
return solve_maze(maze, (next_pos[1], next_pos[2]), end)
else:
mark_dead(maze, pos)
return False
pygame做界面展示
基于pygame,比较简单,具体见 我的github