摘  要
迷宫游戏是一款经典游戏，迷宫左侧有一个入口，右侧有一个出口，并有一些障碍物散布其中，需要寻找一条从入口到出口且不走出迷宫的道路。复杂迷宫游戏的设计使用迷宫生成算法绘制和生成包括唯一解、多解和无解多种情况的精细复杂迷宫地图，且使用路径规划算法在人工智能寻路中具有较高的时间效率和空间效率。本文设计并实现了复杂迷宫环境下地图生成的游戏路径规划问题，完成了系统的主要功能：游戏角色管理、地图绘制和生成，路径规划算法实现。
针对上述迷宫问题，作者采用深度优先搜索算法，迭代加深深度优先搜索算法，广度优先搜索算法，双向广度优先搜索算法，蒙特卡洛算法，启发式搜索算法，迭代加深启发式搜索算法以及遗传算法八种人工智能方法，实现系统在复杂的迷宫环境下，求解寻找路径问题，并比较了各种方法的优势和应用范围，针对具体问题的特征进行特定的优化，使得在求解问题时能达到最高的效率获得最好的结果，进而提升计算机游戏的智能化水平。
关键词：迷宫；游戏；人工智能；迷宫生成算法；路径规划算法
Abstract
Maze Game is a classic game. Maze’s left have entrance, on the right there is an exit, and there are some obstacles spread among them. The way from the entrance to the exit and not out of the maze is needed to find. The design of complex maze game uses maze-generation-algorithm to draw and generate intricate maze map, which including a variety of situation, such as a unique solution, multiple solution and no solution. What's more, it uses path planning algorithm in Artificial Intelligence pathfinding has highly time efficiency and space efficiency. This article mainly discusses on designing and implementing the problem of path planning on the complex maze map. System’s main function include: game role management, map drawing and generation, path planning algorithm implement.
In response to these maze problem, author uses Depth-First-Search algorithm, Iterative deepening Depth-First-Search algorithm, Breadth-First-Search algorithm,  Bi-Directional Breadth-First-Search algorithm, Monte Carlo method, Heuristic search algorithm, Iterative deepening heuristic search algorithm, and Genetic Algorithm that eight kinds of artificial intelligence methods, implementing the system in a complex maze environment, to solve the pathfinding problem. In addition, it compares the advantages of various methods and the range of applications. It aims to optimize the characteristic of the specific issues, so that solving problems to achieve maximum efficiency and getting the best results. Thus enhance the intelligence level of the computer game.
Keyword: maze; game; artificial intelligence; Maze-generation-algorithm; path planning algorithm
目录
第1章  绪论 1
1.1 研究背景及意义 1
1.2 相关理论 2
1.3 本文工作 4
1.4 本文结构 4
第2章  系统需求 6
2.1 系统功能设计 6
2.2 游戏角色管理模块 7
2.2.1 用户登录 7
2.2.2 权限管理 7
2.3 地图绘制和生成模块 9
2.3.1 迷宫绘制策略选择 9
2.3.2 迷宫生成 10
2.4 路径规划算法实现模块 11
2.4.1 路径规划策略选择 11
2.4.2 路径绘制 12
2.5 迷宫辅助模块 12
2.5.1 迷宫管理 12
2.5.2 查看区间路径 13
2.6 非功能性需求 13
2.7 本章小结 14
第3章  系统设计 16
3.1 系统详细设计 16
3.2 游戏角色管理模块 16
3.2.1 功能描述 16
3.2.2 分析流程 16
3.2.3  IPO图 17
3.2.4 接口设计 18
3.2.5 存储结构 18
3.3 地图绘制和生成模块 19
3.3.1 功能描述 19
3.3.2 分析流程 19
3.3.3  IPO图 19
3.3.4 接口设计 21
3.3.5 存储结构 21
3.4 路径规划算法实现模块 22
3.4.1 功能描述 22
3.4.2 分析流程 22
3.4.3  IPO图 22
3.4.4 接口设计 23
3.4.5 存储结构 24
3.5 迷宫辅助模块 24
3.5.1 功能描述 24
3.5.2 分析流程 24
3.5.3  IPO图 25
3.5.4 接口设计 26
3.5.5 存储结构 27
3.6 本章小结 27
第4章  算法设计 28
4.1 迷宫生成模块 28
4.1.1 唯一解迷宫生成算法 28
4.1.2 多解迷宫生成算法 29
4.1.3 无解迷宫生成算法 30
4.2 路径规划算法实现模块 31
4.2.1 深度优先搜索算法 31
4.2.2 迭代加深深度优先搜索算法 32
4.2.3 广度优先搜索算法 34
4.2.4 双向广度优先搜索算法 35
4.2.5 蒙特卡洛搜索算法 36
4.2.6 启发式搜索算法 37
4.2.7 迭代加深启发式搜索算法 39
4.2.8 遗传算法 41
4.3 本章小结 43
第5章  系统实现 44
5.1 实现环境 44
5.2 各种路径规划算法运行时间比较 44
5.3 各种路径规划算法效率分析 46
5.4 界面展示 49
总结与展望 52
致谢 53
参考文献 54