Hero Image
Algorithms

A-Star Path Planning Algorithm 应用场景 很多NPC或者机器人(AI)需要自动寻路的功能来达到与玩家交互的功能。例如吃鸡游戏中,机器人在城镇中跑毒就需要自动寻路,不然可能就被墙卡死了。A-Star(A*)寻路算法原理与实现 算法简介 A* 算法是一种很常用的路径查找和图形遍历算法,最初发表于 1968 年,由 Stanford 研究院的 Peter Hart, Nils Nilsson 以及 Bertram Raphael 发表。它可以被认为是 Dijkstra 算法的扩展。 由于借助启发函数的引导,A* 算法通常拥有更好的性能。路径规划之 A* 算法 发展历程 广度优先搜索:从起点开始,首先遍历起点周围邻近的点,然后再遍历已经遍历过的点邻近的点,逐步的向外扩散,直到找到终点。 这种算法就像洪水(Flood fill)一样向外扩张。 Dijkstra算法:在Dijkstra算法中,需要计算每一个节点距离起点的总移动代价。同时,还需要一个优先队列结构。对于所有待遍历的节点,放入优先队列中会按照代价进行排序。 在算法运行的过程中,每次都从优先队列中选出代价最小的作为下一个遍历的节点。直到到达终点为止。 最佳优先搜索:在一些情况下,如果我们可以预先计算出每个节点到终点的距离,则我们可以利用这个信息更快的到达终点。 其原理也很简单。与Dijkstra算法类似,我们也使用一个优先队列,但此时以每个节点到达终点的距离作为优先级,每次始终选取到终点移动代价最小(离终点最近)的节点作为下一个遍历的节点。 A*算法 A*算法实际上是综合上面这些算法的特点于一身的。 A*算法通过下面这个函数来计算每个节点的优先级。 $$ f(n) = g(n) + h(n) $$ 其中: $ f(n) $ 是节点 $ n $ 的综合优先级。当我们选择下一个要遍历的节点时,我们总会选取综合优先级最高(值最小)的节点。 $ g(n) $ 是节点 $ n $ 距离起点的代价。 $ h(n) $ 是节点 $ n $ 距离终点的预计代价,这也就是 A* 算法的启发函数。 A* 算法在运算过程中,每次从优先队列中选取 $ f(n) $ 值最小(优先级最高)的节点作为下一个待遍历的节点。