Pathfinding in Strategy Games and Maze Solving Using A* Search Algorithm

摘要

Pathfinding algorithm addresses the problem of finding the shortest path from source to destination and avoiding obstacles. One of the greatest challenges in the design of realistic Artificial Intelligence (AI) in computer games is agent movement. Pathfinding strategies are usually employed as the core of any AI movement system. In this work, A* search algorithm is used to find the shortest path between the source and destination on image that represents a map or a maze. Finding a path through a maze is a basic computer science problem that can take many forms. The A* algorithm is widely used in pathfinding and graph traversal. Different map and maze images are used to test the system performance (100 images for each map and maze). The system overall performance is acceptable and able to find the shortest path between two points on the images. More than 85% images can find the shortest path between the selected two points.