文档章节

关于寻路算法的一些思考(4):A* 算法的变体

oschina_00
 oschina_00
发布于 2017/02/20 10:47
字数 2376
阅读 50
收藏 0

定向搜索

 

在A*算法的循环中,OPEN集合用来保存所有用于寻找路径的被搜索节点。定向搜索是在A*算法基础上,通过对OPEN集合大小设置约束条件而得到的变体算法。当集合太大的时候,最不可能出现在最优路径上的节点将会被剔除。这样做会带来一个缺点:由于必须得保持这样的筛选,所以可选择的数据结构类型会受到限制。

 

迭代深化(Iterative deepening)

 

迭代深化是一种很多AI算法采用的方法,开始的时候给一个估计值,然后通过迭代使它越来越精确。这个名字来源于游戏树搜索中对接下来几次操作的提前预判(例如,在象棋游戏中)。你可以通过向前预判更多的操作来深化游戏树。一旦当你的结果不发生变化或提高很多,就可以认为你已经得到了一个非常好的结果,即使让它更精确,结果也不会再改善。在迭代深化A*(IDA*)算法中,“深度”是 f 值当前的一个截断值。当 f 值太大的时候,节点不会被考虑(也就是说,不会被加入到OPEN集中)。第一次循环时,只需要处理非常少的节点。随后的每次循环,都会增加访问的节点数。如果发现路径得到优化,就继续增加当前的截断值,否则结束。更多细节,参见链接。

 

我个人并不看好IDA*算法在游戏地图寻路中的应用。迭代深化的算法往往增加了计算时间,同时降低了内存需求。然而,在地图寻路的场景中,节点仅仅包含坐标信息,所需要的内存非常小。所以减少这部分内存开销并不会带来什么优势。

 

动态加权

 

在动态加权算法中,你假定在搜索开始时快速达到(任意)一个位置更为重要,在搜索结束时到达目标位置更为重要。

 

f(p) = g(p) + w(p) * h(p)

 

有一个权值(w >=  1 )和该启发式关联。当不断接近目标位置的时候,权重值也不断降低。这样降低了启发式函数的重要性,并增加了路径实际代价的相对重要性。

 

带宽搜索

 

带宽搜索有两个被认为非常有用的特性。这个算法变体假设 h 是一个估计过高的值,但它的估计误差不会超过 e。那么在这样的条件下,搜索到的路径代价与最优路径代价的误差不会超过 e。这里需要再一次强调,启发值设置得越好,那么得到的结果也将越好。

 

另外一个特性是用来判断你是否可以删掉OPEN集合中的某些节点。只要 h+d 大于路径真实代价(对于一些 d),那么你可以丢掉任意满足其 f 值比OPEN集合中最优节点 f 值至少大 e+d 的节点。这是一个很奇异的特性。你相当于得到了一个 f 值的带宽;所有在这个带宽意外的节点都可以被丢弃掉,因为他们被保证一定不会出现在最优路径中。

 

有意思地是,对于这两种特性分别使用不同的启发值,仍然可以计算得到结果。你可以使用一个启发值来保证路径代价不会太大,另外一个启发值来决定丢弃掉OPEN集中的哪些节点。

 

双向搜索

 

与从头到尾的搜索不同,你也可以并行地同时进行两个搜索,一个从开始到结束,一个从结束到开始。当它们相遇的时候,你就会得到一个最优路径。

 

这个想法在一些情况下非常有用。双向搜索的主要思想是:搜索结果会形成一个在地图上呈扇形展开的树。而一个大的树远不如两个小的树,所以使用两个小的搜索树更好。

 

面对面的变体将两个搜索结果链接到一起。该算法选择满足最佳 g(start,x) + h(x,y) + g(y,goal) 的一对节点,而不是选择最佳前向搜索节点 g(start,x) + h(x,goal) 或者最佳后向搜索节点 g(y,goal) + h(start,y)。

 

重定向算法放弃同时前向和后向的搜索方法。该算法首先进行一个短暂的前向搜索,并选出一个最佳的前向候选节点。接着进行后向搜索。此时,后向搜索不是朝向开始节点,而是朝向刚刚得到的前向候选节点。后向搜索也会选出一个最佳后向搜索节点。然后下一步,再运行前向搜索,从当前的前向候选节点到后向候选节点。这个过程将会不断重复,直到两个后选节点重合。

 

动态A*与终身规划A*

 

有一些A*的变体算法允许初始路径计算之后地图发生改变。动态A*可以用于在不知道全部地图信息的情况进行寻路。如果没有全部信息,那么A*算法的计算可能会出现错误,动态A*的优势在于可以快速改正那些错误而不会花费很多时间。终身规划A*算法可以用于代价发生改变的情况。当地图发生改变的时候,A*计算得到路径可能会失效;终身规划A*可以重复利用以前的A*计算来产生新的路径。

 

然而,动态A*与终身规划A*都要求大量的空间——运行A*算法时需要保持它的内部信息(OPEN/CLOSED集合,路径树,g值)。当路径发生改变的时候,动态A*或终身规划A*算法会告诉你是否需要根据地图的变化调整你的路径。

 

对于一个有大量运动单元的游戏,通常不会想要保存所有的信息,所以动态D*和终身规划A*可能不适用。这两种算法主要为机器人而设计。当只有一个机器人的时候,你不需要为了其他机器人的路径来重复使用内存。如果你的游戏只有一个或比较少的单元,你能会想要研究一下动态A*或者终身规划A*算法。

 

  • D*算法概述

  • D*文章1

  • D*文章2

  • 终身规划算法概述

  • 终身规划算法论文(PDF)

  • 终身规划 A*算法 applet

跳跃点搜索

 

提高A*算法计算速度的大多数技术都是采取减少节点数量的策略。在统一代价的方格网络中,每次单独搜索一个独立格空间是非常浪费的。一个解决办法是对其中关键节点(例如拐角)建立一个用来进行寻路的图。但是,没有人愿意预先计算出一个路标图,那就来看看可以在网格图上向前跳跃的A*变体算法,跳跃点搜索。 考虑到当前节点的孩子节点有可能会出现在OPEN集合中,跳跃点搜索直接跳跃到从当前点可看到的遥远的节点。随着OPEN集合中节点的不断减少,每一步的代价都会越来越高虽然都很高,但是步数也会越来越少。相关细节,可以参考链接;这篇博客中有很好的可视化解释;还有,reddit上对优缺点的讨论可点击这个链接。

 

此外,在矩形对称消减中,有对地图进行分析和图中嵌入跳跃。这两种技术都是应用于方格网络图中的。

 

Theta*

 

有时网格会用来寻路是因为地图是用网格来生成,而不是因为真的要在网格上移动。如果给定一个关键点的图(例如拐角)而不是网格的话,A*算法可以运行得更快并得到更优的路径。但是,如果你不想预先计算那些图的拐角,你可以通过A*算法的变体Theta*在方格网络上进行寻路而不必严格遵循那些方格。当构建父亲指针的时候,如果有一个祖先与该节点间存在边,那么Theta*算法会直接将该指针指向该祖先而忽略所有的中间节点。不像路径光滑那样将A*找到的路径变为直线,Theta*可以把那些路径的分析作为A*算法过程的一部分。这样的做法可以比后处理方格路径使之成为任意倾角的路径的方式,可以得到更短的路径。这篇文章的是对算法的一个比较合理的介绍,另外可参考懒惰Theta*。

Theta*的思路也可能被应用于导航网格。

 

英文:theory.stanford.edu

译者:伯乐在线 - 乐徒

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

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

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

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

CatherinePlans
2017/11/05
0
0
A星寻路算法入门(Unity实现)

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

青空哲也
03/14
0
0
游戏开发与程序设计知识总结05——游戏前端开发

更新日志 每此对思维导图有改动或者在github中有了对应的实现,则增加一条更新日志。 前言 这是游戏开发与程序设计知识总结系列文章的第五篇游戏前端开发。本系列文章的初衷源于我正在找工作...

kashiwa
2017/09/07
0
0
游戏中的人工智能之流场寻路

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

RonTang
2016/04/20
0
0
[Qt] 迷宫随机生成和寻路算法 - Qt实现的迷宫小游戏

首先贴出下载链接: 1. 完整Qt源码:http://download.csdn.net/detail/mahabharata_/9824044 2. 发布的可执行程序:http://download.csdn.net/detail/mahabharata_/9824066 程序截图: 1. 动......

Mahabharata_
2017/04/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

任务调度-第三方库Quartz实现分布式任务管理与调度

1. 为什么要用第三方库Quartz来实现分布式任务管理和调度? 首先管理的目的是通过集群多节点的管理提供容错,调度的目的是保证同一任务只会被完整执行一次;之前分享过的任务调度-单体应用定...

秋日芒草
11分钟前
0
0
Mysql Explain Type

前言 当我们执行sql,一般都会用Explain来查看sql的效率如何。今天在看sql执行效率的时候,忘记了其中Type的意思,现在在此记录一下。 效率 这里的type指的是访问类型,各个效率高低如下: ...

无敌小杰杰
20分钟前
0
0
外部浏览器网页复制公众号无法自动唤起微信并关注怎么办?

现在有很多用户在外部浏览器网页复制公众号时无法自动唤起微信并关注,这是因为第三方浏览器打开微信的接口,微信只给部分合作平台开放了接口权限,任何第三方想调用只能是通过一些技术手段来...

qjniop
24分钟前
0
0
建造者模式

建造者模式(Builder Pattern) 也叫生成器模式,其定义如下: Separate the construction of a complex object from its representation so that the same construction process can create d......

无知的小狼
29分钟前
0
0
距离计算方法

1、欧式距离(欧几里得距离) 欧式距离是最易理解的距离定义,即各坐标点的坐标之差的平方和相加,然后开根号。 二维平面上点 与点 之间的距离公式是: n维空间上点 和点 之间的距离公式是:...

城北徐公美
31分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部