丘成桐中学数学奖参赛论文丘成桐中学数学奖参赛论文.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 深度优先有哪些信誉好的足球投注网站算法 深度优先有哪些信誉好的足球投注网站算法是最基本的一种有哪些信誉好的足球投注网站算法，这种算法能保证只要迷宫中有 通路，算法一定能返回一条通路，但当迷宫中有多条通路可走时，这种算法一般 情况下给不出最优结果。而且，同样的有哪些信誉好的足球投注网站条件可能给出不同的路径。 深度优先有哪些信誉好的足球投注网站算法是把最近刚产生的结点优先扩展，直 达 一定的深度限 制。若未找到目标或无法再扩展时，再回朔 另一个结点继续扩