Limited-Damage A*: A path search algorithm that considers damage as a feasibility criterion

摘要

Pathfinding algorithms used in todays computer games consider the path length or a similar criterion as the only measure of optimality. However, these games usually involve opposing parties, whose agents can inflict damage on those of the others. Therefore, the shortest path in such games may not always be the safest one. Consequently, a new suboptimal offline path search algorithm based on the A∗ algorithm was developed, which takes the threat zones in the game map into consideration. Given an upper limit as the tolerable amount of damage for an agent, this algorithm searches for the shortest path from a starting location to a destination, where the agent may suffer damage less than or equal to the specified limit. Due to its behavior, the algorithm is called Limited-Damage A∗ (LDA∗). Performance of LDA∗ was tested in randomly-generated maze-like grid-based environments of varying sizes, and in hand-crafted fully-observable environments, in which 8-way movement is utilized. Results obtained from LDA∗ are compared with those obtained from Multiobjective A∗ (MOA∗), which is a complete and optimal algorithm that yields exact (best) solutions for every case. LDA∗ was found to perform much faster than MOA∗, yielding acceptable sub-optimality in path length.