java - A* 多智能体寻路

Question

我目前一直在使用 A* 算法学习和编程寻路(用 Java)。我遇到的一个问题是，当多个实体试图寻路时，它们都改变了 previousNode(正在计算的 Node 的 Node on came from), 搞乱了算法，最终 Node A 将指向 Node B 而 Node B 将指向 Node A.

如何将算法更改为其中之一

• 不要使用遍及所有 A * 算法(即我所见)的 previousNode 系统
• 更改此系统以同时使用

我试图避免让一个实体完成寻路，然后告诉下一个实体进行寻路，等等。就像在 Java 中执行 wait() - notify() 对一样。

public Path findPath(int startX, int startY, int goalX, int goalY) { 
  //Path is basically just a class that contains an ArrayList, 
  //containing Nodes,  which contains the steps to reach a goal.
    if(map.getNode(goalX, goalY).isObstacle()) {
        return null;
    }

    map.getNode(startX, startY).setDistanceFromStart(0);
    closedList.clear();
    openList.clear(); //A List with added getFirst() - gets the first Node in the list
    openList.add(map.getNode(startX, startY));

    while(openList.size() != 0) {
        //Node contains a List that has all of the Nodes around this node, a 
        //F, G, and H value, and its row(y) and column(x)
        Node current = openList.getFirst(); 

        if(current.getX() == goalX && current.getY() == goalY)  {
            return backtrackPath(current);
        }

        openList.remove(current);
        closedList.add(current);

        for(Node neighbor : current.getNeighborList()) {
            boolean neighborIsBetter;

            //If I've already searched this neighbor/node, don't check it
            if(closedList.contains(neighbor)) {
                continue;
            }

            if(!neighbor.isObstacle()) {
                float neighborDistanceFromStart = (current.getDistanceFromStart() + map.getDistanceBetween(current, neighbor));

                if(!openList.contains(neighbor)) {
                    openList.add(neighbor);
                    neighborIsBetter = true;
                } else if(neighborDistanceFromStart < current.getDistanceFromStart()) {
                    neighborIsBetter = true;
                } else {
                    neighborIsBetter = false;
                }

                if(neighborIsBetter) {
                    neighbor.setPreviousNode(current);
                    neighbor.setDistanceFromStart(neighborDistanceFromStart);
                    neighbor.setHeuristic(getManhattanDistance(neighbor.getX(), neighbor.getY(), goalX, goalY));
                }
            }
        }
    }

    return null;
}

public Path backtrackPath(Node fromNode) {
    Path path = new Path();
    while(fromNode.getPreviousNode() != null) {
        path.prependWaypoint(fromNode);
        fromNode = fromNode.getPreviousNode();
    }

    return path;
}

我具体说的是(在 findPath() 内)

if(neighborIsBetter) {
    neighbor.setPreviousNode(current); //previousNode is a value in the Node class that points to the Node that it came from
    neighbor.setDistanceFromStart(neighborDistanceFromStart);
    neighbor.setHeuristic(getManhattanDistance(neighbor.getX(), neighbor.getY(), goalX, goalY));
}

Answer 1

如果不以某种方式存储给定路径的反向指针，我认为您无法执行 A*(或任何寻路算法)。所以这给你留下了两个选择

1. 要求每个代理(我假设是线程)创建自己的图表副本以进行处理。这样一来，每个 A* 调​​用都不会相互干扰，因为它们正在处理不同图表上同一节点的字段。
2. 更改您的 A* 代码以能够处理多个并发调用。

选项 1 是不言自明的，可能是更好的选择。如果这只适合您，您可能应该选择那个(而不是试图在单个图上使 A* 完全并发)。这将需要添加 map 作为输入参数(并要求并发调用应使用不同的 map 实例，如果不发生则抛出异常或具有未指定的行为)。此外，您应该在每次调用中将 closedList 和 openList 实例化为新的数据结构，而不是共享一个列表。

如果这不符合您的喜好 - 您真的想将多次调用用法完全封装到方法本身中，我认为您可以做到这一点的最简单方法是需要 id 的附加参数- 保证与另一个并发调用的 id 不同的一些唯一字符串。所以 A* 的标题现在看起来像:

public Path findPath(final String ID, int startX, int startY, int goalX, int goalY) { 

从那里，将 Node 中每个可设置寻路字段的所有实现更改为以 id 为键的 HashMap .根据您的代码，我猜测您的 Node 类看起来像这样:

public class Node{
    //Fields used by the A* call - no problem here
    private boolean obstacle;

    //Fields *edited* by the A* call
    private float distanceFromStart;
    private Node previous;
    private int heuristic;

    //other fields and stuff

    public boolean isObstacle(){
        return obstacle;
    }

    public float getDistanceFromStart(){
        return distanceFromStart;
    }

    public void setDistanceFromStart(float f){
        distanceFromStart = f;
    }

    public Node getPrevious(){
        return previous;
    }

    public void setPrevious(Node p){
        previous = p;
    }

    public int getHeuristic(){
        return heuristic;
    }

    public void setHeuristic(int h){
        heuristic = h;
    }
}

我们可以编辑 edited 字段，以便能够通过 id 存储许多值，例如:

public class Node{
    //Fields used by the A* call - no problem here
    private boolean obstacle;

    //Fields *edited* by the A* call
    private HashMap<String,Float> distanceFromStart;
    private HashMap<String,Node> previous;
    private HashMap<String,Integer> heuristic;

    //other fields and stuff

    public boolean isObstacle(){
        return obstacle;
    }

    public float getDistanceFromStart(String id){
        return distanceFromStart.get(id);
    }

    public void setDistanceFromStart(String id, float f){
        distanceFromStart.put(id, f);
    }

    public Node getPrevious(String id){
        return previous.get(id);
    }

    public void setPrevious(String id, Node p){
        previous.put(id,p);
    }

    public int getHeuristic(String id){
        return heuristic.get(id);
    }

    public void setHeuristic(String id,int h){
        heuristic.put(id,h);
    }
}

从那里，只需编辑您的 A* 方法，以便在调用时将方法调用中的 id 提供给 getter 和 setter。只要两个并发方法调用没有相同的 id 值，它们就不会相互干扰。要使其正常工作，请记住三件事:

1. 确保每个 可编辑字段都得到这种处理。如果您忘记了一个，它将无法工作。不可编辑的字段(不会作为运行 A* 的副产品而改变的字段)可以保持单一。
2. 如果您使用上述方法，您可能应该在清理阶段添加一个步骤，即从图中删除给定 ID 的所有信息，否则节点的 HashMap 会随着每次调用而变大。

无论哪种方式，无论您选择哪种并发方法，您仍然应该创建 openList 和 closedList 新的local 实例。使 openList 和 closedList 共享实例没有任何好处，只会产生错误。

List<Node> closedList = new LinkedList<Node>();
List<Node> openList = new LinkedList<Node>();
//Don't have to clear them anymore - they're new lists
openList.add(map.getNode(startX, startY));