# <twoyao>

## Yet, Another Astar Article"

April 14, 2014

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

#### 基础

	OPEN = priority queue containing START
CLOSED = empty set
while lowest rank in OPEN is not the GOAL:
current = remove lowest rank item from OPEN
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
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

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

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));
}

#### 高效

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