Optimized A-Star algorithm in hexagon-based environment using parallel bidirectional search

Abstract

Shortest path algorithm is one of classic IT problems and already used in many aspects. One of well-known shortest path algorithm is A-Star algorithm. Usually A-Star will be implemented to a Non-Playable Character (NPC) in some games. This paper wants to tell how to optimize A-Star algorithm in a hexagon-based environment using Parallel Bidirectional Search (PBS). The result of this paper is PBS A-Star can be accelerating classics A-Star algorithm by 68.8% faster in hexagon-based environment.