A Star算法原理及其实现
A －Star算法
A*（A-Star)算法是一种求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。
一、简介
二、寻路方式
三、运行机制
四、常用估价算法
五、示例
一、简介
A*（A-Star)算法是一种求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。注意——是最有效的直接搜索算法，之后涌现了很多预处理算法（如ALT，CH，HL等等），在线查询效率是A*算法的数千甚至上万倍。
公式表示为： f(n)=g(n)+h(n),
其中，
f(n) 是从初始状态经由状态n到目标状态的代价估计，
h(n) 是从状态n到目标状态的最佳路径的估计代价。
（对于路径搜索问题，状态就是图中的节点，代价就是距离）
FGH示意图如下所示（图中格子左下角为G值，右下角为H值，左上角为F值）：
因此从当前格子周边的八个格子中找到下一步所走的格子，依据F值，当F值相同时随机选择。
当然在寻路过程中，会有障碍，不能通过，通过可以行走的格子走到终点。下图中绿色为起点，红色为终点，蓝色是障碍，浅蓝边框是参与计算的格子，A*就是通过这样的一系列计算完成的最优寻路。
二、寻路方式
A* 算法常用的寻路方式有三种：基于单元的导航图、基于可视点的导航图以及导航网格。
1) 基于单元的导航图：将地图划分为由多个正方形或者六边形组成的规则网格，网格点或往各单元的中心可以看作是寻路节点。此种方式适用于塔防、即时战略或者其他频繁动态更新场景的游戏中，但此种方式易造成巨大的内存开销，原因在于寻路过程中，对于复杂地形需要将可行走区域和不可行走区域进行标记，并且需要为单元格记录地形信息，需要消耗大量的存储空间，另外单元格的大小，也影响着寻路结果和内存消耗情况。如下图所示是基于单元的导航图：
2) 基于可视点的导航图实现时，一般先由场景设计者在场景中手工放置一些“路径点”， 然后由设计人员逐个测试这些“路径点”之间的可视性。此种导航方式最大优点在于它的灵活性，分散在各处的路径点是由场景设计者精心选择的，能覆盖绝大部分可行走的区域，还可以将其他一些重要位置的点包含进去。此种方式存在一定的缺点，首先，当场景很大时，手工放置路径点是非常繁琐的工作，也很容易出错，其次，此种方式主要是一些点和线段的集合，角色只能沿着那些边运动，无法表示出实际的二维可行走区域，最后，该种方式也存在组合爆炸的问题，例如：如果设置了100个路径点，就可能需要测试99 * 100条路径。如下图所示，即为基于可视点的导航图
3) 导航网格将游戏场景中的可行走区域划分成凸多边形。导航网格能够表示出可行走区域的真实几何关系，是一个非均匀网格。Unity3D自带的导航系统就简历在导航网格的基础上。导航网格的有点是可以进行精确的点到点移动，其次，非常高效，原因在于多边形的面积可以任意大，因此，只需要较少的多边形，就可以表示出很大的可行走区域，不但占用的内存较小，搜索路径的速度也会有很大的提高。另外，导航网格的生成无需人工干预，只需要通过实现设计好的算法，能够自动地将可行走区域划分成多边形，生成导航网格。导航网格的主要缺点在于生成导航网格需要较长的时间，因此，多用于静态场景中。如下图所示，即为导航网格：
三、运行机制
在A*算法中，使用了两个状态表，分别称为Open表和Closed表。Open表由待考察的节点组成，Closed表由已经考察过的节点组成。
什么样的节点才算是已考察过的呢？对于一个节点来说，当算法已经检查过与它相邻的所有节点，计算出了这些节点的f\g\h值，并把它们放入Open表以待考察，那么，这节点就是“已考察过”的节点。
开始时，Closed表为空，Open表仅包括起始节点，每次迭代中，A*算法将Open表中具有最小代价之的节点去除进行检查，如果这个节点不是目标节点，那么考虑该节点的所有8个相邻节点。对于每个相邻节点按下列规则处理；
（1） 如果相邻节点既不在Open表中，又不在Closed表中，则将它加入Open表中；
（2） 如果相邻节点已经在Open表中，并且新的路径具有更低的代价值，则更新它的信息；
（3） 如果相邻节点已经在Closed表中，那么需要检查新的路径是否具有更低的代价值，如果是，那么将它从Closed表中移出，加入到Open表中，否则忽略。
重复上述步骤，直到到达目标节点。如果在到达目标之前，Open表就已经变空，则意味着在起始位置和目标位置之间没有可达的路径。
四、常用估价算法
（1）曼哈顿距离
标准的启发式函数是曼哈顿距离（Manhattan distance）。考虑你的代价函数并找到从一个位置移动到邻近位置的最小代价D。因此，我的游戏中的启发式函数应该是曼哈顿距离的D倍：
H(n) = D * (abs ( n.x – goal.x ) + abs ( n.y – goal.y ) )
你应该使用符合你的代价函数的衡量单位。
（2）对角线距离
如果在你的地图中你允许对角运动那么你需要一个不同的启发函数。（4 east, 4 north）的曼哈顿距离将变成8*D。然而，你可以简单地移动（4 northeast）代替，所以启发函数应该是4*D。这个函数使用对角线，假设直线和对角线的代价都是D：
h(n) = D * max(abs(n.x - goal.x), abs(n.y - goal.y))
如果对角线运动的代价不是D，但类似于D2 = sqrt(2) * D，则上面的启发函数不准确。你需要一些更准确（原文为sophisticated）的东西：
h_diagonal(n) = min(abs(n.x - goal.x), abs(n.y - goal.y))
h_straight(n) = (abs(n.x - goal.x) + abs(n.y - goal.y))
h(n) = D2 * h_diagonal(n) + D * (h_straight(n) - 2*h_diagonal(n)))
这里，我们计算h_diagonal(n)：沿着斜线可以移动的步数；h_straight(n)：曼哈顿距离；然后合并这两项，让所有的斜线步都乘以D2，剩下的所有直线步(注意这里是曼哈顿距离的步数减去2倍的斜线步数)都乘以D。
（3） 欧几里得距离
如果你的单位可以沿着任意角度移动（而不是网格方向），那么你也许应该使用直线距离：
h(n) = D * sqrt((n.x-goal.x)^2 + (n.y-goal.y)^2)
然而，如果是这样的话，直接使用A*时将会遇到麻烦，因为代价函数g不会match启发函数h。因为欧几里得距离比曼哈顿距离和对角线距离都短，你仍可以得到最短路径，不过A*将运行得更久一些：
（4）平方后的欧几里得距离
我曾经看到一些A*的网页，其中提到让你通过使用距离的平方而避免欧几里得距离中昂贵的平方根运算：
h(n) = D * ((n.x-goal.x)^2 + (n.y-goal.y)^2)
不要这样做！这明显地导致衡量单位的问题。当A*计算f(n) = g(n) + h(n)，距离的平方将比g的代价大很多，并且你会因为启发式函数评估值过高而停止。对于更长的距离，这样做会靠近g(n)的极端情况而不再计算任何东西，A*退化成BFS：
五、示例
本案例采用基于单元的导航图寻路方式以及曼哈顿距离估价法进行实现。
首先需要创建一个格子类Grid：
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System;
/// <summary>
/// 格子类型
/// </summary>
public enum GridType
{
//正常类型
Normal,
//障碍物类型
Obstacle,
//起点类型
Start,
//终点类型
End
}
/// <summary>
/// 格子类（实现IComparable方便排序）
/// </summary>
public class Grid : IComparable
{
//格子坐标x-y
public int x;
public int y;
//格子A*三属性f-g-h
public int f;
public int g;
public int h;
//格子类型
public GridType type;
//格子的归属（父格子）
public Grid parent;
//构造赋值
public Grid (int x, int y)
{
this.x = x;
this.y = y;
}
/// <summary>
/// 实现排序接口方法
/// </summary>
/// <returns>The to.</returns>
/// <param name="obj">Object.</param>
public int CompareTo (object obj)
{
Grid grid = (Grid)obj;
if (this.f < grid.f) {
//升序
return -1;
}
if (this.f > grid.f) {
//降序
return 1;
}
return 0;
}
}
然后主逻辑AStar类：
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
public class MyAStar : MonoBehaviour
{
/// <summary>
/// 单例脚本
/// </summary>
public static MyAStar instance;
//参考物体预设体
public GameObject reference;
//格子数组
public Grid[,] grids;
//格子数组对应的参考物（方块）对象
public GameObject[,] objs;
//开启列表
public ArrayList openList;
//关闭列表
public ArrayList closeList;
//目标点坐标
public int targetX;
public int targetY;
//起始点坐标
public int startX;
public int startY;
//格子行列数
private int row;
private int colomn;
//结果栈
private Stack<string> parentList;
//基础物体
private Transform plane;
private Transform start;
private Transform end;
private Transform obstacle;
//流颜色参数
private float alpha = 0;
private float incrementPer = 0;
void Awake ()
{
instance = this;
plane = GameObject.Find ("Plane").transform;
start = GameObject.Find ("Start").transform;
end = GameObject.Find ("End").transform;
obstacle = GameObject.Find ("Obstacle").transform;
parentList = new Stack<string> ();
openList = new ArrayList ();
closeList = new ArrayList ();
}
/// <summary>
/// 初始化操作
/// </summary>
void Init ()
{
//计算行列数
int x = (int)(plane.localScale.x * 20);
int y = (int)(plane.localScale.z * 20);
row = x;
colomn = y;
grids = new Grid[x, y];
objs = new GameObject[x, y];
//起始坐标
Vector3 startPos =
new Vector3 (plane.localScale.x * -5, 0, plane.localScale.z * -5);
//生成参考物体（Cube）
for (int i = 0; i < x; i++) {
for (int j = 0; j < y; j++) {
grids [i, j] = new Grid (i, j);
GameObject item = (GameObject)Instantiate (reference,
new Vector3 (i * 0.5f, 0, j * 0.5f) + startPos,
Quaternion.identity);
item.transform.GetChild (0).GetComponent<Reference> ().x = i;
item.transform.GetChild (0).GetComponent<Reference> ().y = j;
objs [i, j] = item;
}
}
}
/// <summary>
/// A*计算
/// </summary>
IEnumerator Count ()
{
//等待前面操作完成
yield return new WaitForSeconds (0.1f);
//添加起始点
openList.Add (grids [startX, startY]);
//声明当前格子变量，并赋初值
Grid currentGrid = openList [0] as Grid;
//循环遍历路径最小F的点
while (openList.Count > 0 && currentGrid.type != GridType.End) {
//获取此时最小F点
currentGrid = openList [0] as Grid;
//如果当前点就是目标
if (currentGrid.type == GridType.End) {
Debug.Log ("Find");
//生成结果
GenerateResult (currentGrid);
}
//上下左右，左上左下，右上右下，遍历
for (int i = -1; i <= 1; i++) {
for (int j = -1; j <= 1; j++) {
if (i != 0 || j != 0) {
//计算坐标
int x = currentGrid.x + i;
int y = currentGrid.y + j;
//如果未超出所有格子范围，不是障碍物，不是重复点
if (x >= 0 && y >= 0 && x < row && y < colomn
&& grids [x, y].type != GridType.Obstacle
&& !closeList.Contains (grids [x, y])) {
//计算G值
int g = currentGrid.g + (int)(Mathf.Sqrt ((Mathf.Abs (i) + Mathf.Abs (j))) * 10);
//与原G值对照
if (grids [x, y].g == 0 || grids [x, y].g > g) {
//更新G值
grids [x, y].g = g;
//更新父格子
grids [x, y].parent = currentGrid;
}
//计算H值
grids [x, y].h = Manhattan (x, y);
//计算F值
grids [x, y].f = grids [x, y].g + grids [x, y].h;
//如果未添加到开启列表
if (!openList.Contains (grids [x, y])) {
//添加
openList.Add (grids [x, y]);
}
//重新排序
openList.Sort ();
}
}
}
}
//完成遍历添加该点到关闭列表
closeList.Add (currentGrid);
//从开启列表中移除
openList.Remove (currentGrid);
//如果开启列表空，未能找到路径
if (openList.Count == 0) {
Debug.Log ("Can not Find");
}
}
}
/// <summary>
/// 生成结果
/// </summary>
/// <param name="currentGrid">Current grid.</param>
void GenerateResult (Grid currentGrid)
{
//如果当前格子有父格子
if (currentGrid.parent != null) {
//添加到父对象栈（即结果栈）
parentList.Push (currentGrid.x + "|" + currentGrid.y);
//递归获取
GenerateResult (currentGrid.parent);
}
}
/// <summary>
/// 显示结果
/// </summary>
/// <returns>The result.</returns>
IEnumerator ShowResult ()
{
//等待前面计算完成
yield return new WaitForSeconds (0.3f);
//计算每帧颜色值增量
incrementPer = 1 / (float)parentList.Count;
//展示结果
while (parentList.Count != 0) {
//出栈
string str = parentList.Pop ();
//等0.3秒
yield return new WaitForSeconds (0.3f);
//拆分获取坐标
string[] xy = str.Split (new char[]{ '|' });
int x = int.Parse (xy [0]);
int y = int.Parse (xy [1]);
//当前颜色值
alpha += incrementPer;
//以颜色方式绘制路径
objs [x, y].transform.GetChild (0).GetComponent<MeshRenderer> ().material.color
= new Color (1 - alpha, alpha, 0, 1);
}
}
/// <summary>
/// 曼哈顿方式计算H值
/// </summary>
/// <param name="x">The x coordinate.</param>
/// <param name="y">The y coordinate.</param>
int Manhattan (int x, int y)
{
return (int)(Mathf.Abs (targetX - x) + Mathf.Abs (targetY - y)) * 10;
}
void Start ()
{
Init ();
StartCoroutine (Count ());
StartCoroutine (ShowResult ());
}
}
最后是参考预设体方块的简单实现：
using UnityEngine;
using System.Collections;
using UnityEngine.UI;
public class Reference : MonoBehaviour
{
//颜色材质区分
public Material startMat;
public Material endMat;
public Material obstacleMat;
//显示信息Text
private Text text;
//当前格子坐标
public int x;
public int y;
void Awake ()
{
text = GameObject.Find ("Text").GetComponent<Text> ();
}
//判断当前格子的类型
void OnTriggerEnter (Collider other)
{
if (other.name == "Start") {
GetComponent<MeshRenderer> ().material = startMat;
MyAStar.instance.grids [x, y].type = GridType.Start;
MyAStar.instance.openList.Add (MyAStar.instance.grids [x, y]);
MyAStar.instance.startX = x;
MyAStar.instance.startY = y;
} else if (other.name == "End") {
GetComponent<MeshRenderer> ().material = endMat;
MyAStar.instance.grids [x, y].type = GridType.End;
MyAStar.instance.targetX = x;
MyAStar.instance.targetY = y;
} else if (other.name == "Obstacle") {
GetComponent<MeshRenderer> ().material = obstacleMat;
MyAStar.instance.grids [x, y].type = GridType.Obstacle;
}
}
/// <summary>
/// 鼠标点击显示当前格子基础信息
/// </summary>
void OnMouseDown ()
{
text.text = "XY(" + x + "," + y + ")" + "\n" +
"FGH(" + MyAStar.instance.grids [x, y].f + "," +
MyAStar.instance.grids [x, y].g + "," +
MyAStar.instance.grids [x, y].h + ")";
text.color = GetComponent<MeshRenderer> ().material.color;
}
}