用Python编写迷宫游戏
发布日期:2021-06-29 01:31:11
浏览次数:2
分类:技术文章
本文共 7182 字,大约阅读时间需要 23 分钟。
文章目录
1、 项目概述
1.1 项目目标和主要内容
迷宫游戏是非常经典的游戏,在该项目要求随机生成一个迷宫,并求解迷宫1.2 项目的主要功能
随机生成迷宫并求解2、 项目设计
2.1项目总体框架
通过 Prim 算法随机创建迷宫 通过深度优先算法求解迷宫2.2 关键算法分析
prim算法:
算法思想: *设N=(V,E)是连通网,TE是N上最小生成树中边的集合。 *初始令U={U0},(U0∈V),TE={ }。 *在所有u∈U,v∈V-U的边(u,v)∈E中,找一条代价最小的边(u0,v0). *将(u0,v0)并入集合TE,同时v0并入U0. *重复上述操作直至U=V为止,则T=(V.TE)为N的最小生成树。3、设计步骤
3.1导入模块
import pyxelimport random
说明:
random库是随机生成库 pyxel库是一个用Python编写复古游戏的开发环境3.2生成迷宫
采用 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 #行和列为偶数时设置为0,0表示路,1表示墙 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 set_value(self, point, value): self.map[point[1]][point[0]] = value def get_value(self, point): return self.map[point[1]][point[0]] # 获取坐标(x,y)的邻居 返回数据结构为:二维数组 def get_neighbor(self, x, y, value): res = [] for i in range(4): if 0 < x + self.dx[i] < self.width - 1 and 0 < y + self.dy[i] < self.height - 1 and \ self.get_value([x + self.dx[i], y + self.dy[i]]) == value: res.append([x + self.dx[i], y + self.dy[i]]) return res # 获取坐标(x,y) 的邻墙 def get_neighbor_wall(self, point): return self.get_neighbor(point[0], point[1], 1) # 获取坐标(x,y) 的邻路 def get_neighbor_road(self, point): return self.get_neighbor(point[0], point[1], 0) def deal_with_not_visited(self, point, wall_position, wall_list): if not [point[0], point[1]] in self.visited: #步骤4.1 self.set_value(wall_position, 0) #步骤4.1.1 self.visited.append(point) #步骤4.1.2 wall_list += self.get_neighbor_wall(point)#步骤4.1.3 def generate(self): start = [1, 1] self.visited.append(start) wall_list = self.get_neighbor_wall(start) #步骤3 while wall_list: #步骤4 wall_position = random.choice(wall_list) #步骤4.1 neighbor_road = self.get_neighbor_road(wall_position) wall_list.remove(wall_position) self.deal_with_not_visited(neighbor_road[0], wall_position, wall_list)#进行4.1 self.deal_with_not_visited(neighbor_road[1], wall_position, wall_list) def is_out_of_index(self, x, y): return x == 0 or x == self.width - 1 or y == 0 or y == self.height - 1
3.3定义走迷宫函数
按照深度优先算法求解迷宫def dfs(self, x, y, path, visited=[]): # 越界 if self.is_out_of_index(x, y): return False # 访问过 or 撞墙 if [x, y] in visited or self.get_value([x, y]) == 1: return False visited.append([x, y]) path.append([x, y]) # over if x == self.width - 2 and y == self.height - 2: return True # 递归过程 for i in range(4): if 0 < x + self.dx[i] < self.width - 1 and 0 < y + self.dy[i] < self.height - 1 and \ self.get_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]: path.append([x, y]) # dfs def dfs_route(self): path = [] self.dfs(1, 1, path) ans = [[0, 1]] for i in range(len(path)): ans.append(path[i]) if 0 < i < len(path) - 1 and path[i - 1] == path[i + 1]: ans.append(path[i]) ans.append([width - 1, height - 2]) return ans # bfs def bfs_route(self): start = { 'x': 0, 'y': 1, 'prev': None} now = start q = [start] visited = [[start['x'], start['y']]] # 1、从起点出发,获取起点周围所有连通的路 # 2、如果该路没有走过,则加入队列 Q,否则跳过 同时记录其前驱节点 while q: now = q.pop(0) # 结束 if now['x'] == self.width - 2 and now['y'] == self.height - 2: break roads = my_maze.get_neighbor_road([now['x'], now['y']]) for road in roads: if not road in visited: visited.append(road) q.append({ 'x': road[0], 'y': road[1], 'prev': now}) ans = [] while now: ans.insert(0, [now['x'], now['y']]) now = now['prev'] ans.append([width - 1, height - 2]) return ans
3.4可视化
调用python的pyxel库进行可视化
class App: def __init__(self): #pyxel.init(width * pixel, height * pixel, caption='maze', border_width=10, border_color=0xFFFFFF) pyxel.init(width * pixel, height * pixel) self.death = True self.index = 0 self.route = [] self.step = 5 # 步长,数值越小速度越快,1:每次一格; 10:每次 1/10 格 self.color = start_point_color self.bfs_route = my_maze.bfs_route() self.dfs_route = my_maze.dfs_route() self.dfs_model = True 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 if not self.death: self.check_death() self.update_route() 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 pyxel.rect(y * pixel, x * pixel, pixel, pixel, color) pyxel.rect(0, pixel, pixel, pixel, start_point_color) pyxel.rect((width - 1) * pixel, (height - 2) * pixel, pixel, pixel, end_point_color) if self.index > 0: # draw route offset = pixel / 2 for i in range(len(self.route) - 1): curr = self.route[i] next = self.route[i + 1] self.color = backtrack_color if curr in self.route[:i] and next in self.route[:i] else route_color pyxel.line(curr[0] + offset, (curr[1] + offset), next[0] + offset, next[1] + offset, self.color) pyxel.circ(self.route[-1][0] + 2, self.route[-1][1] + 2, 1, head_color) def check_death(self): if self.dfs_model and len(self.route) == len(self.dfs_route) - 1: self.death = True elif not self.dfs_model and len(self.route) == len(self.bfs_route) - 1: self.death = True def update_route(self): index = int(self.index / self.step) self.index += 1 if index == len(self.route): # move if self.dfs_model: self.route.append([pixel * self.dfs_route[index][0], pixel * self.dfs_route[index][1]]) else: self.route.append([pixel * self.bfs_route[index][0], pixel * self.bfs_route[index][1]])App()
运行游戏,按s开始游戏
4、 结果
转载地址:https://blog.csdn.net/yuanfangyijun/article/details/111658030 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月05日 22时34分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Python爬虫实战:批量下载网站图片
2019-04-29
pycharm的十个小技巧,让你写代码效率翻倍
2019-04-29
python数据可视化神器,我就服它
2019-04-29
Python爬虫如何实用xpath爬取豆瓣音乐
2019-04-29
python爬取网站数据四种姿势,你值得拥有
2019-04-29
python爬虫JS逆向:X咕视频密码与指纹加密分析
2019-04-29
python爬取抖音短视频详细教程(附带源码)
2019-04-29
Python爬取腾讯动漫全站漫画详细教程(附带源码)
2019-04-29
python实现电商平台秒杀商品脚本程序
2019-04-29
520快乐~用python实现520祝福弹窗
2019-04-29
Python制作属于自己的有声小说
2019-04-29
Python制作专属有声小说(调用百度语音合成接口)
2019-04-29
用Python爬取淘宝2000款T T
2019-04-29
17行python代码爬取堆糖网所有MeiNv图片
2019-04-29
Python爬取15万条《我是余欢水》弹幕,还原一个丧到极致的中年人生
2019-04-29
Python 使用 PyQt5 开发的关机小工具分享
2019-04-29
可能是最全面的 python 字符串拼接总结
2019-04-29
利用Python爬取微博数据生成词云图片实例代码
2019-04-29
对Python3 解析html的几种操作方式小结
2019-04-29
Python基于opencv调用摄像头获取个人图片的实现方法
2019-04-29