A*算法

完整的A*算法描述如下：

• 初始化open_set和close_set；
• 将起点加入open_set中，并设置优先级为0（优先级最高）；
• 如果open_set不为空，则从open_set中选取优先级最高的节点n：
  • 如果节点n为终点，则：
    • 从终点开始逐步追踪parent节点，一直达到起点；
    • 返回找到的结果路径，算法结束；
  • 如果节点n不是终点，则：
    • 将节点n从open_set中删除，并加入close_set中；
    • 遍历节点n所有的邻近节点：
      • 如果邻近节点m在close_set中，则：
        • 跳过，选取下一个邻近节点
      • 如果邻近节点m不在open_set中，则：
        • 设置节点m的parent为节点n
        • 计算节点m的优先级
        • 将节点m加入open_set中

class Node
{
  public Node parent;
  public bool canWalk;
  public int gridX, gridY;
  public int gCost, hCost;
  public int fCost
  {
    get { return gCost + hCost; }
  }
}
void FindPath(Node startNode, Node endNode)
{
  List<Node> openSet = new List<Node>();
  List<Node> closeSet = new List<Node>();
  openSet.Add(startNode);
  while(openSet.Count > 0)
  {
    Node curNode = openSet[0];
    for(int i=1; i<openSet.Count; ++i)
    {
      if(openSet[i].fCost < curNode.fCost)
      {
        curNode = openSet[i];
      }
    }
    
    if(curNode == endNode)
    {
       GeneratePath(startNode, endNode);
       return;
    }
    
    openSet.Remove(curNode);
    closeSet.Add(curNode);

    foreach(Node node in GetNeibourhood(curNode))
    {
      if(node.canWalk == false || closeSet.Contains(node)) continue;
      if(openSet.Contains(node))
      {
        if(node.gCost > curNode.gCost + GetDistance(curNode, node))
        {
          node.gCost = curNode.gCost + GetDistance(curNode, node);
          node.parent = curNode;
        }
      }
      else
      {
        node.gCost = curNode.gCost + GetDistance(curNode, node);
        node.hCost = GetDistance(node, endNode);
        node.parent = curNode;
        openSet.Add(node);
      }
    }
  }
}

优先级计算公式：F(n) = G(n) + H(n)
G(n):节点n到开始节点的距离
H(n):节点n到结束节点的距离

启发函数:
(1)如果图形中只允许朝上下左右四个方向移动，使用曼哈顿距离（Manhattan distance）。

int deltaX = Mathf.Abs(a.gridX - b.gridX);
int deltaY = Mathf.Abs(a.gridY - b.gridY);
int distance = deltaX+deltaY;

(2)如果图形中允许朝八个方向移动，则可以使用对角距离。

int deltaX = Mathf.Abs (a.gridX - b.gridX);
int deltaY = Mathf.Abs (a.gridY - b.gridY);
if (deltaX > deltaY) {
  return 14 * deltaY + 10 * (deltaX - deltaY);
} else {
  return 14 * deltaX + 10 * (deltaY - deltaX);
}

(3)如果图形中允许朝任何方向移动，则可以使用欧几里得距离（Euclidean distance）。

int deltaX = Mathf.Abs(a.gridX - b.gridX);
int deltaY = Mathf.Abs(a.gridY - b.gridY);
float distance = Mathf.Sqrt(deltaX * deltaX + deltaY * deltaY);