Application of improved A− algorithm in the 3d virtual roaming

摘要

In the three-dimensional virtual map, using A- algorithm can provide navigation for roaming pathfinding of virtual characters. In view of the problem that A- algorithm produces too many redundant nodes and influences the search efficiency when searching path, A- algorithm improved strategies is proposed from two aspects. In order to avoid blind search to produce redundant nodes, the vector angle was introduced as a reference for priority ranking of nodes with a minimum F value, and firstly searching nodes that with higher priority, when those nodes that with minimum F value are more than one in the OPEN state list; the vector angle was introduced to limit the number of redundant nodes when nodes extend. In this way, redundant nodes which add to OPEN status table could be reduced, the efficiency of the algorithm could be improved obviously. In addition, viewing the problem that the path is not smooth and easy to appear jagged turn, the final path will be smoothed to reduce turning times and the quality of roaming picture is improved. The experimental results show that in the three-dimensional virtual roaming map, the improved A- algorithm can search the feasible and optimal path efficiently and reduce the time of algorithm running and the number of nodes and improve the efficiency of search, while making the paths more smooth.