A* search algorithm - PrincekinNicholas/PacMan-AI-Planning GitHub Wiki

Usage

In defender agent, this algorithm has been used for searching best path to a determined goal. At the same time, the attacker agent also uses A star search algorithm to get the path to its target.

Implementation

The A-star search algorithm will calculate the g value and h value for each step and find the best path to the target. The g value is the cost of each step and the h value is the estimated cost from this step to target. Here, the h value will be calculated by the maze distance between to position and the g value will be the cost of each step and this cost will be initialized by the beginning of the game. The g value cost will according to dead end map index which will present the dangerous index of this position. The higher dangerous index it was, higher the costs it will be.

After selecting the target, A* will be used for searching to determine the optimal path to the target. And the defender and attacker will get the first action that the A* algorithm return.

Performance

The performance of A* search algorithm is reliable and efficient. It will always return the optimal path between 2 positions, considering the dead end and the distance. Although, the drawback of A* search algorithm is that it lacks flexibility. If there's a ghost blocking the way, A* will still only return this path. The target becomes unreachable, and the Pacman has to change to a new target.