关于寻路算法的一些思考(9):寻路者的移动成本

本系列:


寻路者的移动成本

当使用寻路算法的时候,你可能想把地图空间当做一种不单是用通畅或阻碍来表达的东西。通常地图空间会有更多的已知信息,比如通过那片区域的移动难度。比如,沼泽和高山可能比草地和沙漠更难通过。使用算法,比如A*,你可以把给信息编码代入成本函数中。下面列出了一些计算移动成本的想法,也许会派上用场。

海拔

高海拔(比如高山)比低海拔有更高的移动成本。当使用成本函数计算的时候,只要可能移动单元会试图一直停留在低洼的地方。例如,如果你的起始点和终点都在高地,移动单元可能会先下山,移动一段时间后再次登山。

爬山移动

相对于高海拔有一个高的成本,爬山成本也很高。这就避免了上面描述的奇怪状况。使用这种成本函数,移动单元就会尽量避免爬山寻路。面对同样的情况,移动单元也会避免寻路时最后还要爬山;在整个移动过程中,单元能始终保持在一个高的海拔区间。使用这种成本函数有益于士兵(soldiers)这样的下山容易上山难的单元。

上下山移动

一些单元,比如坦克(tanks),上下山都很困难。你可以设置一个比较高的成本下山,然后一个更高的成本上山。这个单元就会尽力避免改变移动时的海拔。

地形

不同的地形,可以设置不同的移动成本。

森林、高山和山丘

可以使用不同的地形类型来代替使用海拔的概念。比如在游戏《文明》(civilization)中,每个地形都有一个和它相关的移动成本。这种移动成本表可以适用于所有的单元,或者每一个单元类型都有匹配它的不同的移动成本。比如solider在森林中移动可能没有任何困难,但是tanks在森林中移动就很艰难。改变地形的时候设置移动成本是个很好的办法,从草地到高山会比从山丘到高山成本高,从山丘到高山移动又比高山之间移动成本高。

道路

在很多游戏里,道路的原始目的就是让移动变得可能或者更简单。在选择好移动成本函数后,可以加一条道路来修正它。一个可能的办法就是用成本除一个常数(比如2);另外的办法是设置一个表示沿着道路移动的成本常量。

我强烈的建议不要设道路移动成本为零。这会给寻路算法比如A*带来麻烦,因为它可能会算出这样的一种路径,即从一点到另一点间沿着一条弯曲的道路行进,其实没有指向任何目的地。这样算法不得不搜索一个很大的区域,确保没有这样的路存在。注意在Civilization的游戏中,铁路移动成本是零,但是当使用”auto-goto”函数的时候,铁路的移动成本就不是零了。这就是游戏使用了寻路算法的证据。

墙壁或其它障碍

无需既检查移动成本又要检查寻路算法里的路障,用移动成本一个计算就可以了。只要给你的路障设置一个非常高的移动成本即可。 (在A*算法里)当展开节点的时候,检查成本是否太高;如果是的话,就放弃这个节点吧。

有坡度的地形

你也许想在任何山丘中的移动设置较高的成本,来代替使用上山和下山。这样做,需要计算全部地势的斜度(通过观察行进路径的当前位置和它相连部分的最大高度差),使用这个来作为移动的成本。地势陡峭的陆地成本高,地势比较平缓的成本低。这种方法和上下山移动方法计算成本不同,因为它关注的是陡峭的地势,而之前的方法关注的是在一个陡峭的方向上移动的单元。特别是,如果你正在一个山丘上,而且可以向左或向右移动而不用向上或向下,那么上下山方法会认为这种情况成本低,而这个方法会认为成本高(因为地形本身陡峭,即便不用上下山的移动)。

根据地形陡峭判断成本的方法可能对于单元的移动来说不是很合理,但是你可以使用寻路算法不只是寻找单元的路径。我会使用它来寻找道路,管道,桥梁等等。如果你想在平地上建设这些项目,寻找一条道路或者管道的路线时,你可以考虑这种判断地势坡度的方法。参考这部分的应用可以挖掘出更多的想法。

敌对和友好单元

再设置一个修正器可以帮你避免敌人的单元。使用 influence 地图,你可以监视附近有敌人或者友好单元的区域、或最近有士兵被杀的区域、或最近刚被探索过的区域、或是靠近一条逃跑路线的区域、抑或是最近穿越过区域(《帝国时代2》里在 influence 寻路中使用了 influence 地图)。一个influence地图可能对友好单元有积极的作用,对敌人单元有消极的作用。无论何时你在一个敌对的领域里,通过增加移动成本,你可以改变你的单元离敌人远一点。

更复杂的是(可能在influence地图下是不行的)参考可见度。对敌对单元来说你的单元是否可见?换句话说,你的单元是否可遭受攻击?你的敌对单元有可能向你开火么?

设置信号标(beacon)

如果你的地图是设计出来的不是自动生成的,你可以添加额外的信息进去。比如,旧的贸易路线经常会经过一些变成贸易城镇的特定地点。这些地方就叫beacon,即优质路线上的已知地点。与beacon的距离值可以加入移动成本中,这种方法是根据对beacon的偏好影响寻路结果的。

灯塔、城市、山路和桥梁等都是beacon比较好的选择。

燃料消耗

注:为了保持状态空间比较小,你需要将燃料的价值四舍五入成一个近似的测量单元。不幸的是,这会将让搜索变得效率低下。

不但需要观察单元去某些地方所用的时间,你也要考虑它花费掉的燃料。当单元的燃料级别比较低的时候,燃料消耗可能会被赋予更大的权重。

就像上面描述的,为了跟踪地图上能源的耗费量,你需要使用状态空间。每个状态可能是成对的描述:<坐标,燃料>。然而,状态空间可能会变得非常大,所以不用普通的A*算法,寻找其他替代方法也是值得考虑的。

我们的另一个选择是加入有界成本的A*算法(A* with Bounded Costs (ABC))使用 ABC 算法,你可以给成本(比如“燃料”)设置一个界限(比如”20加仑”)。

1 4 收藏 1 评论

关于作者:土豆粉ss

兴趣:算法,人工智能,机器学习 个人主页 · 我的文章 · 13 ·   

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部