Multithreaded A* pathfinding freezes in Top Down Game

Question

I have been making a top down shooter, and when I spawn multiple HostileEntity's(the super-class of any "enemy", that contains all of the pathfinding functions), the enemies either:

• Don't move from the start of the game
• Start moving once the game starts, but all freeze once I move the player.

In my Algorithm class it freezes at this function

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

In which fromNode is retrieved from method findPath, and is the "goal", the player's coordinates, of the pathfinding algorithm. The bug is that it goes from, say Node A, which has previousNode as Node B, while Node B has previousNode as Node A, so the while loop runs back and forth indefinitely.

A slice of 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)); 

}

I belive this may be caused because, since each enemy will only find the path when the player's coordinates have changed since the previous pathfinding, once the player moves, each enemy pathfinds at the exact same time, calling findPath(), and does calculations on the same Node's, mixing up the previous Nodes.

How can I prevent this from happening? I've thought of, instead of setting a previous node in findPath(), just adding it to the path to return.

Tested above out and didn't work, as I believe there were multiple neighbor Node's that were "better" than the current Node being calculated, resulting in the same Node being in the path multiple times.

Answer 1

You are holding character-specific information inside of each path node (the previous node on a specific character's path). The problem is that multiple characters may be using a path node, and each node can only hold one previous node at a time, so if multiple characters use it, the data will get mixed up.

Now if you want to keep the design as it is, you could make each node thread-safe, blocking other characters from modifying it until the current character has finished. I won't delve into synchronization here, you can find that information here: http://docs.oracle.com/javase/tutorial/essential/concurrency/sync.html

However what I recommend is that you change the design a bit. Now, you want to store "previous nodes" to keep a history of your characters' paths. I would store a path object in each character that would accumulate each node the character has been to. That way each character stores it's own data, and each node stores it's own data, not specific to any one character. That way, when you want your backtrack path, you can just use the member variable you've been building all along.

So, say you had a variable Path pathHistory;, inside of your HostileEntity class. Every time your entity sets a new destination node, you can add the current node to your pathHistory variable. You can also delete really old nodes in the path history if it surpasses a maximum threshold of some sort, and you can also just clear out the whole thing when you don't need it anymore. It is very similar to maintaining an undo history in a desktop program.

You can incorporate this new design simply by saying:

public Path backtrackPath() {
    return pathHistory;
}

Or if you want to utilize the fromNode parameter, you would essentially search pathHistory for that node, and then return the path of everything behind that node, otherwise return no path at all.

For telling an entity to go towards a goal point, you wouldn't even need a path history, just an algorithm to find the next destination node and store it within the entity.

Good luck in designing your path finding system! I hope this answer is helpful.