当前位置: 首页 > news >正文

课程作业-基于Python实现的迷宫搜索游戏附源码

简单介绍一下

该项目不过是一个平平无奇的小作业,基于python3.8开发,目前提供两种迷宫生成算法与三种迷宫求解算法,希望对大家的学习有所帮助。

项目如果有后续的跟进将会声明,目前就这样吧~

效果图如下所示:
在这里插入图片描述

环境介绍

刚刚说了,这是python3.8,同时我们还包含了两个第三方库,这些我将会放在requirement.txt中。是的,我现在意识到它非常重要,因为跑别人代码没有它真的很容易环境冲突。

文件介绍

项目很简单,一共只有三个文件,所以如果是想要学习的朋友应该很容易可以梳理清楚文件的关系。

ui.py 是项目的UI设计以及运行入口,所有的逻辑都是基于此开发的;

Generate.py 是项目中负责生成迷宫的,提供了DFSPRIM两种生成方式,具体的逻辑一会会介绍;

solve.py 是项目中负责迷宫求解的部分,提供了DFSBFSA*三种迷宫求解方案。

生成算法逻辑实现

该部分介绍一下两个迷宫生成算法的主要逻辑。

DFS 生成迷宫

深度搜素算法构建迷宫。我在实现该算法的时候和网络上的方法略有出入,大体流程如下:

  1. 首先构建迷宫大小的两个矩阵,分别位记录迷宫形状的maze_map和记录迷宫访问状态的maze_state;同时还有一个记录DFS状态的memory列表。
  2. 将起点添加进上述三个空间中:
  3. memory列表不为空时,开始循环:
    1. 如果memory最后一个元素可以向外扩展:即与该元素相邻的元素存在未被访问过的元素,则将该元素添加进入列表中,如果有多个未被访问过的元素,则随机选择一个进入,来确保迷宫的随机性。并将添加进来的元素的maze_state标记为1。
    2. 如果memory最后一个元素无法向外扩展,则将该元素从memory中弹出。

这里需要注意的时,如何判断一个元素是否可以向外扩展呢?这里的判断条件如下:

  1. 不可以超出迷宫限定的大小范围;
  2. 扩展的点不能被访问过
  3. 被扩展的点不能联通两个两条路线,防止出现环;

在这里插入图片描述

PRIM 生成迷宫

PRIM构建迷宫。该算法构建迷宫构建流程如下图所示:

  1. 构建一个迷宫大小的深度为5的向量,分别包含访问标记、四周墙体的状态。同时,包含一个memory来记忆以及打通的墙体;
  2. 将起点添加进去;
  3. 当memory长度不为空的时候,开始循环:
    1. 随机从memory中抽取一个节点m;
    2. 获取节点m所有合法的探索方向;
    3. 如果探索方向合法且新的节点未被访问过则添加进入memory,并标记为访问过,否则弹出memory。

同样的,这里的合法的探索方向也有限制条件:

  1. 不可以超出迷宫限定的大小范围;
  2. 扩展的点不能被访问过

通过PRIM生成的迷宫图效果如下图所示:
在这里插入图片描述

求解路径算法逻辑实现

在完成了迷宫设计后,接下来开始设计求解方法。

DFS 迷宫求解

DFS是经典的迷宫求解算法,通过深度搜索探索全部路径,直到到达终点,这在仅有一条通路的情况下是还不错的。但通常现实环境是复杂的,存在多条通路的,在这种情况下DFS很难获得最优路径。
接下来介绍DFS的实现流程:

  1. 建立地图的标记坐标,以及存放以及走过位置的memory;
  2. 开始循环:
    1. 如果当前坐标无法扩展新的坐标,则弹出;
    2. 如果当前坐标可以扩展新的坐标,则将新的坐标入栈,且新坐标的标志位设置为1;
    3. 若新的坐标为终点时,结束循环。

同样的,算法方向的选择也是核心问题之一:

  1. 新的坐标未超出地图位置;
  2. 新的坐标不是墙体且未被访问过。

BFS 迷宫求解

BFS也是常用的迷宫问题求解算法,通过广度优先的方法,通常来说广度优先搜索在路径搜索中可以得到最优解。如果迷宫有且仅有唯一解,该算法所探索的格子一般远高于DFS探索的空间,但如果迷宫中有多个路径存在时,该算法可以获得最优解。接下来时BFS算法逻辑:

  1. 建立地图的标记坐标,以及存放以及走过位置的memory,同时我们还需要一个存放每一次迭代的所有坐标的列表;
  2. 开始循环:
    1. 对坐标列表中的所有位置进行迭代,将可以到达的坐标添加到新的坐标列表中,并更新memory和标志位;
    2. 检查是否到达终点,到达则跳出循环。

在方向的统计上,同BFS一样。

A* 迷宫求解

DFS虽然可以求得最优路径,但由于其的复杂度极高,且遍历空间极大的问题,在实际使用中通常不被采用;A*算法是在其后的佼佼者,通过启发式搜索的方式,在程序运行的阶段,对于其当前位置的移动损耗和预计损耗作为评估指标,来实现剪枝的作用。其流程如下所示:

  1. 建立地图的标记坐标、存放以及走过位置的memory、损耗优先队列cost;
  2. 开始循环:
    1. cost最小的元素进行拓展;
    2. 如果拓展结果为空,则弹出;
    3. 如果拓展结果存在值,则计算新节点的cost,并添加入cost队列中。
    4. 检查是否到达终点,到达则跳出循环。

一些问题

  1. 还有一些迷宫生成方法没有加入,如递归分割迷宫生成法。

  2. 在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是什么&#xff1f;2 Jenkins目标是什么&#xff1f;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

参考&#xff1a;ubuntu系统下切换python版本的方法 文章目录 python版本问题查看ubuntu下的所有python版本通过apt-get install可以安装不同版本python查看python版本号更新update-alternatives替代列表查看update-alternatives下的python版本切换python版本删除python版本 p…...

使用FreeMarker导出word文档(支持导出图片)

今天跟大家分享一下工作中比较实用的导出word 带图片的功能。 对于在idea开发中我们需要引入以下依赖&#xff1a; 2.对于eclipse 开发我们需要进入对应的jar包 这个必须放在lib下&#xff0c;同样也需要在当前项目的环境是加入该依赖 需要在MEAT-INF加入 首先制定word 导出…...

C/C++中变量按位操作

一、按位写入1 uint32_t writeBit (1 << 5) // 第5位的掩码 uint32_t value 0x12341234; // 设置第5位为1 value | writeBit;原理就是原值与掩码… 00010000进行按位相与&#xff0c;与0相交的位还是等于原来的值&#xff0c;与1相交的位则变为1。 二、按位写入0…...

uni、css——制作表格样式的模型

案例展示 这里以5列做展示&#xff08;可随意调节&#xff09; 案例代码 <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是一款功能强大的代码编辑器&#xff0c;适合所有需要高效编写代码和进行代码管理的程序员使用。 快速响应&#xff1a;Sublime Text 4在加载文件和执行命令时非常快速&#xff0c;能够让用户在高效的开发过程中体验到无缝的交互。 多种语言支持&#…...

面试之HashMap

1.什么是集合框架 Java的集合主要有两个根接口Collection和Map派生出来的&#xff0c;Collection派生出来了三个子接口&#xff1a;List,Queue,Set。因此Java集合大致可分为List,Queue,Set,Map四种体系结构。 2.HashMap与TreeMap HashMap是直接实现Map接口&#xff0c;而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…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

HTML前端开发:JavaScript 获取元素方法详解

作为前端开发者&#xff0c;高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法&#xff0c;分为两大系列&#xff1a; 一、getElementBy... 系列 传统方法&#xff0c;直接通过 DOM 接口访问&#xff0c;返回动态集合&#xff08;元素变化会实时更新&#xff09;。…...