下载文档原格式
浅谈游戏中自动寻路算法的实现与应用作者：蒋恺来源：《中国新通信》 2018年第2期在信息技术的支持下，互联网进入了迅猛发展期，各种网游、页游大量出现，受到不同玩家的喜爱与青睐。
当然为了逐步扩大受众群，需要不断的优化游戏，满足玩家对游戏的需求，其中自动寻路算法就是十分关键的技术之一，提升了游戏角色在虚拟游戏环境中的灵活性，更利于对游戏角色的控制，是判断游戏质量的重要标准之一”1。
一、关于自动寻路算法的概述1.1自动寻路算法的原理在自动寻路算法中最常用的为A*算法，这属于启发式的算法，被广泛应用于游戏中的路径搜索【21。
主要是节点的设置，具有记录、搜索进度的功能，通过节点在游戏地图中移动，当搜寻到目标位置时就结算，否则会进一步搜索记录目标位置周围相邻的位置。
举例而言，游戏角色最初的位置就是开始节点，将要到达的目标位置设置为目标节点，在两者之间存在一定的障碍物和可以顺利通行的路径，黑色部分为障碍物，白色部分为可通行路径，具体如下图1所示：在设计A*算法时采用的基本原理，其实为最短路径算法，在整个游戏地图中，从起始节点到目标节点的路径多种多样，将这些全部读入到开放式列表中，再通过与目标节点距离最近的节点进行对比，从而找到最优路径”1。
将上图1中的起始节点设置为A，目标节点力B，在计算最优路径节点C时需要在考虑几何距离基础上使用计算公式：(A—C)2+fB—C)2在A*算法中通过对各个不同节点的计算，从而找出路径最短最优的节点，但这一算法具有一定的缺陷，很可能要将整个地图上的节点都计算完了才能得出结果，当游戏场景复杂且节点数量过多的话，会大大增加游戏设计制作中的寻路算法的费用。
为此，就要对A*算法进行优化改进，以便扩大应用范围，满足玩家的游戏需求。
1.2自动寻路算法的实现为了最快的找到游戏地图中的最优路径，需要将游戏场景进行网格划分，让每个网路成为大小相同的正方形，成为游戏中的导航网格，就可以选择一个节点起始位置，进行目标节点位置的广度搜索，在确定区域后在计算最佳路径。
0 引言路径搜索是一项在各个领域中广泛应用的重要技术，是计算机游戏尤其是在角色扮演类、战略类游戏的重要组成部分。
智能游戏中的路径搜索就是玩家根据地图场景中各类物体的分布信息，控制角色找到从起点到目标节点之间最佳路径的过程[1]。
除了基本的避障算法之外，目前该领域已经有许多路径搜索算法，有传统的启发式A*寻路算法，基于抽象图的HPA*、M-A*等寻路方法，考虑地图分布信息的CDHPA*分层路径搜索算法等[2]。
这些算法虽然各有不同的优缺点，但都是希望快速找出一条最优路径，使角色能够尽快到达目的地。
角色扮演游戏简称为RPG 游戏，一般就是玩家控制角色在虚拟空间中不断地自主探索，并在探索过程不断的提升[3]，场景一般都会比较大，而且会随着游戏剧情的展开而动态的变化，现有的寻路方法难以适应这些要求。
本文提出一种专门针对角色扮演游戏特点的寻路算法——分层避障寻路算法。
该算法使用分层处理提高搜索效率，A*算法选取最优路径，避障处理解决场景的动态变化问题，兼顾了大场景的快速寻路，同时也能够体现出角色的探索过程，保证了玩家的游戏乐趣。
1 典型路径搜索算法1.1 简单避障算法虚拟场景中的寻路，简单说就是向目标点靠近的过程。
如果没有障碍物，用基本的跟踪算法就可以实现。
在有障碍物的地图中，需只要使用一定的避障策略才能到达目的地。
具体的有试探法、轮廓跟踪法等[4]。
试探法的基本思路是当智能体与障碍物发生碰撞后，先退后左转或右转一定角度，然后向前移动一段距离，再根据目标位置调整朝向进行寻路。
或者随机的移动一段位置。
该方法虽然简单，但会使智能体显得比较笨拙。
相对真实和高效的寻路技术是轮廓跟踪，就是在智能体遇到障碍物一定距离时，就旋转移动方向使之绕着障碍物的轮廓进行移动[5]。
避障算法属于盲目的搜索，不能实现最优寻路，但是响应快，无论多么复杂的场景，多少对象的同时寻路，系统都会立刻响应，而且这种盲目性在游戏过程中显现出来的探索过程也正是RPG 游戏所需要的，适度的探索在一定程度上能够增加游戏的真实感。
A*寻路算法在游戏中的应用作者：刘娜王玉芳来源：《数字技术与应用》2012年第06期摘要：寻路是游戏开发中中非常重要的一个元素,如何高效的找到一条最短的路径是游戏AI设计的基础之一，本文比较了A*算法相对于普通的深度搜索及广度搜索在路径搜索上的优势，探讨了A*算法的原理及实现以及如何在游戏中使用A*算法实现路径探索。
关键词：游戏开发人工智能状态空间搜索 A*算法中图分类号：TP301 文献标识码：A 文章编号：1007-9416(2012)06-0135-01近年来，随着游戏产业的发展，越来越多的游戏开始采用人工智能技术提高游戏的可玩性。
在游戏中，玩家操控主要角色，而其他角色的行为逻辑由人工智能操纵。
大部分游戏在开发过程中都会遇到路径探索问题：即如何快速、准确地计算出游戏角色从地图中的A点到达B 点的一条路径，优秀的寻路算法一直是游戏开发者追求的目标，同时也是人工智能基础算法之一。
1、常见状态空间搜索算法当求解一个问题时，由于求解问题的过程中分枝有很多，使得求解的路径很多，就构成了一个图，这个图称之为状态空间，问题的求解就是在这个图中找到一条路径可以从开始到结果，这个过程就叫做状态空间搜索。
常见的状态空间搜索有深度优先和广度优先，深度优先即是先按照一定的顺序搜索完一个分枝再搜索另外一个分枝，广度优先即是从起点开始一层一层向下找，直到找到目标为止。
它们在状态空间规模不大时是一个好的选择，但是它们有一个很大的缺陷就是在状态空间中穷举，当状态空间很大时，要搜索的节点数就会增长很快，效率很低，这时就需要用到启发式搜索了。
即是在搜索时对下面将要搜索的每一个位置进行价值评估，这样就可以省去大部分无谓的搜索过程从而提高搜索效率。
2、A*搜索算法启发式搜索也有很多的算法，如局部择优搜索法、最好优先搜索法等，这些算法都使用了启发函数，区别在于选取最佳搜索节点时的策略不同。
局部择优搜索法，就是在搜索的过程中选取最佳节点后舍弃其他的节点一直搜索下去。
第7卷 第2期漯河职业技术学院学报V o.l 7N o 2 2008年3月Journa l o f Luohe V ocationa lT echno l ogy Co ll egeM ar 2008收稿日期:2008-01-09作者简介:王晓红(1969-),女,河南登封人,漯河职业技术学院讲师;刘 歌(1973-),女,河南漯河人,漯河职业技术学院讲师。
基于电脑游戏设计的人工智能A *算法王晓红,刘 歌(漯河职业技术学院计算机工程系,河南漯河462002)摘要:在电脑游戏设计中经常要用到人工智能算法。
人工智能A *算法是目前最快的一种计算最短路径的人工智能算法。
本文论述了A *算法的基本原理,并以二维地图的寻径为例对A *算法进行了实例分析。
关键词:人工智能;A *算法;评估函数;寻径函数中图分类号:TS952 83文献标识码:A 文章编号:1671-7864(2008)02-0051-02电脑游戏设计的人工智能A I 指用计算机来模拟人的思维和行动。
A I 使游戏中的角色,如歹徒、怪物还有警察等,都变得更加聪明,同时增加的隐藏任务和事件为游戏的可玩性和不确定性奠定了基础。
从1994年以来,A I 原理应用了人造基因、基因突变、培养、进化等理论,并创造了一个现实的和国际互联网上的A I 生命生存空间 生命的空间 。
生命的空间 包括一个可以让用户通过键盘输入文字信息的网页,这些文字作为创造不知名虚拟生命的基因密码,在虚拟空间里生成三维生命,开始与其他虚拟生命共存。
A I 的设计开发从理论走到现实,尤其是其核心算法在游戏中实现,经历了一个漫长的过程。
在1996年举行了世界上最著名的国际象棋人机大战,俄罗斯国际象棋世界冠军加里 卡斯帕罗夫与IB M 公司的计算机 深蓝 之间的对抗,最后战成4 2。
1997年,经过IB M 一年多的改进, 深蓝 在A I 方面有了长足的进步,被称为 更深的蓝 。
这一次卡斯帕罗夫在6局较量中败下阵来。
路径搜索算法在游戏中的应用及改进游戏开发领域中，路径搜索算法是一个非常重要的部分。
主要用于实现游戏中角色的移动、寻路、避障等功能。
在这篇文章中，我们将会介绍一些常见的路径搜索算法，并讨论如何对其进行改进，以适应不同类型的游戏。
一、常见的路径搜索算法1. Dijkstra算法Dijkstra算法最初是用于解决单源最短路径问题的。
但是在游戏中，我们通常使用它来找到角色移动的最短路径。
这个算法的思路非常简单，从起点出发，不断找到与起点距离最短的那个节点，并将其标记为已访问过。
然后再以这个节点为中心，继续寻找距离最短的节点，如此往复，直到找到目的地。
2. A*算法A*算法比Dijkstra算法更加高效，因为它可以利用启发式函数来指导搜索方向。
启发函数通常是基于目的地的距离和当前节点到目的地的估计距离进行计算的。
通过将距离和估计距离相加，找到当前节点与目的地之间最小的路径，这也就是A*算法优于其他算法的地方。
3. BFS算法BFS算法是一种基于层级的搜索算法。
它的思路是先访问起点，然后访问与起点相邻的节点，并将它们加入队列中。
接下来依次访问队列中的节点，并将其邻居节点加入队列中。
如此往复，直到访问到目的地。
二、路径搜索算法的改进在不同类型的游戏中，我们需要使用不同的路径搜索算法。
有些游戏中，需要处理大量角色的运动，这时候Dijkstra算法或者A*算法可能会比较慢。
而在一些动作游戏中，需要精确控制角色的运动，这时候就需要使用更加高效的算法。
1. 公平性算法在一些游戏中，我们需要处理大量角色的运动，这些角色也很容易相互干扰。
公平性算法就是为了解决这个问题而设计的。
它可以在保证所有角色都能达到目的地的前提下，让他们尽可能地避开其他角色。
2. 高效算法在一些动作游戏中，需要达到更高的运动速度。
这时候，Dijkstra算法或者A*算法可能会显得有些慢了。
所以，我们需要使用更加高效的算法。
一个思路是把搜索空间进行预处理，这样就可以非常快地找到任意两个位置之间的路径了。
一劳永逸的固定寻路平时我尽我所能，以避免可能被解释为一个在行业中的其他游戏或开发的批评说的事情。
但在这种情况下，我不得不做出一个异常的位。
我要谈谈我们与寻路面临的一些问题。
为了证明，这些问题仍然存在，我觉得有必要使这个视频... ...在幽默和轻松愉快的精神，它的目的是，希望在采取所有这些片段在上周录得最新，最最近修补的每场比赛的版本。
正如你可以看到，我们仍然是一个强大的寻路全线长的路要走... ...它甚至在一些万元的单位销售，AAA级质量职称的问题。
它不一定是一个普遍性的问题。
许多现代游戏有高品质的寻路，寻路经常在这里显示的一些游戏。
但仍有太多的游戏，寻路，游戏在20世纪90年代，以同样的方式。
（注：只是你看到大量的PC角色扮演游戏的唯一原因归结到便利，这些都是我当时安装的游戏，问题是不特定的任何类型或任何发挥想象力的平台。
有类似的问题，大量的游戏机游戏）。
据我所知，这些游戏大多使用寻路航点图。
我认为这几个寻路的问题，您在这个视频中看到，许多我们在整个行业面临的寻路问题的原因。
我相信航点图现在已经过时。
这篇文章解释了航点图方法的局限性，并勾画出了一个更好的方法五点的说法。
曾经有一段时间，这是有意义的，使用寻路航点。
早在20世纪80年代和90年代，我们的工作受到严重的技术限制，我们不得不削减了很多弯道。
但是我们现在一个多亿美元的产业。
我们的目标平台多内核和日益增加的大量的内存，我们可以做不起寻路正确。
有一个行业AI开发中说：“寻路是解决了。
”我们每一个寻路的问题，面临着现代游戏的好方法。
我们只是不经常使用它们。
我们没有理由不寻路，在每场比赛，每次。
打跳了详细的解释。
为什么航点对于寻路让我告诉你什么是一个典型的航点图看起来。
下面是一个在魔兽世界暴风城的小片：图1。
魔兽世界暴风城的一部分，下面是一个典型的航点图可能看起来在这方面想。
图2。
同一地区的一个航点图注释还有另一种方式做到这一点，它涉及使用凸多边形来描述AI角色可以旅行。
A星寻路算法介绍这篇blog是由iOS Tutorial Team的成员Johann Fradj发表的，他目前是一位全职的资深iOS开发工程师。
他是Hot Apps Factory的创始人，该公司开发了App Cooker。
学习A星寻路算法是如何工作的！你是否在做一款游戏的时候想创造一些怪兽或者游戏主角，让它们移动到特定的位置，避开墙壁和障碍物呢？如果是的话，请看这篇教程，我们会展示如何使用A星寻路算法来实现它！在网上已经有很多篇关于A星寻路算法的文章，但是大部分都是提供给已经了解基本原理的高级开发者的。
本篇教程将从最基本的原理讲起。
我们会一步步讲解A星寻路算法，幷配有很多图解和例子。
不管你使用的是什么编程语言或者操作平台，你会发现本篇教程很有帮助，因为它在非编程语言的层面上解释了算法的原理。
稍后，会有一篇教程，展示如何在Cocos2D iPhone 游戏中实现A星算法。
现在找下到达一杯咖啡因饮料和美味的零食的最短路径，开始吧！:]一只探路猫让我们想象一下，有一款游戏，游戏中一只猫想要找到获取骨头的路线。
“为什么会有一只猫想要骨头？！”你可能会这么想。
在本游戏中，这是一只狡猾的猫，他想捡起骨头给狗，以防止被咬死！:]现在想像一下下图中的猫想找到到达骨头的最短路径：不幸的是，猫不能直接从它当前的位置走到骨头的位置，因为有面墙挡住了去路，而且它在游戏中不是一只幽灵猫！游戏中的猫同样懒惰，它总是想找到最短路径，这样当他回家看望它的女朋友时不会太累:-)但是我们如何编写一个算法计算出猫要选择的那条路径呢？A星算法拯救了我们！简化搜索区域寻路的第一步是简化成容易控制的搜索区域。
怎么处理要根据游戏来决定了。
例如，我们可以将搜索区域划分成像素点，但是这样的划分粒度对于我们这款基于方块的游戏来说太高了（没必要）。
作为代替，我们使用方块（一个正方形）作为寻路算法的单元。
其他的形状类型也是可能的（比如三角形或者六边形），但是正方形是最简单并且最适合我们需求的。
基于改进A_Start算法的地图游戏寻径A_Start（A－SｔAｒ）算法是一种启发式搜索策略，是在静态地图中寻找最短路径的有效方法。
A_Start 算法的估价函数f(x)定义为从起始点到节点ｘ已付出的实际代价与节点ｘ到达目标点的接近程度估计值总和，是代价函数ｇ(x)与启发函数ｈ(x)的折中。
启发函数ｈ(x)的选取直接关系到能否找到最短路径（最优解）。
A_Start算法搜索思想如下：１）新建OPEN表和CLOSED表，初始均为空。
２）在OPEN表中添加起始节点S。
３）若OPEN表为空则失败退出，否则取最小f 值节点作为当前考察点ｘ。
４）将节点ｘ从OPEN表移至CLOSED表。
５）若节点ｘ为目标节点，则最优解找到成功退出，否则，扩展节点ｘ并生成后继节点N。
６）对节点ｘ所有后继节点N 进行考察：第一：对于后继节点N 有ｇ（N）＝ｇ(x)＋ｇ（ｘ，N）。
第二：创建从后继节点N 返回节点ｘ的指针。
第三：若节点N 为OPEN表的旧有节点，将旧有节点记为ｏ，将节点N 添加至ｘ的子节点表中。
如果f（N）＜f（ｏ），则f（ｏ）＝f（N）。
若节点N 不在OPEN表中，则判断它是否在CLOSED表中。
第四：若节点N 为CLOSED表的旧有节点，将旧有节点记为ｏ，将节点N 添加至ｘ的子节点表中。
如果f（N）＜f（ｏ），则f（ｏ）＝f（N）。
否则将它添加至OPEN表和ｘ的后继节点表。
第五：计算f 值，返回步骤３）继续判断。
A_Start搜索算法的游戏寻径策略高效，但仍有一些不足之处。
首先，在寻径过程中，随着节点的扩展，会对OPEN表进行反复遍历；在大规模游戏中，反复遍历会严重影响搜索效率。
其次，在寻路过程中，根据A_Start算法的搜索策略，会对具有相同f 值节点进行对比考察；但是只有靠近目标的节点才是最优节点，导致产生大量对非最优节点的考察，直接影响搜索效率。
A_Start算法改进1、混合数据结构A_Start寻路过程中，随着节点的扩展，会对OPEN表进行反复遍历，本研究针对反复遍历OPEN表问题，使用混合数据结构对OPEN表节点进行存储和标记。
基于改进A~*算法的地图游戏寻径研究
随着科技的进步,电子游戏经历了跨越式发展,游戏业的快速发展离不开游
戏开发技术的研究,基于A~*算法游戏寻路是游戏开发技术的一个热门研究课题。
A~*搜索算法虽然高效,但也有一些不足之处。
首先,在节点扩展过程中,会对OPEN表反复遍历,在大规模游戏中,严重影响搜索效率。
其次,在寻找最优节点时会对相同F值节点逐一考查比较,但是远离目标的节点不是最优节点,这样就产生了大量对无用节点的考察量。
本文的研究工作是基于A~*算法的地图游戏寻径所展开,利用改进的A~*算
法来提高地图游戏寻径的效率,并进行了仿真实验,验证了改进后的A~*算法的
有效性。
本文的主要工作:(1)针对A~*寻路算法对OPEN表反复遍历问题,本文使用混合数据结构优化OPEN表操作。
选用最小二叉堆存储OPEN表节点,可有效的提高取最小F值节点的效率。
同时使用索引数组来对OPEN表中节点进行标记,可使OPEN成员的隶属判断的时间复杂度减至O(1)。
(2)针对A~*寻路算法中产生大量无用节点的考察量问题,本文使用余弦函
数对启发函数进行改进,改进后的启发函数可有效减少无用节点的访问量。
(3)
本文为了验证改进后的A~*算法的有效性和可行性,通过仿真实验对改进前后的
A~*算法进行了对比实验分析,分别统计出改进前后算法寻路所花费的时间毫秒
数以及总的搜索节点数。
通过耗时和搜索节点总数这两个值的对比分析来评估改进后算法的有效性。
