In the field of NPC game or GIS system development, there are more studies on finding the efficient method of the shortest path search problem, especially the research of A* algorithm efficiency optimization in the search of finding shortest path algorithm. Most of the maps used in artificial intelligence or algorithm research are based on arbitrary graphs rather than grid-based graphs. Based on above mentioned scenario, by combining arbitrary graphs with grid graphs and directions, an optimization of A* algorithm is proposed in this study. The heuristic search strategy is improved, which can reduce the scale and range of algorithm search and improve the efficiency of A* algorithm. Finally, the experimental results show that compared with the traditional A* algorithm, after the optimization of A* algorithm, the heuristic search strategy is more accurate and the computational efficiency became more efficient and more quickly.