摘  要

经典的迷宫游戏是在一个由障碍物和通路组成的复杂环境中，玩家通过上下左右操作使得游戏角色从左上角的入口点走到右下角的出口点的过程。智能迷宫游戏系统是一个可以自动生成用户自定义大小和起始位置等信息的随机复杂有解迷宫，然后选择不同的路径规划算法寻找一条从起始点到目标点的最优路径，并且可以将迷宫生成过程和寻路过程动态地展示出来的系统。它的主要功能包括：游戏角色管理、复杂有解迷宫生成、自动寻路、输出算法执行信息和设置系统单步运行速度等。

本文的研究工作主要包括：输入迷宫的宽度、高度和起始点位置，然后生成随机、复杂、有解的迷宫；从深度优先搜索、宽度优先搜索、启发式搜索和遗传算法等四种路径算法选择一种算法来寻找从起始点到目标点的最优路径并对四种算法的运行结果进行分析和比较；动态可控地展示迷宫生成和路径规划过程；结合实际软件开发情况，总结不同路径规划算法的优势和适用范围。

关键词：迷宫游戏，动态展示，人工智能，迷宫生成算法，路径规划算法

Abstract

The classic maze game is a process that player makes the game character move from the entry point to the exit point through the up, down, left and right operation. The intelligent maze game system is a system which can automatically generate a random and complex maze with users’ entering the size, starting position and other information, and then users can choose a different path planning algorithm to find an optimal path from the starting point to the target point, and the maze generation process and the pathfinder process can be dynamically displayed. Its main functions include: game character management, random complex maze generation, automatic path finding, output algorithm execution information and set the system single step speed and so on.

The research work of this paper mainly includes inputting the width, height and starting point position of the maze, and then generating random, complex maze; choose an algorithm from depth-first search, width-first search, heuristic search and genetic algorithm to find the optimal path from the starting point to the target point and analyze and compare the results of the four algorithms; dynamically controllable display of maze generation and path planning; combined with the actual software development, summed up the advantages of different path planning algorithm and the scope of application.

Keyword: maze game, dynamic display, artificial intelligence, maze generation algorithm, path planning algorithm