A* pathfinding with Multiple Agents

Question

I've currently been learning and programming pathfinding(in Java) using the A* algorithm. A problem I've run into is when multiple entities are trying to pathfind, they both alter the previousNode(the Node that the Node being calculated on came from), messing up the algorithm, and eventually Node A will point to Node B and Node B will point to Node A.

How can I change the algorithm to either

• Not use this previousNode system that is littered throughout all of the A * algorithms(that I have seen, that is)
• Alter this system to be used concurrently

I am trying to avoid having one entity finish pathfinding, then telling the next entity to pathfinding, and so on. Like doing a wait() - notify() pair in Java.

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;
}

I am specifically talking about(within 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

I don't think you can do A* (or any pathfinding algorithm, for that matter) without somehow storing a backpointer for a given path. So that leaves you with two options

1. Require each agent (Thread, I assume) to create their own copy of the graph to work on. That way each A* call going on won't interfere with one another, as they are working with the fields of the same node on different graphs.
2. Change your A* code to be able to handle multiple concurrent calls.

Option 1 is fairly self-explanatory and probably the better option. If this is just for you, you should probably just go with that one (instead of trying to make A* fully concurrent on a single graph). This would entail adding map as an input parameter (and requiring that concurrent calls should use a different map instance, either throwing an exception or having unspecified behavior if that doesn't occur). Additionally, you should instantiate closedList and openList as new data structures in each call, rather than share a list.

If that's not to your liking - you really want to fully encapsulate the mutli-call usage into the method itself, I think the simplest way you could do this is require an additional parameter of an id - some unique string that is guaranteed not to be the same as the id of another concurrent call. So the header of A* now looks like:

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

From there, change all of the implementations of each of the settable pathfinding fields in Node to a HashMap with the id as the key. From your code, I'm going to guess that your Node class looks something like this:

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;
    }
}

We can edit the edited fields to be able to store many values, by id, as such:

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);
    }
}

From there, simply edit your A* method to give the id from the method call to the getters and setters when called for. So long as two concurrent method calls don't have the same id value, they won't interfere with each other. Three things to keep in mind for this to work correctly:

1. Make sure that every editable field gets this treatment. It won't work if you forget about one. Non-editable fields (fields that don't get altered as a byproduct of running A*) can stay singular.
2. If you use the the above, you should probably add to the cleanup stage a step of removing all the information for the given ID from the graph, or the nodes' hashmaps will grow larger with each call.

Either way, you still should make openList and closedList new local instances, no matter what concurrent approach you pick. There's nothing to gain from making openList and closedList shared instances, and only bugs can come of it.

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));