课程作业-基于Python实现的迷宫搜索游戏附源码
简单介绍一下
该项目不过是一个平平无奇的小作业,基于python3.8开发,目前提供两种迷宫生成算法与三种迷宫求解算法,希望对大家的学习有所帮助。
项目如果有后续的跟进将会声明,目前就这样吧~
效果图如下所示:

环境介绍
刚刚说了,这是python3.8,同时我们还包含了两个第三方库,这些我将会放在requirement.txt中。是的,我现在意识到它非常重要,因为跑别人代码没有它真的很容易环境冲突。
文件介绍
项目很简单,一共只有三个文件,所以如果是想要学习的朋友应该很容易可以梳理清楚文件的关系。
ui.py 是项目的UI设计以及运行入口,所有的逻辑都是基于此开发的;
Generate.py 是项目中负责生成迷宫的,提供了DFS、PRIM两种生成方式,具体的逻辑一会会介绍;
solve.py 是项目中负责迷宫求解的部分,提供了DFS、BFS、A*三种迷宫求解方案。
生成算法逻辑实现
该部分介绍一下两个迷宫生成算法的主要逻辑。
DFS 生成迷宫
深度搜素算法构建迷宫。我在实现该算法的时候和网络上的方法略有出入,大体流程如下:
- 首先构建迷宫大小的两个矩阵,分别位记录迷宫形状的
maze_map和记录迷宫访问状态的maze_state;同时还有一个记录DFS状态的memory列表。 - 将起点添加进上述三个空间中:
- 当
memory列表不为空时,开始循环:- 如果
memory最后一个元素可以向外扩展:即与该元素相邻的元素存在未被访问过的元素,则将该元素添加进入列表中,如果有多个未被访问过的元素,则随机选择一个进入,来确保迷宫的随机性。并将添加进来的元素的maze_state标记为1。 - 如果
memory最后一个元素无法向外扩展,则将该元素从memory中弹出。
- 如果
这里需要注意的时,如何判断一个元素是否可以向外扩展呢?这里的判断条件如下:
- 不可以超出迷宫限定的大小范围;
- 扩展的点不能被访问过
- 被扩展的点不能联通两个两条路线,防止出现环;

PRIM 生成迷宫
PRIM构建迷宫。该算法构建迷宫构建流程如下图所示:
- 构建一个迷宫大小的深度为5的向量,分别包含访问标记、四周墙体的状态。同时,包含一个memory来记忆以及打通的墙体;
- 将起点添加进去;
- 当memory长度不为空的时候,开始循环:
- 随机从memory中抽取一个节点m;
- 获取节点m所有合法的探索方向;
- 如果探索方向合法且新的节点未被访问过则添加进入memory,并标记为访问过,否则弹出memory。
同样的,这里的合法的探索方向也有限制条件:
- 不可以超出迷宫限定的大小范围;
- 扩展的点不能被访问过
通过PRIM生成的迷宫图效果如下图所示:

求解路径算法逻辑实现
在完成了迷宫设计后,接下来开始设计求解方法。
DFS 迷宫求解
DFS是经典的迷宫求解算法,通过深度搜索探索全部路径,直到到达终点,这在仅有一条通路的情况下是还不错的。但通常现实环境是复杂的,存在多条通路的,在这种情况下DFS很难获得最优路径。
接下来介绍DFS的实现流程:
- 建立地图的标记坐标,以及存放以及走过位置的
memory; - 开始循环:
- 如果当前坐标无法扩展新的坐标,则弹出;
- 如果当前坐标可以扩展新的坐标,则将新的坐标入栈,且新坐标的标志位设置为1;
- 若新的坐标为终点时,结束循环。
同样的,算法方向的选择也是核心问题之一:
- 新的坐标未超出地图位置;
- 新的坐标不是墙体且未被访问过。
BFS 迷宫求解
BFS也是常用的迷宫问题求解算法,通过广度优先的方法,通常来说广度优先搜索在路径搜索中可以得到最优解。如果迷宫有且仅有唯一解,该算法所探索的格子一般远高于DFS探索的空间,但如果迷宫中有多个路径存在时,该算法可以获得最优解。接下来时BFS算法逻辑:
- 建立地图的标记坐标,以及存放以及走过位置的
memory,同时我们还需要一个存放每一次迭代的所有坐标的列表; - 开始循环:
- 对坐标列表中的所有位置进行迭代,将可以到达的坐标添加到新的坐标列表中,并更新
memory和标志位; - 检查是否到达终点,到达则跳出循环。
- 对坐标列表中的所有位置进行迭代,将可以到达的坐标添加到新的坐标列表中,并更新
在方向的统计上,同BFS一样。
A* 迷宫求解
DFS虽然可以求得最优路径,但由于其的复杂度极高,且遍历空间极大的问题,在实际使用中通常不被采用;A*算法是在其后的佼佼者,通过启发式搜索的方式,在程序运行的阶段,对于其当前位置的移动损耗和预计损耗作为评估指标,来实现剪枝的作用。其流程如下所示:
- 建立地图的标记坐标、存放以及走过位置的
memory、损耗优先队列cost; - 开始循环:
- 对
cost最小的元素进行拓展; - 如果拓展结果为空,则弹出;
- 如果拓展结果存在值,则计算新节点的
cost,并添加入cost队列中。 - 检查是否到达终点,到达则跳出循环。
- 对
一些问题
-
还有一些迷宫生成方法没有加入,如递归分割迷宫生成法。
-
在UI输出坐标移动位置时,如果地图过大会导致页面卡死。
完整源码
https://download.csdn.net/download/DeepLearning_/88167896
相关文章:
课程作业-基于Python实现的迷宫搜索游戏附源码
简单介绍一下 该项目不过是一个平平无奇的小作业,基于python3.8开发,目前提供两种迷宫生成算法与三种迷宫求解算法,希望对大家的学习有所帮助。 项目如果有后续的跟进将会声明,目前就这样吧~ 效果图如下所示: 环境…...
差值结构的相互作用能
( A, B )---3*30*2---( 1, 0 )( 0, 1 ) 让网络的输入只有3个节点,AB训练集各由6张二值化的图片组成,让A,B中各有3个点,且不重合,统计迭代次数并排序。 其中有10组数据 差值结构 A-B 迭代次数 构造平均列 平均列…...
UI、UE、UX的区别
UI、UE、UX的区别 大部分程序员可能对UI、UE、UX这几个概念不是很熟悉,但在整个项目周期里,这些岗位还是很重要的,特别是对于产品公司,这些岗位对于一个产品是否能成功起着关键的作用。老规矩,我们先看看这三个缩写的定义。 UI:是User Interface英文的缩写,即用户界面的…...
RabbitMQ 教程 | 第10章 网络分区
👨🏻💻 热爱摄影的程序员 👨🏻🎨 喜欢编码的设计师 🧕🏻 擅长设计的剪辑师 🧑🏻🏫 一位高冷无情的编码爱好者 大家好,我是 DevO…...
Flask学习笔记_异步论坛(四)
Flask学习笔记_异步论坛(四) 1.配置和数据库链接1.exts.py里面实例化sqlalchemy数据库2.config.py配置app和数据库信息3.app.py导入exts和config并初始化到app上 2.创建用户模型并映射到数据库1.models/auth.py创建用户模型2.app.py导入模型并用flask-mi…...
K8S系列文章之 kubeasz部署K8S环境
自动化安装方式(kubeasz)* 生产环境推荐(首次安装下载相关配置和安装包)是基于Ansible实现的部署工具 简单介绍 每一具体k8s集群的详细配置参数文件 Ansible 任务配置文件 镜像安装包 安装部署步骤 前提 : 保证Ansib…...
nodejs和vue的关系--vue3教程
文章目录 总结性nodejs和vue的关系nodejs和vue产生关系的周边nodejs和vue的区别 总结性 vue是一套用于构建用户界面的前端框架,如果web项目中有前后端分离,前端项目想单独运行在服务器端,那么就要依赖nodeJs。 Vue的配套周边会和Node.js产生…...
前端大屏尺寸实现自适应屏幕大小
说在前面 目前很多业主在使用系统的时候都会有大屏的需求,很多屏幕并不会像我们开发的屏幕一样标准,比如1920*1080,这样我们就需要根据业主的屏幕尺寸进行适配,避免一些图表或文字在大屏中出现偏移,影响视觉观感。 方…...
leetcode 416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。 示例 1: 输入:nums [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。 示例 2&a…...
cesium加载三维模型3dtiles
1.将数据和代码放到一个目录下 目的:为避免跨域 输入cmd命令 python3 -m http.server 5500 2.三维服务地址 http://127.0.0.1:5500/data/mars3d-max-shihua-3dtiles-master/tileset.json 3.模型网页地址 http://127.0.0.1:5500/cesium/cesium%E5%8A%A0%E8%BD%…...
el-select控制单选还是多选
<el-form :inline"true" :model"form" class"demo-form-inline"><el-form-item><el-select v-model"form.properties_id" placeholder"请选择样品性质" clearable :multiple"multiple_properties"…...
nginx使用
1 安装 yum -y install gcc pcre-devel zlib-devel openssl openssl-devel yum install -y wget wget https://nginx.org/download/nginx-1.16.1.tar.gz tar -zxvf nginx-1.16.1.tar.gz cd nginx-1.16.1 ./configure --prefix/usr/local/nginx make make install2 目录 目录说…...
基于Jenkins+Python+Ubuntu+Docker的接口/UI自动化测试环境部署详细过程
基于JenkinsPythonUbuntuDocker的接口/UI自动化测试环境部署详细过程 1 Jenkins是什么?2 Jenkins目标是什么?3 什么是CI/CD?3.1 CI持续集成3.2 CD持续部署3.3 CD持续交付 4 Ubuntu环境4.1 环境需求4.2 实现思路 5 Ubuntu下安装Docker6 安装Jenkins6.1 拉…...
Linux|ubuntu下运行python
参考:ubuntu系统下切换python版本的方法 文章目录 python版本问题查看ubuntu下的所有python版本通过apt-get install可以安装不同版本python查看python版本号更新update-alternatives替代列表查看update-alternatives下的python版本切换python版本删除python版本 p…...
使用FreeMarker导出word文档(支持导出图片)
今天跟大家分享一下工作中比较实用的导出word 带图片的功能。 对于在idea开发中我们需要引入以下依赖: 2.对于eclipse 开发我们需要进入对应的jar包 这个必须放在lib下,同样也需要在当前项目的环境是加入该依赖 需要在MEAT-INF加入 首先制定word 导出…...
C/C++中变量按位操作
一、按位写入1 uint32_t writeBit (1 << 5) // 第5位的掩码 uint32_t value 0x12341234; // 设置第5位为1 value | writeBit;原理就是原值与掩码… 00010000进行按位相与,与0相交的位还是等于原来的值,与1相交的位则变为1。 二、按位写入0…...
uni、css——制作表格样式的模型
案例展示 这里以5列做展示(可随意调节) 案例代码 <view class"list"><view class"item" v-for"(item,index) in list" :key"index">1</view> <!-- 有内容 --><view clas…...
mac前端代码编辑 Sublime Text 4 Dev 中文v4.0(4151)
Sublime Text 4 for Mac是一款功能强大的代码编辑器,适合所有需要高效编写代码和进行代码管理的程序员使用。 快速响应:Sublime Text 4在加载文件和执行命令时非常快速,能够让用户在高效的开发过程中体验到无缝的交互。 多种语言支持&#…...
面试之HashMap
1.什么是集合框架 Java的集合主要有两个根接口Collection和Map派生出来的,Collection派生出来了三个子接口:List,Queue,Set。因此Java集合大致可分为List,Queue,Set,Map四种体系结构。 2.HashMap与TreeMap HashMap是直接实现Map接口,而Tree…...
promethues mysql-rules
groups: - name: mysql.rules rules: - alert: MysqlDown expr: mysql_up 0 for: 1s labels: severity: critical annotations: title: MySQL down description: "Mysql实例: 【{{ $labels.instance }}】, MySQL instance is down…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
蓝桥杯 2024 15届国赛 A组 儿童节快乐
P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡,轻快的音乐在耳边持续回荡,小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下,六一来了。 今天是六一儿童节,小蓝老师为了让大家在节…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
k8s从入门到放弃之HPA控制器
k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率(或其他自定义指标)来调整这些对象的规模,从而帮助应用程序在负…...
