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可以移动屏幕)。
我用一个二插堆存储开放节点。相邻节点的距离为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值对于这些问题…待续