astar算法的文章已经泛滥,为什么还要写呢?因为近来我研究了我们游戏的寻路算法,对astar又有了更深入的理解。写这文章,一来梳理下自己的理解,二来则是我的博客缺少博文,以astar作为a start再合适不过。

基础

这里不再对astar的基础进行详细介绍。非常详细的介绍请看斯坦福的详尽版astar伪代码如下:

    OPEN = priority queue containing START
    CLOSED = empty set
    while lowest rank in OPEN is not the GOAL:
      current = remove lowest rank item from OPEN
      add current to CLOSED
      for neighbors of current:
        cost = g(current) + movementcost(current, neighbor)
        if neighbor in OPEN and cost less than g(neighbor):
          remove neighbor from OPEN, because new path is better
        if neighbor in CLOSED and cost less than g(neighbor): *
          remove neighbor from CLOSED
        if neighbor not in OPEN and neighbor not in CLOSED:
          set g(neighbor) to cost
          add neighbor to OPEN
          set priority queue rank to g(neighbor) + h(neighbor)
          set neighbor's parent to current

    reconstruct reverse path from goal to start
    by following parent pointers

* 如果启发算法是可采纳的,这种情况将不会出现。但在大地图中,启发算法往往是不可采纳的。

根据这个算法,我用as3实现了astar寻路的一个demo(按space可以移动屏幕)。




Alternative content



我用一个二插堆存储开放节点。相邻节点的距离为1,相间节点的距离为$\sqrt{2}$,
所使用的启发函数如下(也叫八方向寻路):

public static function diagonal(pos0:GraphNode, pos1:GraphNode):Number { 
    var D:Number = 1;
    var D2:Number = Math.SQRT2;
    var d1:Number = Math.abs(pos0.x - pos1.x);
    var d2:Number = Math.abs(pos0.y - pos1.y);
    return (D * (d1 + d2) + (D2 - 2*D) * Math.min(d1, d2));
}

高效

上面的程序对于128×128以下格子的寻路基本是够了,但是对于更大规模的寻路则存在几个问题:

  • 如果查找的路径不能存在,该算法将遍历所有节点
  • 随着地图规模的增大,访问的节点大大增加
  • 每次搜索都要重置所有节点的fgh

对于这些问题…待续