algorithm - 这个游戏问题怎么解决

Question

我有一个使用 A* 的简单游戏问题:

我们在一棵树中有几个节点，一个节点包含:

1. 拥有力量和元素的怪物
2. 链接到其他节点的方式。
3. 我们杀死这个怪物后获得的加分。

金、木、水、火、地五行。

只有当我们元素的遭遇分数大于或等于怪物的分数时，我们的角色才能杀死怪物。

而且击杀怪物后必须将所有的bonus point加到一个元素的分数上，不能拆分成多个元素。

目标:找到到特定节点的最短路径。

我的解决方案:我将使用 A*:

启发式:Dijkstra

find(mainCharacter,node,plusPoint) {
  // node here is the node has smallest f
  shortestWay[5] ways;
  foreach(element in elements) {
       mainCharacter->element += plusPoint;
       if (mainCharacter can beat the monster in node) {
           bestNode is node has the smallest f in node->neighbourNodes
           *ways[element] ++ << the steps, we plus point to the first element at very first path. it can be -1 if we can't go.
           find(mainCharacter,bestNode,node->plusPoint)
       }
}
Our goal will be the *ways[element] with the smallest step.

我的问题:

我的解决方案是否正确且足够好？

这个游戏有没有更好的解决方案？

先谢谢了:)

Answer 1

我不确定 A* 是否允许您这样做。

这里的主要问题是，当您探索新节点时，您的可用节点会发生变化。这意味着有时回溯可能是值得的。

示例:您在节点 A，该节点通向 B 和 C。B 通向 E。E 通向 F，F 通向 G，G 通向 D。C 通向 D，这是您的目的地。

B 由 2 级元素守卫，C 由 4 级元素守卫。你的力量是 3。E F 和 G 都有力量 2 元素。

从A你只能去B和C。C太强大了，所以你去B。你可以一直绕到A B E F G D，或者你可以回溯:A B A C D。(在你去掉B之后，C是不再太强大了。)

因此，无论您提出什么算法，您最终都会进行大量的重新评估。由于潜在的回溯，这甚至不受 O(n!) 的限制。

我会采取的方法是查看最短路线而不回溯。这是你的上限，应该很容易用 A* (我认为......)或类似的东西来做。然后你可以找到比这个距离更短的地理路径(忽略功率水平)。从那里开始，您可以开始消除能量障碍，直到 1) 将它们全部放下，或 2) 获得额外能量以通过障碍所需的地理距离将距离推到上限。