Parallelizing Bidirectional A* Algorithm
Sumit Sharma, Shashwat Srijan, J V.Vidhya · Advances in parallel computing · 2020
Dijkstra’s algorithm is one of the simplest shortest path finding algorithm. A star(A*) algorithm is a variation of the shortest path first Dijkstra’s algorithm and is very commonly used in games using heuristics. The idea behind A* is to assign weight to each open node and then use a heuristic to calculate the cost from start to finish. A* uses heuristics and cost functions to find the most appropriate path in games and robotics. Games are needed to be fast and so we can have tradeoffs between speed and accuracy. So instead of accuracy we focus more on speed which is not needed in some of the situations like autonomous vehicles and simulation games. So, the A* algorithm may underestimate the costs but will never overestimate it. Bidirectional A*reduces the computation by calculating the shortest path from the source as well as the destination. A solution may be the General-Purpose Graphics Processing Units. It can be used to enhance the processing and execution speed of Bidirectional A* algorithm by using parallel processing and multiple threads. GPU based path finding may be approximately 45 times as fast as CPU pathfinding mechanism.