摘  要

迷宫游戏是一款经典游戏，迷宫左侧有一个入口，右侧有一个出口，并有一些障碍物散布其中，需要寻找一条从入口到出口且不走出迷宫的道路。复杂迷宫游戏的设计使用迷宫生成算法绘制和生成包括唯一解、多解和无解多种情况的精细复杂迷宫地图，且使用路径规划算法在人工智能寻路中具有较高的时间效率和空间效率。本文设计并实现了复杂迷宫环境下地图生成的游戏路径规划问题，完成了系统的主要功能：游戏角色管理、地图绘制和生成，路径规划算法实现。

针对上述迷宫问题，作者采用深度优先搜索算法，迭代加深深度优先搜索算法，广度优先搜索算法，双向广度优先搜索算法，蒙特卡洛算法，启发式搜索算法，迭代加深启发式搜索算法以及遗传算法八种人工智能方法，实现系统在复杂的迷宫环境下，求解寻找路径问题，并比较了各种方法的优势和应用范围，针对具体问题的特征进行特定的优化，使得在求解问题时能达到最高的效率获得最好的结果，进而提升计算机游戏的智能化水平。

关键词：迷宫；游戏；人工智能；迷宫生成算法；路径规划算法

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