实时执行David Silver的合作path查找

我目前正在使用基于网格运动的2D游戏(全部八个方向)实施David Silver的Cooperative Pathfindingalgorithm

我遇到麻烦的问题是实时预订表。 我已经在自己的testing平台上完全实现了这个algorithm。 然而,我的实现是基于回合的,每个人都在以相同的速度移动。

我试图将这个小组寻find的游戏与具有不同速度的单元进行实时移动。


我已经编制了一些我需要考虑的因素,有些可以帮助我实现这一点:

  1. 敌人不寻找玩家的角色
  2. 但是,有些敌方单位会stream连忘返
  3. 敌人将根据敌人types有不同的移动速度
  4. 玩家通过点击目的地来移动头像(这会开始散步)
  5. 玩家可以通过双击一个目的地开始运行(这可以发生在网格节点之间)
  6. 玩家有跟随化身的盟友
  7. 如果距离太远,盟军将跟随虚拟形象,如果距离足够近,就会再次步行(这也可能发生在网格节点之间)
  8. 速度并不是完美的倍数

考虑到这些,我目前的部分解决scheme包括以下内容:

  • 由于考虑1和2,敌人将共享保留表,因为我可以让他们在相同的时间间隔内移动,所以他们的时间将会匹配
  • 由于考虑3和8,敌人的预定表将因运动速度而有所不同。 我想这样做,因为我不知道如何使用一个预订表,如果他们的速度是不完美的倍数彼此。
  • 由于4,5,7和8的速度变化考虑,玩家和盟友的path在开始行走或开始行驶时将被重新计算,因为这会影响path协调。
  • 由于path可以在玩家头像上重新计算,因此我需要为玩家准备两张预留表格(一个用于散步,一个用于运行)。 我也可能需要有两张盟友分享的预约表(一个是散步,一个是运行)。
  • 由于可以在节点之间重新计算path的事实,我相信我将不得不限制速度的变化,只有当一个单元直接在一个节点上,而不是在当前工作时能够改变节点之间的速度。 否则,我相信我将不得不计算到达下一个节点所需的时间,然后以某种方式跟踪预订表中的时间。

最后,这里是我想知道的事情:

  • 如果协调单位这么难,我一定不能完全理解预定表。 如何在空间 – 时间映射中定义一个节点的时间,而不是从一个节点到另一个节点需要多长时间?
  • 在时空映射中定义节点的时间时,对角线运动是否会成为问题?
  • 是否有一个更简单的方法来处理这个短的实现一个不同的组path搜寻algorithm?
  • 如果还有另外一种你推荐的寻路algorithm,那么我就是所有人,但在这个发展阶段,最有可能的是没有时间去实现新的东西,除非编码和整合到游戏中的时间要less于干扰已经编码的algorithm进入游戏。

随意建议稍微改变敌人,玩家和盟友如何移动的方法,如果这样做会使执行起来更容易。 我感谢您提供的任何帮助。 谢谢你的时间!

在阅读链接的文档之前,不熟悉这种方法,似乎使用多个预定表会产生混淆。 这将不具备预订表的观点。 你可以防止相同types单位之间的碰撞,但是试图穿越同一空间的快速单位和慢速单位仍然可能在碰撞反应舞蹈中结束,因为他们试图相互移动。 此外,链接的pdf格式的第11页指出,他们预计将共享预订表的具体问题。

如果你的devise要求一个友方单位能够经过一组敌方单位,盟友和敌人也将共享一个预定表。 如果你特别希望他们在碰撞时碰碰舞,也许你可以为每个小组使用不同的表格,但是我仍然认为最好把他们所有的path放在同一张保留表上,并依靠行为逻辑来确定他们是否停止互动,或继续移动。 我的意思是说,你可以通过有意识地寻找path来破解你的一些逻辑,但是我强烈建议不要这样做。

我想我可以看到对角线移动的不确定性,或者不同的速度倍数,但是pdf将再次指示使用相同的预留表格,并且为移动速度不适合干净的单元保留更大的空间由表建立。 如果一个单位正在对角线移动,并且在预留表的某个部分期间将部分占用多个图块,则保留该间隔的所有图块。 如果从现在开始x秒,则由于以不是表格中使用的间隔的干净倍数的速度移动,更快或更慢的单位将部分地在一个瓦片中并且部分地在另一个瓦片中,保留这两个瓦片。

最后,从跑步到步行的单位速度变化不应该产生第二个预定表,它应该沿着一个预定表刷新所有单位共享的单位path。

唯一的情况是,如果你有不同的移动高度(2D游戏或3D渲染游戏,移动限于2D平面),那么飞行单元可以通过头部地面单位没有碰撞。 在完整的3D游戏中,您将使用4D预留表。

这可能有助于做一些阅读animation。 从概念上讲,预订表(在我的脑海中)分享了一些animation顶点的元素,这个顶点预计会从这个时间点移动到这个时间点,此时结束,而游戏时钟几乎保证不会完全更新与模型的关键帧间隔一致。