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

作　　者：Nawaf Hazim Barnouti Sinan Sameer Mahmood Al-Dabbagh Mustafa Abdul Sahib Naser Nawaf Hazim Barnouti;Sinan Sameer Mahmood Al-Dabbagh;Mustafa Abdul Sahib Naser(Al-Mansour University College, Baghdad, Iraq)

机构地区：[1]Al-Mansour University College, Baghdad, Iraq

出　　处：《Journal of Computer and Communications》2016年第11期15-25,共12页电脑和通信（英文）

摘　　要：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.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.

关 键 词：Nawaf Hazim Barnouti Sinan Sameer Mahmood Al-Dabbagh Mustafa Abdul Sahib Naser 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]