在游戲開發中，AI的最基本問題之一就是尋路算法或稱路徑規劃算法，在三 年前，我曾實現過 基於“圖算法”的最短路徑規劃算法，然而在游 戲中，我們通常將地圖抽象為有單元格構成的矩形，如：
這個微型地圖 由3*3的單元格構成，當然，實際游戲中的地圖通常比它大很多，這裡只是給出 一個示例。
由於游戲地圖通常由單元格構成，所以，基於“圖算法 ”的路徑規劃便不再那麼適用，我們需要采用基於單元格的路徑規劃算法 。A*算法是如今游戲所采用的尋路算法中相當常用的一種算法，它可以保證在任 何起點和任何終點之間找到最佳的路徑（如果存在的話），而且，A*算法相當有 效。
關於A*算法的原理的詳細介紹，可以參考 這篇文章。當你明白A*算 法的原理之後，在來看接下來的A*算法的實現就會比較容易了。
現在， 讓我們轉入正題，看看如何在C#中實現A*算法。
首先，我們把地圖劃分 為單元格，如此，一個地圖就可以由（M行*N列）個單元格構成。我們使用 AStarNode類來抽象單元格，表示一個節點，而節點的位置用Point表示，其X坐 標表示Column Index，Y坐標表示Line Index。AStarNode的定義如下：
Code
[copy to clipboard]CODE:
/// <summary>
/// AStarNode 用於保存規劃到當前節點時的各個 Cost值以及父節點。
/// zhuweisky 2008.10.18
/// </summary>
public class AStarNode
{
#region Ctor
public AStarNode(Point loc, AStarNode previous, int _costG, int _costH)
{
this.location = loc;
this.previousNode = previous;
this.costG = _costG;
this.costH = _costH;
}
#endregion
#region Location
private Point location = new Point(0, 0);
/// <summary>
/// Location 節點所在的位置， 其X值代表ColumnIndex，Y值代表LineIndex
/// </summary>
public Point Location
{
get { return location; }
}
#endregion
#region PreviousNode
private AStarNode previousNode = null;
/// <summary>
/// PreviousNode 父節點，即是由哪個節點導航到當前節點的。
/// </summary>
public AStarNode PreviousNode
{
get { return previousNode; }
}
#endregion
#region CostF
/// <summary>
/// CostF 從起點導航經過本節點然後再到目的節點的估算總代價。
/// </summary>
public int CostF
{
get
{
return this.costG + this.costH;
}
}
#endregion
#region CostG
private int costG = 0;
/// <summary>
/// CostG 從起點導 航到本節點的代價。
/// </summary>
public int CostG
{
get { return costG; }
}
#endregion
#region CostH
private int costH = 0;
/// <summary>
/// CostH 使用啟發式方法估算的從本節點到目的節點的代價。
/// </summary>
public int CostH
{
get { return costH; }
}
#endregion
#region ResetPreviousNode
/// <summary>
/// ResetPreviousNode 當從起點到達本節點 有更優的路徑時，調用該方法采用更優的路徑。
/// </summary>
public void ResetPreviousNode(AStarNode previous, int _costG)
{
this.previousNode = previous;
this.costG = _costG;
}
#endregion
public override string ToString()
{
return this.location.ToString();
}
}
如果 ，你看過上面提到的那篇參考文章，那麼類中的各個屬性的定義就不難理解了。
我們假設，從某個節點出發，最多可以有8個方向移動，這8個方向定義 為CompassDirections：
Code
[copy to clipboard] CODE:
public enum CompassDirections
{
NotSet = 0,
North = 1, //UP
NorthEast = 2, //UP Right
East = 3,
SouthEast = 4,
South = 5,
SouthWest = 6,
West = 7,
NorthWest = 8
}
CompassDirections遵守“左西右東，上北下南”的 地圖方位原則。
而從某個節點出發，朝8個方向之中的某個方向移動是有 代價（Cost）的，而且朝每個方向移動的代價可能是不相同的，而我們的尋路算 法正是要找到起點和終點之間總代價最小的路徑。我們使用一個接口 ICostGetter來獲取從某個節點開始朝8個方向移動的代價值。
Code
[copy to clipboard]CODE:
/// <summary>
/// ICostGetter 獲取從當前節點向某個方向移動 時的代價。
/// </summary>
public interface ICostGetter
{
int GetCost(Point currentNodeLoaction, CompassDirections moveDirection);
}
之所以將其定義為接口，是因為不同的游戲中的對移動代價賦值 是不一樣的。不同的游戲可以自己實現這個接口，以表明自己的代價賦值策略。
盡管如此，我們還是給出一個最簡單的ICostGetter實現以方便我們測試 ，這個實現表示從當前節點向上、下、左、右四個方向的移動的代價是一樣的。
Code
[copy to clipboard]CODE:
/// <summary>
/// SimpleCostGetter ICostGetter接口的簡化實 現。直線代價為10， 斜線為14。
/// </summary>
public class SimpleCostGetter : ICostGetter
{
#region ICostGetter 成員
public int GetCost(Point currentNodeLoaction, CompassDirections moveDirection)
{
if (moveDirection == CompassDirections.NotSet)
{
return 0;
}
if (moveDirection == CompassDirections.East || moveDirection == CompassDirections.West || moveDirection == CompassDirections.South || moveDirection == CompassDirections.North)
{
return 10;
}
return 14;
}
#endregion
}
我們知道，如果定義上、下、左、右的 代價為1，那麼斜線的代價應為根號2，為了提高計算效率，我們將根號2取近似 值為1.4，並將單位放大10倍（計算機對整數的運算比對浮點數的運算要快很多 ）。
我們還需要一個結構來保存在路徑規劃過程中的中間結果：
Code
[copy to clipboard]CODE:
/// <summary>
/// RoutePlanData 用於封裝一次路徑規劃過程中 的規劃信息。
/// </summary>
public class RoutePlanData
{
#region CellMap
private Rectangle cellMap;
/// <summary>
/// CellMap 地圖的矩形大小。經過單元格標准處理。
/// </summary>
public Rectangle CellMap
{
get { return cellMap; }
}
#endregion
#region ClosedList
private IList<AStarNode> closedList = new List<AStarNode>();
/// <summary>
/// ClosedList 關閉列表，即存 放已經遍歷處理過的節點。
/// </summary>
public IList<AStarNode> ClosedList
{
get { return closedList; }
}
#endregion
#region OpenedList
private IList<AStarNode> openedList = new List<AStarNode>();
/// <summary>
/// OpenedList 開放列表，即存 放已經開發但是還未處理的節點。
/// </summary>
public IList<AStarNode> OpenedList
{
get { return openedList; }
}
#endregion
#region Destination
private Point destination;
/// <summary>
/// Destination 目的節點的位置。
/// </summary>
public Point Destination
{
get { return destination; }
}
#endregion
#region Ctor
public RoutePlanData(Rectangle map, Point _destination)
{
this.cellMap = map;
this.destination = _destination;
}
#endregion
}
有了上述這些基礎結構 ，我們便可以開始實現算法的核心功能了：
Code
[copy to clipboard]CODE:
/// <summary>
/// AStarRoutePlanner A*路徑規劃。每個單元格Cell的位置用Point表示
/// F = G + H 。
/// G = 從起點A，沿著產生的路徑，移動到網 格上指定方格的移動耗費。
/// H = 從網格上那個方格移動到終點B 的預估移動耗費。使用曼哈頓方法，它計算從當前格到目的格之間水平和垂直的 方格的數量總和，忽略對角線方向。
/// zhuweisky 2008.10.18
/// </summary>
public class AStarRoutePlanner
{
private int lineCount = 10; //反映地圖高度，對應 Y坐標
private int columnCount = 10; //反映地圖寬度，對應X 坐標
private ICostGetter costGetter = new SimpleCostGetter();
private bool[][] obstacles = null; // 障礙物位置，維度：Column * Line
#region Ctor
public AStarRoutePlanner() :this(10 ,10 ,new SimpleCostGetter())
{
}
public AStarRoutePlanner(int _lineCount, int _columnCount, ICostGetter _costGetter)
{
this.lineCount = _lineCount;
this.columnCount = _columnCount;
this.costGetter = _costGetter;
this.InitializeObstacles();
}
/// <summary>
/// InitializeObstacles 將所有位置均標記為無障礙物。
/// </summary>
private void InitializeObstacles()
{
this.obstacles = new bool [this.columnCount][];
for (int i = 0; i < this.columnCount; i++)
{
this.obstacles = new bool[this.lineCount];
}
for (int i = 0; i < this.columnCount; i++)
{
for (int j = 0; j < this.lineCount; j++)
{
this.obstacles[j] = false;
}
}
}
#endregion
#region Initialize
/// <summary>
/// Initialize 在路徑規劃之前先設置障礙物 位置。
/// </summary>
public void Initialize(IList<Point> obstaclePoints)
{
if (obstacles != null)
{
foreach (Point pt in obstaclePoints)
{
this.obstacles[pt.X][pt.Y] = true;
}
}
}
#endregion
#region Plan
public IList<Point> Plan(Point start, Point destination)
{
Rectangle map = new Rectangle(0, 0, this.columnCount, this.lineCount);
if ((!map.Contains(start)) || (!map.Contains(destination)))
{
throw new Exception ("StartPoint or Destination not in the current map!");
}
RoutePlanData routePlanData = new RoutePlanData(map, destination);
AStarNode startNode = new AStarNode(start, null, 0, 0);
routePlanData.OpenedList.Add(startNode);
AStarNode currenNode = startNode;
//從起始節點開始進行遞歸調用
return DoPlan(routePlanData, currenNode);
}
#endregion
#region DoPlan
private IList<Point> DoPlan(RoutePlanData routePlanData, AStarNode currenNode)
{
IList<CompassDirections> allCompassDirections = CompassDirectionsHelper.GetAllCompassDirections();
foreach (CompassDirections direction in allCompassDirections)
{
Point nextCell = GeometryHelper.GetAdjacentPoint(currenNode.Location, direction);
if (!routePlanData.CellMap.Contains(nextCell)) //相鄰 點已經在地圖之外
{
continue;
}
if (this.obstacles[nextCell.X][nextCell.Y]) //下一個Cell為障礙物
{
continue;
}
int costG = this.costGetter.GetCost (currenNode.Location, direction);
int costH = Math.Abs(nextCell.X - routePlanData.Destination.X) + Math.Abs (nextCell.Y - routePlanData.Destination.Y);
if (costH == 0) //costH為0，表示相鄰點就是目的點，規劃完成，構造結果路徑
{
IList<Point> route = new List<Point>();
route.Add (routePlanData.Destination);
route.Insert(0, currenNode.Location);
AStarNode tempNode = currenNode;
while (tempNode.PreviousNode != null)
{
route.Insert(0, tempNode.PreviousNode.Location);
tempNode = tempNode.PreviousNode;
}
return route;
}
AStarNode existNode = this.GetNodeOnLocation(nextCell, routePlanData);
if (existNode != null)
{
if (existNode.CostG > costG)
{
//如果 新的路徑代價更小，則更新該位置上的節點的原始路徑
existNode.ResetPreviousNode(currenNode, costG);
}
}
else
{
AStarNode newNode = new AStarNode(nextCell, currenNode, costG, costH);
routePlanData.OpenedList.Add(newNode);
}
}
//將已遍歷過的節點從開放列表轉移到關閉 列表
routePlanData.OpenedList.Remove(currenNode);
routePlanData.ClosedList.Add(currenNode);
AStarNode minCostNode = this.GetMinCostNode (routePlanData.OpenedList);
if (minCostNode == null) //表明從起點到終點之間沒有任何通路。
{
return null;
}
//對開放列表 中的下一個代價最小的節點作遞歸調用
return this.DoPlan(routePlanData, minCostNode);
}
#endregion
#region GetNodeOnLocation
/// <summary>
/// GetNodeOnLocation 目標位置location是 否已存在於開放列表或關閉列表中
/// </summary>
private AStarNode GetNodeOnLocation(Point location, RoutePlanData routePlanData)
{
foreach (AStarNode temp in routePlanData.OpenedList)
{
if (temp.Location == location)
{
return temp;
}
}
foreach (AStarNode temp in routePlanData.ClosedList)
{
if (temp.Location == location)
{
return temp;
}
}
return null;
}
#endregion
#region GetMinCostNode
/// <summary>
/// GetMinCostNode 從開放列表中獲取代價F最小的節點，以啟動下一次遞 歸
/// </summary>
private AStarNode GetMinCostNode(IList<AStarNode> openedList)
{
if (openedList.Count == 0)
{
return null;
}
AStarNode target = openedList[0];
foreach (AStarNode temp in openedList)
{
if (temp.CostF < target.CostF)
{
target = temp;
}
}
return target;
}
#endregion
}
代碼中已經加了詳盡的注釋，要注意的有以下幾點：
1.Initialize方法用於初始化障礙物的位置，所謂“障礙物 ”，是指導航時無法穿越的物體，比如，游戲中的牆、河流等。
2. 標記為紅色的ResetPreviousNode方法調用處，說明，到達當前節點的當前路徑 比已存在的路徑代價更小，所以要選擇更優的路徑。
3.標記為黑體的 route.Insert(0, tempNode.PreviousNode.Location);方法調用，表示已經找到 最優路徑，此處便可通過反向迭代的方式整理出從起點到終點的最終路徑。
4.CostH 的計算使用曼哈頓方法，它計算從當前格到目的格之間水平和 垂直的方格的數量總和，忽略對角線方向。
5.在該算法中，至少還有一 個地方可以優化，那就是GetMinCostNode方法所實現的內容，如果在路徑搜索的 過程中，我們就將OpenList中的各個節點按照Cost從小到大進行排序，那麼每次 GetMinCostNode時，就只需要取出第一個節點即可，而不必在遍歷OpenList中的 每一個節點了。在地圖很大的時候，此法可以大幅提升算法效率。
最後 ，給出一個例子，感受一下：
Code
[copy to clipboard] CODE:
AStarRoutePlanner aStarRoutePlanner = new AStarRoutePlanner();
IList<Point> obstaclePoints = new List<Point>();
obstaclePoints.Add(new Point(2, 4));
obstaclePoints.Add(new Point(3, 4));
obstaclePoints.Add(new Point(4, 4));
obstaclePoints.Add(new Point(5, 4));
obstaclePoints.Add(new Point(6, 4));
aStarRoutePlanner.Initialize(obstaclePoints);
IList<Point> route = aStarRoutePlanner.Plan(new Point(3, 3), new Point(4, 6));
運行後，返回的route結果如下：
{3,3}, {2,3}, {1,3}, {1,4}, {1,5}, {2,5}, {2,6}, {3,6}, {4,6}
