This is the Unidirectional and Bidirectional A Star Search Algorithm Python Implementation. For more info about this algorithm: https://en.wikipedia.org/wiki/A*_search_algorithm
Important Details Regarding the Implementation (Unidirectional A star search Algorithm):
-
For the heuristic, Euclidean distance/octile have been used to get an estimate from the given node to the goal node.
-
In order to address the ties (nodes having the same F value in our (discovered) heap, then we prefer using that node whihc are closer to the goal node i.e. node having higher H value.)
Important Details Regarding the Implementation (Bidirectional A star search Algorithm):
-
For the heuristic, Euclidean distance/octile have been used to get an estimate from the given node to the goal node.
-
The node selction policy that is being used here is : we select that frontier which offers us the node with minimum f-value.
-
The stopping condition that is being used here is: we stop as soon as we come across such a node from either of the frontiers, that happens to be in the closed list of the opposite frontier.
NOTE:
-
If the source/target node happens to be such a node which is not walkable, then the algorithm will return an empty path with a total cost of 0.
-
This particular implementation will only work for 2D maps.
-
In order to get more test cases, please refer to https://www.movingai.com/benchmarks/grids.html