Pathfinding Strategy for Multiple Non-Playing Characters and Agents in a 2.5D Game World

This essay focuses on pathfinding in a 2.5D game world for Non-playing Characters (NPC) and agents. The primary focus is to investigate and determine the optimal pathfinding strategy based on several measures such as steps and time taken to reach the goal. For this investigation the most popular pathfinding algorithms and interaction schemes will be analyzed and tested using standard analysis techniques and test applications. The result of this analysis and testing is that it is shown that the A* algorithm is optimal using the Manhattan distance heuristic. Unfortunately, our testing did not reveal an optimal choice among the three interaction scheme that was tested which were cooperative, non-cooperative and competitive.
2009-02