如何⽤Python制作⼀个迷宫游戏
⽬录
⽣成迷宫
⾛出迷宫
可视化
如何制作一个个人网页总结
相信⼤家都玩过迷宫的游戏,对于简单的迷宫,我们可以⼀眼就看出通路,但是对于复杂的迷宫,可能要仔细寻好久,甚⾄耗费数天,然后可能还要分别从⼊⼝和出⼝两头寻才能的到通路,甚⾄也可能不到通路。
虽然⾛迷宫问题对于我们⼈类来讲⽐较复杂,但对于计算机来说却是很简单的问题。为什么这样说呢,因为看似复杂实则是有规可循的。
我们可以这么做,携带⼀根很长的绳⼦,从⼊⼝出发⼀直⾛,如果有岔路⼝就⾛最左边的岔⼝,直到⾛到死胡同或者到出路。如果是死胡同则退回上⼀个岔路⼝,我们称之为岔⼝ A,
这时进⼊左边第⼆个岔⼝,进⼊第⼆个岔⼝后重复第⼀个岔⼝的步骤,直到到出路或者死胡同退回来。当把该岔路⼝所有的岔⼝都⾛了⼀遍,还未到出路就沿着绳⼦往回⾛,⾛到岔⼝ A 的前⼀个路⼝ B,重复上⾯的步骤。
不知道你有没有发现,这其实就是⼀个不断递归的过程,⽽这正是计算机所擅长的。
上⾯这种⾛迷宫的算法就是我们常说的深度优先遍历算法,与之相对的是⼴度优先遍历算法。有了理论基础,下⾯我们就来试着⽤程序来实现⼀个⾛迷宫的⼩程序。
⽣成迷宫
⽣成迷宫有很多种算法,常⽤的有递归回溯法、递归分割法和随机 Prim 算法,我们今天是⽤的最后⼀种算法。
该算法的主要步骤如下:
1、迷宫⾏和列必须为奇数
2、奇数⾏和奇数列的交叉点为路,其余点为墙,迷宫四周全是墙
3、选定⼀个为路的单元格(本例选 [1,1]),然后把它的邻墙放⼊列表 wall
4、当列表 wall ⾥还有墙时:
4.1、从列表⾥随机选⼀⾯墙,如果这⾯墙分隔的两个单元格只有⼀个单元格被访问过
4.1.1、那就从列表⾥移除这⾯墙,同时把墙打通
4.1.2、将单元格标记为已访问
4.1.3、将未访问的单元格的邻墙加⼊列表 wall
4.2、如果这⾯墙两⾯的单元格都已经被访问过,那就从列表⾥移除这⾯墙
我们定义⼀个 Maze 类,⽤⼆维数组表⽰迷宫地图,其中 1 表⽰墙壁,0 表⽰路,然后初始化左上⾓为⼊⼝,右下⾓为出⼝,最后定义下⽅向向量。
class Maze:
def __init__(self, width, height):
self.width = width
self.height = height
self.map = [[0 if x % 2 == 1 and y % 2 == 1 else 1 for x in range(width)] for y in range(height)]
self.map[1][0] = 0 # ⼊⼝
self.map[height - 2][width - 1] = 0 # 出⼝
self.visited = []
# right up left down
self.dx = [1, 0, -1, 0]
self.dy = [0, -1, 0, 1]
接下来就是⽣成迷宫的主函数了。
def generate(self):
start = [1, 1]
self.visited.append(start)
wall_list = _neighbor_wall(start)
while wall_list:
wall_position = random.choice(wall_list)
neighbor_road = _neighbor_road(wall_position)
ve(wall_position)
self.deal_with_not_visited(neighbor_road[0], wall_position, wall_list)
self.deal_with_not_visited(neighbor_road[1], wall_position, wall_list)
该函数⾥⾯有两个主要函数 get_neighbor_road(point) 和 deal_with_not_visited(),前者会获得传⼊坐标点 point 的邻路节点,返回值是⼀个⼆维数组,后者 deal_with_not_visited() 函数处理步骤 4.1 的逻辑。
由于 Prim 随机算法是随机的从列表中的所有的单元格进⾏随机选择,新加⼊的单元格和旧加⼊的单元格被选中的概率是⼀样的,因此其分⽀较多,⽣成的迷宫较复杂,难度较⼤,当然看起来也更⾃然些。⽣成的迷宫。
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1]
[1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1]
[1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]
[1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
⾛出迷宫
得到了迷宫的地图,接下来就按照我们⽂⾸的思路来⾛迷宫即可。主要函数逻辑如下:
def dfs(self, x, y, path, visited=[]):
# outOfIndex
if self.is_out_of_index(x, y):
return False
# visited or is wall
if [x, y] in visited _value([x, y]) == 1:
return False
visited.append([x, y])
path.append([x, y])
#
if x == self.width - 2 and y == self.height - 2:
return True
# recursive
for i in range(4):
if 0 < x + self.dx[i] < self.width - 1 and 0 < y + self.dy[i] < self.height - 1 and \
<_value([x + self.dx[i], y + self.dy[i]]) == 0:
if self.dfs(x + self.dx[i], y + self.dy[i], path, visited):
return True
elif not self.is_out_of_index(x, y) and path[-1] != [x, y]:
很明显,这就是⼀个典型的递归程序。当该节点坐标越界、该节点被访问过或者该节点是墙壁的时候,
直接返回,因为该节点肯定不是我们要的路径的⼀部分,否则就将该节点加⼊被访问过的节点和
路径的集合中。
然后如果该节点是出⼝则表⽰程序执⾏结束,到了通路。不然就遍历四个⽅向向量,将节点的邻路传⼊函数 dfs 继续以上步骤,直到到出路或者程序所有节点都遍历完成。
来看看我们 dfs 得出的路径结果:
[[0, 1], [1, 1], [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 1], [8, 1], [9, 1], [9, 1], [8, 1], [7, 1], [6, 1], [5, 1], [5, 2], [5, 3], [6, 3], [7, 3], [8, 3], [9, 3], [9, 4], [9, 5], [9, 5], [9, 4], [9, 3], [8, 3], [7, 3], [7, 4], [7, 5], [7, 5], [7, 4], [7, 3], [6, 3], [5, 3], [4, 3], [3, 3], [2, 3], [1, 3], [1, 可视化
有了迷宫地图和通路路径,剩下的⼯作就是将这些坐标点渲染出来。今天我们⽤的可视化库是 pyxel,这是⼀个⽤来写像素级游戏的 Python 库,
当然使⽤前需要先安装下这个库。
Win ⽤户直接⽤ pip install -U pyxel命令安装即可。
Mac ⽤户使⽤以下命令安装:
brew install python3 gcc sdl2 sdl2_image gifsicle
pip3 install -U pyxel
先来看个简单的 Demo。
import pyxel
class App:
def __init__(self):
pyxel.init(160, 120)
self.x = 0
pyxel.run(self.update, self.draw)
def update(self):
self.x = (self.x + 1) % pyxel.width
def draw(self):
pyxel.cls(0)
<(self.x, 0, 8, 8, 9)
App()
类 App 的执⾏逻辑就是不断的调⽤ update 函数和 draw 函数,因此可以在 update 函数中更新物体的坐标,然后在 draw 函数中将图像画到屏幕即可。
如此我们就先把迷宫画出来,然后在渲染 dfs 遍历动画。
width, height = 37, 21
my_maze = Maze(width, height)
ate()
class App:
def __init__(self):
pyxel.init(width * pixel, height * pixel)
pyxel.run(self.update, self.draw)
def update(self):
if pyxel.btn(pyxel.KEY_Q):
pyxel.quit()
if pyxel.btn(pyxel.KEY_S):
self.death = False
def draw(self):
# draw maze
for x in range(height):
for y in range(width):
color = road_color if my_maze.map[x][y] is 0 else wall_color
<(y * pixel, x * pixel, pixel, pixel, color)
<(0, pixel, pixel, pixel, start_point_color)
<((width - 1) * pixel, (height - 2) * pixel, pixel, pixel, end_point_color)
App()
看起来还可以,这⾥的宽和⾼我分别⽤了 37 和 21 个像素格来⽣成,所以⽣成的迷宫不是很复杂,如果像素点很多的话就会错综复杂了。
接下⾥来我们就需要修改 update 函数和 draw 函数来渲染路径了。为了⽅便操作,我们在 init 函数中新增⼏个属性。
self.index = 0
self.step = 1 # 步长,数值越⼩速度越快,1:每次⼀格;10:每次 1/10 格
self.bfs_route = my_maze.bfs_route()
其中 index 和 step 是⽤来控制渲染速度的,在 draw 函数中 index 每次⾃增 1,然后再对 step 求余数得到当前的真实下标 real_index,简⾔之就是 index 每增加 step,real_index 才会加⼀,渲染路径向
前⾛⼀步。
def draw(self):
# draw maze
for x in range(height):
for y in range(width):
color = road_color if my_maze.map[x][y] is 0 else wall_color
<(y * pixel, x * pixel, pixel, pixel, color)
<(0, pixel, pixel, pixel, start_point_color)
<((width - 1) * pixel, (height - 2) * pixel, pixel, pixel, end_point_color)
if self.index > 0:
# draw route
offset = pixel / 2
for i in range(ute) - 1):
curr = ute[i]
next = ute[i + 1]
pyxel.line(curr[0] + offset, (curr[1] + offset), next[0] + offset, next[1] + offset, lor)
pyxel.ute[-1][0] + 2, ute[-1][1] + 2, 1, head_color)
def update(self):
if pyxel.btn(pyxel.KEY_Q):
pyxel.quit()
if pyxel.btn(pyxel.KEY_S):
self.death = False
if not self.death:
self.check_death()
self.update_route()
def check_death(self):
if self.dfs_model and ute) == len(self.dfs_route) - 1:
elif not self.dfs_model and ute) == len(self.bfs_route) - 1:
self.death = True
def update_route(self):
index = int(self.index / self.step)
self.index += 1
if index == ute): # move
if self.dfs_model:
else:
App()
⾄此,我们完整的从迷宫⽣成,到寻路径,再到路径可视化已全部实现。直接调⽤主函数 App() 然后按 S 键盘开启游戏
总结
今天我们⽤深度优先算法实现了迷宫的遍历,对于新⼿来说,递归这思路可能⽐较难理解,但这才是符合计算机思维的,随着经验的加深会理解越来越深刻的。其次我们⽤ pyxel 库来实现路径可视化,难点在于坐标的计算更新,细节⽐较多且繁琐,当然读者也可以⽤其他库或者直接⽤⽹页来实现也可以。
以上就是如何⽤ Python 制作⼀个迷宫游戏的详细内容,更多关于python 制作迷宫游戏的资料请关注其它相关⽂章!
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论