A-star算法概述及其在游戏开发中的应用分析

首先需要感谢Amit’s A star PageA-star算法中译本,让我能够全面地了解A-star算法,下面大部分内容也是由原文及中译文中提炼而得。

1. 从Dijkstra算法和最佳优先搜索到A-star算法

1.1 Dijkstra算法

核心思想:

每次都选取距离起始点最近的点,并加入完成列表。算法的效率并不高,但对于没有负数权值边的情况能够得到从起始点到大部分点的最短路径。Dijkstra算法相当于启发式函数h(x) = 0的A-star算法(在后面会详细说明)。

适用领域:

相对于A-star算法,Dijkstra算法也有它适用的领域。当移动单位需要找到从其当前位置出发到N个分散目的地中的一个的最短路径(比如盟军只需抢占N个据点中的任意一个就能取胜,此时盟军需要选择一个离自己最近的据点i即可),Dijkstra算法会比A-star算法更为合适。

原因在于,Dijkstra对所有中间节点一视同仁,并不考虑它们到目的地的实际代价,这就导致该算法会偏执地选择离起点最近的节点,而当当前扩展节点集中出现了任意一个目的地i,算法就可以终止,而得到的目的地i就是N个目的地中距起始点最近的目的地。相反地,A-star算法则需要找到从起始点出发到所有目的地的最短路径,通过比较得到所有最短路径中的最小值。而实际上我们并不需要知道除了最近的目的地之外的其他目的地的路径就是如何。

总而言之,A-star算法更适用于单点对单点的寻径;Dijkstra算法更适用于单点到多点的寻径。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×