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}
為了進(jìn)行尋路的計(jì)算，我們還需要一個(gè)類(lèi)來(lái)保存針對(duì)地圖上某些點(diǎn)遍歷信息的記錄，比如這個(gè)點(diǎn)的F、G、H值各是多少，這個(gè)點(diǎn)的坐標(biāo)以及到達(dá)這個(gè)點(diǎn)的上一個(gè)點(diǎn)的坐標(biāo)。


 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}

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


前兩個(gè)是算法中提到的“開(kāi)啟列表”和“關(guān)閉列表”，最后一個(gè)是找到的最終路徑。
最后來(lái)實(shí)現(xiàn)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}

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