丘成桐中学数学奖参赛论文丘成桐中学数学奖参赛论文.pdf

丘成桐中学数学奖参赛论文 明园迷宫设障游戏中的迷宫算法研究 赛队员：申靓博，谭侃然 指导老师：纪荣强 赛学校：北京四中 1 圆明园迷宫设障游戏中的迷宫算法研究 摘要 现在的游戏为了玩家的方便，都开始提供迷宫的自动导航功能。对于大规模 的迷宫，要提供实时的导航，必须要有高效的迷宫算法。本文着重描述了 A*算 法的思想，然后从理论上证明了算法的可接纳性和一致性，最后对几种算法的运 行效率进行了比较，并在算法实现过程中提出了改进算法。 关键词：迷宫算法，A*算法，迪杰斯特拉算法 Abstract Now the game for players convenience, are beginning to offer a maze of automatic navigation function. For the large-scale maze, to provide real-time navigation of the maze algorithm must be efficient. In this paper, describes the A * algorithm, and then theoretically proved that the algorithm is the admissibility and consistency, the last of the operational efficiency of several algorithms were compared and proposed algorithm of the improvements. Keywords: maze algorithm, A star algorithm, Dijkstra algorithm 2 1 问题背景 随着现代科技的发展，计算机开始普及，计算机游戏也达 了空前的繁荣。 提 游戏，不得不提 游戏中的迷宫。国内游戏中最早出现的最有名的迷宫当数 仙剑奇侠传1 中的迷宫，曾令多少玩家为之痴迷。随着网络的普及，网络游戏正 如火如荼的发展，当然，网络游戏中也少不了迷宫地图，但现在大部分游戏为方 便玩家的操作，都提供了一种称为自动导航、自动寻路的功能，只要在当前地图 中确定出发点与目的点，系统就能自动找出一条可行的、最优 （局部最优）的路 径并使玩家自动移动到目的地。 本文研究的就是如何能够在迷宫地图中更快地找 一条路径满足当前的移 动需求，并且考虑 游戏中有多个玩家同时进行时，会相互构成动态障碍，从而 产生了一种动态设障迷宫算法改进的需求。 本文以圆明园迷宫为例来探索迷宫路径搜索算法的一种改进。 圆明园迷宫相传是由 大利传教士郎士宁、法国传教士蒋友仁、艾启蒙等为 中国皇帝设计修建。迷宫由宫墙和凉亭组成。宫墙高1.60米，总长1660米，占 地6000 平方米。墙身由特别烧制有 “万”字不 头的图案的灰砖砌成。凉亭位 于迷宫中心，高11 米，汉白玉建筑，亭柱上雕镂着精美的花纹图案，半圆形的 亭顶突出欧式建筑风格，站在亭中俯首四望，迷阵一览无遗。 清代，每当中秋之夜，皇帝在此举行盛大灯火晚会，嫔妃宫女们手持黄色宫 灯，由四门而入，为争先 达阵中凉亭，嫔妃们追逐嬉戏，各选捷径，此时皇帝 于凉亭中，四面望去，只见无数黄花灯在阵内游动，甚为壮观。所以，迷宫又 称为黄花阵、万花阵。 2 算法理论分析 传统的迷宫算法主要有两种，深度优先搜索算法和DIJKSTRA （迪杰斯特拉） 算法。 2．1 深度优先搜索算法 深度优先搜索算法是最基本的一种搜索算法，这种算法能保证只要迷宫中有 通路，算法一定能返回一条通路，但当迷宫中有多条通路可走时，这种算法一般 情况下给不出最优结果。而且，同样的搜索条件可能给出不同的路径。 深度优先搜索算法是把最近刚产生的结点优先扩展，直 达 一定的深度限 制。若未找到目标或无法再扩展时，再回朔 另一个结点继续扩