C#實現A*算法（1）

在游戲開發中，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();
　　　　}
　　}