淺談A*算法的一個C#實現

作者：blacktear 2009-07-22 17:15:04

最近正在讀云風的《游戲之旅》，看著看著就讀到了A*尋路算法，雖然以前沒有接觸過，但總覺得好奇。于是從網上找了一些C#實現資料便開始研究。

當然，主要參考的算法文檔是“http://www.vckbase.com/document/viewdoc/?id=1422”不過這里并沒有給出實際的源代碼。而搜了一下A*算法的代碼，大都是ActionScript的源碼。畢竟用Flash做一個Demo會方便很多。不過既然都打開了VisualStudio，那么就用寫一個C#實現吧。

A*算法最主要的是對路徑的評分函數。而實際應用時，這個函數的設計會產生不同的結果。從上面的文檔中我們可以很容易地了解到評分F的公式：

F = H + G

當然根據文中提到的簡便方法，我們可以對H和G的計算寫出下面的代碼。

1private int G(int parent)
2{
3    int d = 10;
4    return d + parent;
5}
6private int H(int x, int y, Point end)
7{
8    return (Math.Abs(x - end.X) + Math.Abs(y - end.Y)) * 10;
9}
為了進行尋路的計算，我們還需要一個類來保存針對地圖上某些點遍歷信息的記錄，比如這個點的F、G、H值各是多少，這個點的坐標以及到達這個點的上一個點的坐標。

 1class PathNode : IComparable
 2{
 3    public int G;
 4    public int H;
 5    public int F {
 6        get{
 7            return G + H;
 8        }
 9    }
10
11    public PathNode Parent;
12    public Point Position;
13
14    public PathNode(Point pos)
15    {
16        this.Position = pos;
17        this.Parent = null;
18        this.G = 0;
19        this.H = 0;
20    }
21
22    public override string ToString()
23    {
24        return Position.ToString();
25    }
26
27    IComparable Members#region IComparable Members
28    public int CompareTo(PathNode other)
29    {
30        return F - other.F;
31    }
32    #endregion
33}

PathNode這個類實現了IComparable接口，目的是為了對PathNode列表進行排序。還記得上面提到的文章中的一句話嗎“尋找開啟列表中F值最低的格子。我們稱它為當前格。”沒錯，這就是為這個條件做的準備。對于尋找F值最低的“格子”，把開啟列表一排序就OK了。

在實現實際的算法時，還需要準備3個容器對象：

private List unLockList = new List();
private Dictionary lockList = new Dictionary();
private List path = new List();

前兩個是算法中提到的“開啟列表”和“關閉列表”，最后一個是找到的最終路徑。
最后來實現A*算法：
 1public List FindPath()
 2{
 3    unLockList.Clear();
 4    lockList.Clear();
 5    path.Clear();
 6    doFindPath();
 7    path.Reverse();
 8    return path;
 9}
10
11private void doFindPath()
12{
13    PathNode start = new PathNode(Start);
14    PathNode cur = start;
15    while (true)
16    {
17        if(!lockList.ContainsKey(cur.ToString()))
18            lockList.Add(cur.ToString(), cur);
19        for (int i = 0; i < delta.Length; i++)
20        {
21            Point newp = new Point(cur.Position.X + delta[i][0],
22                cur.Position.Y + delta[i][1]);
23            if (!canWalkOnIt(newp))
24                continue;
25            if (lockList.ContainsKey(newp.ToString()))
26                continue;
27            if (isPointInUnlockList(newp))
28            {
29                PathNode ulnode = __pn;
30                int newg = G(cur.G);
31                if (newg < ulnode.G)
32                {
33                    ulnode.Parent = cur;
34                    ulnode.G = newg;
35                }
36                continue;
37            }
38            PathNode newpn = new PathNode(newp);
39            newpn.G = G(cur.G);
40            newpn.H = H(newp.X, newp.Y, End);
41            newpn.Parent = cur;
42            unLockList.Add(newpn);
43        }
44        if (unLockList.Count == 0)
45            break;
46        unLockList.Sort();
47        cur = unLockList[0];
48        unLockList.Remove(cur);
49        
50        if (cur.Position.Equals(End))
51        {
52            while (cur != null)
53            {
54                path.Add(cur);
55                cur = cur.Parent;
56            }
57            break;
58        }
59    }
60}
61
62private PathNode __pn;
63
64private bool isPointInUnlockList(Point src)
65{
66    __pn = null;
67    foreach (PathNode item in unLockList)
68    {
69        if (item.Position.Equals(src))
70        {
71            __pn = item;
72            return true;
73        }
74
75    }
76    return false;
77}
78
79private bool canWalkOnIt(Point node)
80{
81    if (node.X < 0 || node.Y < 0)
82        return false;
83    if (node.X > Width - 1 || node.Y > Height - 1)
84        return false;
85    return GetNodeValue(node.X, node.Y) >= 0;
86}

沒寫什么注釋，但思路就是上文中的“A*方法總結”。在此就不重新粘貼一遍了。在此需要多啰嗦兩句的是，關閉列表用了一個Dictionary，其實關閉列表的目的就是查找下一個點是否在關閉列表當中，用Dictionary的ContainsKey方法比較容易，畢竟在Hashtable中找個Key總比在List中找個元素要快。

為了簡化C#實現算法，這里只是遍歷了當前點的上下左右4個相鄰點。上文中介紹的是遍歷8個點的情況，不過這也不是很復雜，只不過麻煩點在于G這個方法，需要判斷一下是不是斜向走的。另外對4個相鄰點的遍歷，方法來源于之前看的一段AS代碼，它用了一個偏移量數組來保存8個偏移量。而這里只是保存了4個偏移量。在實際的算法中，循環一下偏移量數組就很方便了（之前見過一個代碼并沒有用這個方法，而是復制了8短類似的函數調用代碼，邏輯上就不如這個看的清晰）。delta數組如下：

private int[][] delta = new int[][]{
    new int[]{0,1},
    new int[]{0,-1},
    new int[]{1,0},
    new int[]{-1,0}
};

另一個C#實現過程中需要注意的地方是如果4個偏移后的新點包含在開啟列表中，那么應該是對開啟列表中對應的PathNode的G值進行更新。如果是重新new一個新的PathNode，然后再加入開啟列表，那么算法就會出現問題，有可能會陷入無限循環。

對于尋路的結果獲取無非就是對PathNode鏈表中每個PathNode進行遍歷，然后放到一個List中再Reverse一下。對于地圖來說，這里用的是一個int數組，元素小于0的時候代表不能通過。而A*算法計算出的結果可能并不是最優的結果，不過其效率還是比較高的，原因在于有了評分函數的幫助可以遍歷更少的節點。

最后，還是貼上整個Demo項目的文件吧，結構和代碼看起來可能并不優雅。

【編輯推薦】

為ASP.NET控件加入快捷菜單
為Asp.net控件寫單元測試(ViewState)
ASP.NET開發程序過程中值得注意的兩個地方
ASP.NET、JSP和PHP究竟哪個好
ASP.NET頁面請求原理淺析

責任編輯：彭凡來源： cnblogs

C#實現