计算机软件实习项目三 —— 闯迷宫 (实验准备)

迷宫 (实验准备)"/>

计算机软件实习项目三 —— 闯迷宫 (实验准备)

目录

一、实验目的

二、算法学习

四、难点和解决方案

五、参考资料

一、实验目的

1.随机生成一个迷宫，并求解迷宫； 要求游戏支持玩家走迷宫，和系统走迷宫路径两种模式。

2.玩家走迷宫，通过键盘方向键控制，并在行走路径上留下痕迹；系统走迷宫路径要求基于A*算法实现，输出走迷宫的最优路径并显示。

3.设计交互友好的游戏图形界面。

二、算法学习

• 深度优先算法（DFS）

       深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth             First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的         相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等           等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深           入到不能再深入为止，而且每个节点只能访问一次。

• A*算法

       A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题           的常用启发式算法。A*算法作为Dijkstra算法的扩展，因其高效性而被广泛应用于寻路及图的         遍历。

       公式表示为： f(n)=g(n)+h(n),

       其中，
       f(n) 是从初始状态经由状态n到目标状态的代价估计，
       g(n) 是在状态空间中从初始状态到状态n的实际代价，
       h(n) 是从状态n到目标状态的最佳路径的估计代价（欧几里（斜边的长度）/曼哈顿距离（x的         距离+y的距离差））。
三、编程语言和平台

       编程语言：JAVA

       IntelliJ IDEA Community Edition 2021.2.1

四、难点和解决方案

• 如何将方格填入数字。先制作迷宫数组，利用循环数定坐标，再画格子。
• 广度优先和A*算法的编写。百度查找资料。

五、参考资料

深度广度优先算法、A*算法_八爪大头鱼-CSDN博客_a算法是广度优先算法吗