1． 选题内容

迷宫游戏是一款经典的益智类游戏，玩法非常简单，但游戏内容多变。复杂迷宫游戏的设计则对地图和路径规划均提出了较高的要求。本课题旨在设计实现复杂迷宫环境下地图生成的游戏路径规划问题。系统的主要功能包含：游戏角色管理、地图绘制和生成，路径规划算法实现，其中路径规划算法是重点。在复杂的迷宫环境中，路径规划可利用多种人工智能方法求解：逻辑推理、启发式搜索、遗传算法均可作为候选解决方案。通过多种路径规划算法的实施，比较各种方法的优势和应用范围，进而提升计算机游戏的智能化水平。系统的设计要遵循计算机游戏的基本架构，为了保证效率，系统采用C++开发。

2． 研究方案

2.1 本选题的主要任务

1.了解计算机游戏体系架构；了解国内外行业标准、规范和技术发展趋势，理解其对环境以及社会可持续发展的影响，理解相关行业的政策和法律法规；

2.在指导教师指导下阅读国内外文献和自学相关知识，对游戏人工智能的寻找路径问题进行研究和分析。在复杂的迷宫环境中，利用多种人工智能方法求解并进行性能比较：逻辑推理通过对知识库的构建和访问，按照某种策略从已知事实出发推出结论；A*算法是对估价函数加上一些限制后得到的一种启发式搜索算法；遗传算法思想来源于生物进化过程,是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的以字符串表示状态空间搜索算法。

需要解决的问题有：

⑴ 学习各种人工智能路径规划方法：逻辑推理、启发式搜索、遗传算法；

⑵ 设计实现随机的复杂完美迷宫自动生成功能；

⑶ 设计实现较为复杂的迷宫环境下的路径求解程序；

⑷ 设计实现美观，简洁，人性化的软件界面，更好地展示算法之间的区别；

⑸ 总结归纳各种算法的优势和应用范围；

3.完成毕业设计（论文）外文翻译；

4.完成毕业设计论文并提交软件及相关文档。

2.2 技术方案的分析、选择

2.2.1 迷宫的自动生成

迷宫是一种非常经典的益智类游戏，在程序中我们通常把迷宫看成一个M*N的矩阵，矩阵的每个单元之间通过墙壁分隔开来，打通某些墙壁就可以实现单元之间的联通，一般的迷宫就是这样实现的。

但是上面描述的迷宫实现方法，有可能存在两个单元之间不连通，或者迷宫中存在环路，这样的迷宫是不完美的，因为它可能不存在解，或者在自动寻路的过程中出现死循环，这都是不合理的。所以必须采用正确的迷宫生成算法来生成perfect maze(完美迷宫，任意两个区域之间都联通，并且没有环路)。

程序拟采用递归回溯（Recursive Backtracking）来实现随机复杂完美迷宫的自动生成功能。递归回溯算法的大致思路是：

1. 一个M*N的迷宫矩阵，初始墙壁都存在

2. 随机选择一个单元作为当前单元，作为打通墙壁的起点

3. 随机选择当前单元的一个没有联通的邻接单元，并打通两个单元之间的墙壁，使之联通，然后将邻接单元作为新的当前单元（递归过程）

4. 重复第3步，直到当前单元与其所有邻接单元都是联通的，则退回上一单元，即将跳入当前单元的上一单元再次作为新的当前单元，继续重复第三步。（回溯过程）

5. 当最开始选择的单元被回退时，算法结束，生成完美迷宫

2.2.2 路径规划算法分析

1. 深度搜索和宽度搜素算法

逻辑推理算法是指通过对知识库的构建和访问，按照某种策略从已知事实出发推出结论。常见的策略有深度优先遍历（DFS：Depth-First-Search）和宽度优先遍历（BFS：Breadth-First-Search）。

深度优先遍历算法的一般思路是：

(1) 初始状态迷宫中所有单元都没有被访问过，以迷宫起点为顶点

(2) 按照一定的顺序访问当前单元的没有访问过的且可到达的领接单元，并将其设为当前单元

(3) 重复第(2）步，直到当前单元的所有可达领接单元都被访问过，当前单元回退为其上一单元，继续重复第(2)步，直至到达迷宫重点或者迷宫起点被回退

广度优先遍历的一般思路是：

(1) 初始状态迷宫中所有单元都没有被访问过，以迷宫起点为顶点

(2) 访问当前单元的所有可到达的领接单元，然后访问所有领接单元的可达领接单元，一直重复此过程

(3) 直至访问到迷宫终点或者所有单元都被访问

2. 启发式搜索

启发式搜索(Heuristically Search)又称为有信息搜索(Informed Search)，它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。但一般得到的解是令人能接受的解，通常并不一定是最佳解。

A*寻路算法是一种常见的启发式搜索算法，一般是通过估值函数对每个搜索位置进行评估，找到最好的位置，继续从这个位置如此循环进行搜索直到目标。估值函数的表示一般为：f(n) = g(n) + h(n)

其中f(n) 是节点n的估价函数，g(n)是从初始点到n结点的实际代价， h(n)是从n结点到目标点最佳路径的估价。不同的A*寻路算法有很多种估价函数，对于普通的A*算法通常使用当前结点到目标结点的距离来计算h(n)。

3. 遗传算法

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法的基本运算过程如下：

(1)初始化：设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。

(2)个体评价：计算群体P(t)中各个个体的适应度。

(3)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

(4)交叉运算：将交叉算子作用于群体。遗传算法中起核心作用的就是交叉算子。

(5)变异运算：将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。

(6)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。

2.2.3 界面与交互

作为一个游戏程序，美观、简洁的界面，便捷、良好的交互是非常必要的。而本程序不仅是一个迷宫游戏，更是一个学习理解随机复杂完美迷宫自动生成算法和路径规划算法的学习工具，所以界面和交互显得尤为重要。

对于复杂迷宫的绘制和自动生成，拟采用动态、过程可视化的方式来实现迷宫由最初的矩阵一步一步绘制成迷宫的效果。这样可以很直观到看到算法的执行逻辑，如何一步一步向下递归打破壁垒，如何回溯等等，使得原本抽象的算法变得更加易于理解。

对于路径规划算法的选择和寻路过程，本程序应该实现用户可以很便捷地切换不同路径规划算法，可以自定义设置寻路的起点和终点。并且当用户开始寻路后，游戏角色从起到走到终点的动态寻路过程也应该是可视的、逐步进行的，这样可以方便用户理解所选算法的执行逻辑，使抽象的寻路算法变得易于理解。程序还应该在迷宫右侧设计一个文本输出窗口，记录当前寻路算法的时间消耗、内存消耗、步数等信息，便于查看。

对于不同路径规划算法之间的比较，程序应该实现用户可以在所有路径算法中任意选择两种以上的算法来进行比较。比较的过程应该分为两部分，第一部分：程序按顺序把所选的算法来都进行一遍快速寻路，此寻路过程和单纯的寻路过程基本相同，但是整个过程会比单纯寻路要快，既能体现过程，形象地理解不同算法之间的差异，又不会太浪费时间。第二部分：所有算法寻路完毕后，右侧文本输出窗口切换为图表窗口，用户通过图表可以在时间、内存等维度比较不同算法的区别，并且可以切换折线、柱状图等不同变现形式。

2.2.4 算法、界面实现的语言、环境的选择

为了提高程序的性能，实现算法的可拓展，拟采用面向对象的C++语言。鉴于个人习惯和所长及程序的可跨平台性，界面相关的实现拟采用跨平台的C++图形用户界面应用程序框架——Qt。

2.3 实施技术方案所需的条件

1. 开发环境：

操作系统： Windows7

语言： C++11 Qt图形框架

IDE： Qt Creator

2. 运行环境：

操作系统：WindowsXP Windows7 Windows10 Linux MacOS

硬件要求：Intel I3处理器

内存256MB

硬盘128GB

2.4 存在的主要问题和技术关键

随机复杂完美迷宫自动生成过程的可视化，复杂的A*寻路算法和遗传算法是程序实现的技术关键。

如何将抽象的算法执行过程通过可视化的逐步分解，让用户更容易地理解和体会算法的逻辑是非常不容易的。这要求程序设计者不仅自身要对算法理解得足够透彻，还要有良好的表达、具象能力，用通俗易懂的图像变化来体现抽象的算法的逐步执行过程。所以必须要花费时间对算法进行深入、透彻的研究，对界面，交互进行反复的设计和体验。

2.5 预期能够达到的研究目标

1. 实现随机的复杂完美迷宫自动生成

用户可以自定义迷宫的大小，可以直观地看到由最初的矩阵状态一步一步生成复杂迷宫的动态过程，理解迷宫生成算法的执行过程。

2. 实现不同的路径规划算法的选择

用户可以自定义寻路的起点和终点，可以直观地看到角色从起点一步一步走到终点的全过程，理解不同路径规划算法的执行过程。

3. 实现以图表的方式形象地查看不同算法间的不同维度的区别

用户可以自定义进行比较的算法，可以直观地看到每种算法角色从起点到终点的快速过程，感受不同路径规划算法的差别，并且可以以图表的方式在不同维度对算法进行更加数据化的比较。

4. 总结归纳各种算法的优势和应用范围

毕业论文中要对不同路径规划算法的区别，各自的优缺点、试用场景等方面进行深入的分析和阐述，并提出可能的改进策略。

3． 课题计划进度表

4． 参考文献

1. 百度百科[启发式搜索][遗传算法][深度优先遍历][广度优先遍历]等词条

2. 《四种寻路算法并比较》 大招至胜的博客

3. 《游戏编程算法与技巧》Sanjay Madhav著