An improved pathfinding algorithm based on sorted linked list and indexed array

摘要

A* algorithm is a famous heuristic algorithm in artificial intelligence. It is mainly applied to path planning in game programming. One important characteristic of A* algorithm is there are two lists in it. One is open list, the other is close list. By analyzing operating type, operating times of the two lists, and the complexity of several data structure when implementing the two lists, this paper represents the open list and close list by cooperative sorted linked list and indexed array. Cooperative sorted linked list and indexed array make full use of respective advantage of sorted linked list and indexed array. Comparing with indexed array, it saves about 10% time.