Real-Time A* Pathfinding

If canvas does not appear here, try a better browser, like chrome.

Here I am using the space map and routes generated by the bubbling process for pathfinding with Real-Time A* search. This example has a pre-generated maze which is mapped with the bubbling technique. After enough of the area has been mapped the starting and goal nodes are identified, and then pathfinding begins.

The Real-Time A* search opperates on two basic principles: choose the best node to select next based on the cost to move to it and the estimated distance of the node from the goal (the heuristic); and consider the heuristic of any node we leave to be the cost and heuristic of the second best route we found. The agent then moves to the node with the lowest total cost, and the search is carried out again. The method means we try in genral to move directly towards the goal if we can, that backtracking is discouraged by the increasing estimated cost from repeatedly visiting nodes, but that it is allowed if necessery. This implementation uses a look ahead over several nodes for the heuristic. This allows the agent to more quickly come to the right decision about the path to take.

You can click on the canvas to set a new goal. This will discard the stored heuristic values (as they are not useful after the goal changes) and then pathfinding begins again.