GameRes游资网

 找回密码
 立即注册
返回列表
查看: 851|回复: 1

A* 寻路的八个变种

[复制链接]
发表于 2019-4-3 11:32:23 | 显示全部楼层 |阅读模式
游戏程序
平台类型:  
程序设计: 算法逻辑/智能AI 
编程语言:  
引擎/SDK:  
QQ截图20190403113107.png

变种1:束搜索(Beam Search)

在A*算法的住循环中,OPEN集存储可能需要搜索的节点,用来以查找路径。

束搜索是A*的变体,它限制了OPEN集的大小。

如果集合变得太大,则丢弃给出良好路径的最差机会的节点。

束搜索的一个缺点是你必须保持你的设置排序这样做,这限制了你选择的数据结构的种类。

变种2:迭代加深(Iterative Deepening)

迭代加深是一种在许多AI算法中使用的方法,以近似答案开始,然后使其更准确。

该名称来自游戏树搜索,您可以在其中查看前面的一些移动(例如,在国际象棋中)。

您可以通过向前看更多动作来尝试加深树木。

一旦你的答案没有改变或改善很多,你就会认为你有一个非常好的答案,当你试图让它再次变得更准确时它不会改善。

在IDA*中,“深度”是f值的截止值。

当f值太大时,甚至不考虑节点(即,它不会被添加到OPEN集)。

第一次通过你处理很少的节点。

每次后续传递,都会增加您访问的节点数。

如果您发现路径有所改善,那么您将继续增加截止值;否则,你可以停下来。

我个人认为在游戏地图上不太需要用IDA*查找路径。

因为ID算法倾向于增加计算时间,同时减少内存需求。

然而,在地图寻路中,“节点”非常小-它们只是坐标。

我没有看到节约存储这些节点有什么巨大优势。

变种3:动态加权(Dynamic Weighting)

通过动态加权,您可以假设——

在搜索开始时,快速到达目的地所在区域更重要;

在搜索结束时,得到到达目标的最佳路径更重要。

有一个与启发式相关的权重(w>=1)。

随着你越来越接近目标,你减轻了权重;这降低了启发式的重要性,并增加了路径实际成本的相对重要性。

变种4:带宽搜索(Bandwidth Search)

有一些人可能觉得有用的带宽搜索有两个属性。

这种变化假设h是高估的,但它并没有高估超过一些数e。

如果您的搜索就是这种情况,那么您获得的路径的成本不会超过最佳路径的成本超过e。

再次,您的启发式越好,您的解决方案就越好。

您获得的另一个属性是,如果您可以删除OPEN集中的某些节点。

每当h+d大于路径的真实成本(对于某些d),您可以丢弃任何f值至少比OPEN中最佳节点的f值高e+d的节点。

这是一个奇怪的属性。

你有一个很好的f值“带宽”;这个频段以外的所有东西都可以丢弃,因为可以保证它不会走在最佳路径上。

奇怪的是,您可以对这两个属性使用不同的启发式方法,但事情仍然有效。

您可以使用一个启发式方法来保证您的路径不是太糟糕,另一个用于确定OPEN集中的内容。

注意:

带宽搜索看起来可能有用,但在游戏行业很少使用到。

搜索Google以获得更多信息,尤其是相关论文。

变种5:双向搜索(Bidirectional Search)

您可以不从开始到结束搜索,而是并行开始两次搜索,一次从头到尾,一次从完成到开始。

当他们见面时,你应该有一条好路。

在某些情况下,这是一个好主意。

双向搜索背后的想法是搜索结果在地图上扇出的“树”。

一棵大树比两棵小树要糟糕得多,所以最好有两棵小树。

从面对面的变化将两个搜索链接在一起。

不是选择最佳前向搜索节点【g(start,x)+h(x,goal)】或最佳后向搜索节点【g(y,goal)+h(start,y)】

该算法选择具有最佳【g(start,x)+h(x,y)+g(y,goal)】的节点对。

重定向方法(retargeting approach)放弃了向前和向后方向的同时搜索。

相反,它会在短时间内执行前向搜索,选择最佳前向候选者N;

然后在终点执行后向搜索,搜索的目标不是起点,而是最佳前向候选者N。

过了一会儿,它选择了一个最好的后向候选人M,并执行从N到M的前向搜索。

这个过程一直持续循环,直到两个候选人是同一个点。

Holte,Felner,Sharon,Sturtevant在2016年的论文《具有近似最优节点扩展的前端双向启发式搜索》是最近的结果,具有接近最优的A*双向变体。

Pijls和Post在2009年的论文《另一种用于最短路径的双向算法》提出了一种比平衡双向搜索运行得更快的不平衡双向A*。

变种6:动态A*(Dynamic A*)和终身规划A*(Lifelong Planning A*)

A*的变体允许在计算初始路径之后改变世界。

D*适用于没有完整信息的情况。

如果你没有所有的信息,A*会犯错误;D*的贡献在于它可以在不花费太多时间的情况下纠正这些错误。

LPA*旨在用于成本变化时使用。

使用A*,路径可能会因地图的更改而失效;LPA*可以重复使用先前A*的计算来生成新路径。

但是,D*和LPA*都需要很大的空间——需要保存在最佳路径周围的很多节点的内部信息(OPEN/CLOSED集,路径树,g值)

然后当地图改变时,D*或LPA*会告诉您是否需要调整路径以考虑地图更改。

对于具有大量移动单位的游戏,您通常不希望保留所有这些信息(因为太大),因此D*和LPA*不适用。

它们是专为机器人设计的,如果只有一个机器人——您不需要将内存重用于其他机器人的路径。

如果您的游戏只有一个或少数单位,您可能需要试试D*或LPA*。

LPA*概述

LPA*小程序

变种7:跳点搜索(Jump Point Search)

许多加速A*的技术实际上都是关于减少节点数量。

在具有统一成本的方形网格中,一次一个地查看所有单独的网格空间是相当浪费的。

一种方法是构建关键点(例如角点)的图形并将其用于寻路。

但是,如果您不希望预先计算航点图,那就可以了解一下跳转点搜索,这是A*的变体,可以在方格网格上向前跳跃。

当考虑当前节点的子节点可能包含在OPEN集中时,跳转点搜索会向前跳到从当前节点可见的远端节点。

每个步骤都更昂贵,但它们更少,减少了OPEN集中的节点数量。

有关详细信息,请参阅此博客。

此文章提供了一个很好的可视化程序用来解释。

另请参阅矩形对称缩减,它可以分析地图并将跳转嵌入到图形本身中。

这两种技术都是为方形网格开发的。

这个网站是为六边形网格扩展的算法。

变种8:Theta*

网格用于寻路,是因为地图是在网格上制作的,而不是因为我们实际上想要在网格上移动。

如果给出关键点(例如角点)而不是网格的图形,A*将运行得更快并产生更好的路径。

但是,如果您不想预先计算角点图形,则可以使用在方形网格上运行的A*变体Theta*来查找不严格遵循网格的路径。

在构建父指针时,如果该节点与祖先节点有一条视线,互相可见,那么Theta*将该节点直接指向祖先节点,并跳过他俩中间的节点。

与路径平滑不同,路径平滑在A*找到路径之后拉直路径;而Theta*可以在A*过程中分析这些路径的,是A*的一部分。

这可以得到比将网格路径后处理成任意角度路径更短的路径。

这篇文章是对该算法的合理介绍;这里是Lazy Theta*。

Theta*的想法很可能也适用于导航网格。

另请参阅Block A*,它声称通过使用分层方法比Theta*快得多。

作者:howeXu_吼徐
博客地址:https://www.cnblogs.com/xuuold/p/10366834.html

Advertisement
发表于 2019-4-3 14:49:14 | 显示全部楼层
浓浓的翻译味儿,没有原文链接的吗?
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|作品发布|文章投稿|广告合作|关于本站|GameRes游资网 ( 闽ICP备05005107-1 )

GMT+8, 2019-8-23 18:16

快速回复 返回顶部 返回列表