文档章节

关于寻路算法的一些思考(5):处理移动中的障碍物

oschina_00
 oschina_00
发布于 2017/02/21 10:16
字数 2026
阅读 8
收藏 0

一个寻路算法会计算出一条绕过静止障碍物的路径,但如果障碍物会移动呢?当一个单位移动到达某特定点时,原来的障碍物可能不在那点了,或者在那点上出现了新的障碍物。如果路线可以绕过典型的障碍物,那么只要使用单独的避障算法来配合你的寻路算法。寻路算法会寻找到期望的路径,并且在沿着路径的同时绕过障碍物。但是如果障碍物可以移动,进而导致路径不停地发生显著改变,就应考虑使用寻路算法来避障。

 

重新计算路径

 

我们希望游戏世界随着时间改变。一条一段时间之前发现的路径,可能不再是现在的最优路径。用新的信息更新旧路径是值得的。下面列出的是一些用来判断决定是否需要重新计算路径的标准:

 

  • 每N步一次:这样保证用来计算路径的信息不会旧于N步。

  • 当额外的CPU时间可用时:这样可以实现路径质量的动态调整。即使使用了更多的游戏单位,或者是在一台较慢的电脑上运行游戏,每个游戏单位的CPU使用率都可以降低。

  • 当游戏单位转弯或者通过一个关键路径点的时候。

  • 当游戏单位附近的世界发生改变的时候。

重新计算路线的主要缺点在于有很多路径信息被丢弃了。例如,如果路径长100步,并且每十步进行一次重新计算,那么路径的总步数是100+90+80+70+60+50+40+30+20+10 = 550。对于一个长M步的路径,总共大概进行了M^2步计算。因此,如果你想要得到很多条长路径,重新计算路线并不是一个好主意。重复使用路线信息,而非丢弃,这样会是更好的办法。

 

路径剪接

 

当一条路径需要被重新计算时,意味着世界正在改变。给定一个变化中的世界,地图上的邻近部分比远处的部分更好了解。我们可以遵循一个局部修正策略:找到附近的一条好路径,并且假定较远的路径直到我们靠近它了才需要重新计算。我们可以仅仅重新计算路径的前M步,而不是整条路径:

 

  1. 设p[1]..p[N] 是路径剩余部分(N步)

  2. 计算一条从p[1]到p[M]新路径

  3. 剪接新路径到旧路径中,通过移除p[1]..p[M]然后插入新路径到这些空位置上。

 

因为p[1]和p[M]相距不到M步,所以新路线不太可能长。不幸的是,像新路径又长又不是非常好的情况,也有可能发生。上图展示了这样一个情况。原始的红色路径是1-2-3-4,棕色区域是障碍。如果我们到达2然后发现从2到3的路径被阻挡了,路径剪接会用绿色的路径2-5-3来替换2-3,导致这个单位循着路径1-2-5-3-4移动。我们可以看到这并不是一个好的路径,蓝色路径1-2-5-4是更好的选择。

 

不好的路径经常可以通过计算新路径的长度来判断。如果它明显比M长,它就可能是不好的路径。一个简单的解决方法,给寻路算法添加一个上限(最大路径长度)。如果找不到一条短的路径,这个算法返回一个错误代码,在这种情况下,使用重新计算路线而不是路线剪接来得到一条像1-2-5-4这样的路径。

 

对于没有涉及到这类情况的例子,对于一条N步的路径,路线剪接会计算2N到3N路径步数,取决于一条新路径进行剪接插入的频繁程度。这是一个相对低的代价,使得算法能对世界的改变作出反应。意想不到的是,这个花费的代价大小取决于M,也就是进行剪接的路径步数。M控制一个反馈和路径质量的平衡,而不是CPU时间的影响。如果M的值较大,单位的移动将不会快速地对地图的改变作出反馈。如果M太小,被剪接的路径可能太短,以至于不能得到可以绕过障碍的替换路径:更不优的路径(例如1-2-5-3-4)可能会被找到,尝试M的不同取值和不同的剪接标准(例如每隔3/4 M步),来看看怎样做最适合你的地图。

 

路径剪接比重新计算路径明显地快了许多,但它对于路径的重大改变并不能很好地应对。不过很多这种情况可以容易地发现,并直接使用重新计算路径来代替路径剪接。它同样有几个可以调整的变量,比如M和进行新路径的寻找的时间,所以它可以被调整为适合不同的情况(即使是在运行的时候)。但是路径剪接并不能处理游戏单位需要确定位置进而来互相穿过的情况。

 

监视地图的改变

 

选择重新计算全部或部分路径在特定的时间间隔,是对地图的改变来触发重新计算。地图可以分成不同的区域,每个游戏单位可以在特定的区域表现出兴趣。(所有包括部分路径的区域都可能是感兴趣的,或者仅仅是邻近的包含部分路径的区域)无论障碍进入或离开某个区域,那个区域就标记为已经改变,然后所有对那个区域感兴趣的游戏单位都会被通知,所以路径可以在考虑障碍发生变化这一前提下被重新计算。

 

这一技术有很多可能的变化。例如,我们可以仅仅在特定的时间间隔通知游戏单位而不是立即通知。并且多次改变可以被组合成一次通知,所以不再需要过多的进行重新计算路径。另一个变化是让游戏单位来查询地区的状态,而不是让地区来通知游戏单位。

 

监视地图的改变,避免了游戏单位在障碍物没有发生变化的时候进行重新计算,因此当你有很大地区不会经常发生改变的时候,可以考虑使用这种方法。

 

预测障碍物移动

 

如果障碍物的移动可以被预测,那就可以在进行寻路时把未来的障碍物位置纳入考虑。像A*这类算法有一个代价函数,来决定通过地图上某点的困难程度。A*可以被修改成实时更新到达一点所需要的时间(由当前的路径长度决定),这个时间也可以被传入代价函数中。代价函数就可以把时间纳入考虑,然后就可以使用在那个时刻的障碍物预测位置,来决定那个地图位置是否无法通过。但是这个修改并不完美,因为它不会考虑在某个点等待障碍物离开路径的可能性,另外A*并不是设计用来区分相同路线上的路径,而是时间不同的点。

 

英文:theory.stanford.edu

译者:伯乐在线 - xxmen

链接:http://blog.jobbole.com/83499/

本文转载自:http://blog.jobbole.com/83499/

oschina_00
粉丝 5
博文 101
码字总数 0
作品 0
廊坊
私信 提问
【文集】寻路算法汇总

寻路是游戏开发中非常重要的一部分,能够让人物的操作更符合玩家想要的行为 先来一个在Unity3D中实现自动寻路的文章 Unity3D 自动寻路 在Unity3D中实现以及调试A*寻路算法 Unity3D A* 寻路...

CatherinePlans
2017/11/05
0
0
游戏中的人工智能之流场寻路

流场简介 流场,一般为网格图,网格中的每一个节点包含一个向量,该向量是物体在该位置时期望的速度。 流场寻路 利用流场的速度信息指导大量物体同时进行寻路。换句话说,如何生成可以寻路的...

RonTang
2016/04/20
0
0
AS3 做webGame 地图寻路实例 .

总结目的 在地图中,通过鼠标或者由程序自动运行,让一个人物自动从地图的一点走到另一点。需要计算两点之间的最优路线,要实现这样的寻路算法。最常规和最简单的方法,使用A算法。本篇总结不...

小木头的冬天
2016/07/27
23
0
A星寻路算法入门(Unity实现)

最近简单学习了一下A星寻路算法,来记录一下。 还是个萌新,如果写的不好,请谅解。 Unity版本:2018.3.2f1 A星寻路算法是什么 游戏开发中往往有这样的需求,让玩家控制的角色自动寻路到目标...

青空哲也
03/14
0
0
unity-AI设计理念和编程思想(三)

前两个模块大致讲了讲AI角色的感知和自主决策,决策之后呢?当然就要开始行动了。比如AI角色发现一个目标,并决定去攻击它,但它与目标之间可能还有一段距离,AI角色需要先到达目标点,这就需...

scopperil
2018/05/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

用 Sphinx 搭建博客时,如何自定义插件?

之前有不少同学看过我的个人博客(http://python-online.cn),也根据我写的教程完成了自己个人站点的搭建。 点此:使用 Python 30分钟 教你快速搭建一个博客 为防有的同学不清楚 Sphinx ,这...

王炳明
昨天
2
0
黑客之道-40本书籍助你快速入门黑客技术免费下载

场景 黑客是一个中文词语,皆源自英文hacker,随着灰鸽子的出现,灰鸽子成为了很多假借黑客名义控制他人电脑的黑客技术,于是出现了“骇客”与"黑客"分家。2012年电影频道节目中心出品的电影...

badaoliumang
昨天
12
0
很遗憾,没有一篇文章能讲清楚线程的生命周期!

(手机横屏看源码更方便) 注:java源码分析部分如无特殊说明均基于 java8 版本。 简介 大家都知道线程是有生命周期,但是彤哥可以认真负责地告诉你网上几乎没有一篇文章讲得是完全正确的。 ...

彤哥读源码
昨天
13
0
jquery--DOM操作基础

本文转载于:专业的前端网站➭jquery--DOM操作基础 元素的访问 元素属性操作 获取:attr(name);$("#my").attr("src"); 设置:attr(name,value);$("#myImg").attr("src","images/1.jpg"); ......

前端老手
昨天
6
0
Django的ChoiceField和MultipleChoiceField错误提示,选择一个有效的选项

在表单验证时提示错误:选择一个有效的选项 例如有这样一个表单: class ProductForm(Form): category = fields.MultipleChoiceField( widget=widgets.SelectMultiple(), ...

编程老陆
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部