多线程 A* 寻路在自上而下游戏中冻结

Question

我一直在制作自上而下的射击游戏，当我生成多个 HostileEntity 时（任何“敌人”的超级 class，包含所有寻路功能），敌人：

游戏一开始不要移动
游戏一开始就开始移动，但是一旦我移动玩家就全部冻结了。

在我的算法中class它冻结在这个函数

public Path backtrackPath(Node fromNode) {
    Path path = new Path();
    
    while(fromNode.getPreviousNode() != null) { 
        path.prependWaypoint(fromNode);
        fromNode = fromNode.getPreviousNode();
    }
    
    reset(); //Resets all of the previousNodes to null
             //so the next iteration will(should) work correctly
    return path;
}

其中 fromNode 是从方法 findPath 中检索到的，并且是寻路算法的“目标”，即玩家的坐标。错误在于它来自，比如说 Node A，它有 previousNode 作为 Node B，而 Node B 有 previousNode 作为 Node A，所以while循环无限循环往复。

一片findPath()

if(neighborIsBetter) { //if the next neighbor node is closer to the goal then current node being checked
    neighbor.setPreviousNode(current); //connects the current Node to the better neighbor Node
    neighbor.setDistanceFromStart(neighborDistanceFromStart);
    neighbor.setHeuristic(getManhattanDistance(neighbor.getCol(), neighbor.getRow(), goalX, goalY));

}

我相信这可能是因为，由于每个敌人只会在玩家的坐标自上次寻路以来发生变化时才会找到路径，一旦玩家移动，每个敌人都会同时寻路，调用 findPath()，并对相同的 Node 进行计算，混淆了之前的节点。

如何防止这种情况发生？ ~~我想到了，不是在 findPath() 中设置前一个节点，而是将其添加到 return 的路径中。~~

上面的测试并没有起作用，因为我相信有多个 neighbor Node 比当前正在计算的节点“更好”，导致相同的 Node 多次出现在路径中。

Answer 1

您在每个路径节点（特定角色路径上的前一个节点）中保存了特定于角色的信息。问题是多个字符可能会使用一个路径节点，而每个节点一次只能容纳一个前一个节点，所以如果多个字符使用它，数据会混淆。

现在如果你想保持设计不变，你可以让每个节点都是线程安全的，阻止其他角色修改它，直到当前角色完成。我不会在这里深入研究同步，您可以在这里找到该信息：http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html

不过我建议您稍微更改一下设计。现在，您想存储 "previous nodes" 以保留角色路径的历史记录。我会在每个角色中存储一个路径对象，该对象会累积角色去过的每个节点。这样每个角色都存储自己的数据，每个节点都存储自己的数据，不特定于任何一个角色。这样，当你想要你的回溯路径时，你可以只使用你一直在构建的成员变量。

因此，假设您在 HostileEntity class 中有一个变量 Path pathHistory;。每次您的实体设置一个新的目标节点时，您都可以将当前节点添加到您的 pathHistory 变量中。如果它超过某种最大阈值，您还可以删除路径历史中真正的旧节点，并且您也可以在不再需要时清除整个节点。这与在桌面程序中维护撤消历史非常相似。

您只需说：

就可以加入这个新设计

public Path backtrackPath() {
    return pathHistory;
}

或者如果你想使用 fromNode 参数，你基本上会搜索 pathHistory 该节点，然后 return 该节点后面的所有路径，否则 return 根本没有路径。

为了告诉一个实体走向目标点，您甚至不需要路径历史，只需要一个算法来找到下一个目标节点并将其存储在实体中。

祝您设计寻路系统顺利！希望这个回答对您有所帮助。

多线程 A* 寻路在自上而下游戏中冻结

Multithreaded A* pathfinding freezes in Top Down Game

java

multithreading

a-star

path-finding