C#開發WPF/Silverlight動畫及游戲系列教程(Game Course)：(七)傳說中的A*尋徑算法
關於地圖引擎方面的處理涉及到兩個方面的知識：
1）地圖的實現（包括地圖的切割、合成、呈現方式等）
2）地圖物件的實現（包括地圖中實現尋路、遮罩、傳送點等）
為了讓大家能更加有興趣深入後面的知識，我選擇先從地圖尋路開始講解吧：
目前游戲中的尋路最經典的莫過於A*(A Star)尋路了，它是一種尋路思維的合集，那麼基於它產生的算法則又有多種，例如曼哈頓啟發式算法、對角線取徑算法、歐幾裡德幾何算法、最大取值算法等等，不同的算法產生的效果不同：如計算出路徑需要的總時間，得到的路徑長短優劣等，並且參數的不同也將導致結果的大異。我借助國外一位牛人的A*尋徑工具(有興趣的朋友可以在http://www.codeguru.com/csharp/csharp/cs_misc/designtechniques/article.php/c12527/中找到相關資源)，分別通過對各種路徑使用各種A*算法來尋徑，最終通過花費時間和路徑的優美性進行了橫向與縱向的比較評分，得出速度最快的算法：曼哈頓啟發式算法。它在所有的包括就算九曲十八彎的復雜路徑計算中均能表現極其優異的速率，下圖為測試的部分截圖：
圖中棕色格子代表障礙物，起點位於左上角，終點在中間的紅色邊框格子，藍色格子代表找到的路徑。從圖中右下角可以看到，就算如此復雜的充滿分支的迷宮中仍可以在3毫秒中找到最佳路徑，這是極其優異的。那麼很多朋友看到這可能會感覺如此復雜的程序，哪是一般人能寫出來的？其實說難還是有一些難度的，但是幸運的是，我們的同胞已經將一篇入門文章翻譯出來了，我看了一下很不錯，該翻譯文章地址如下（看該文章請有耐心不長不短，但是看完以後將有非常大的收獲！）：http://data.gameres.com/message.asp?TopicID=25439，那麼我們該如何通過C#代碼來實現曼哈頓A*呢？我拋磚引玉簡單原理描述一下：從起點開始發散式的尋找周圍8個點，通過各種條件篩選出最優的那個點，然後將此點再作為起點繼續循環以上過程，最後我們得到的所有起點集合即為最終路徑。是不是覺得不太難了？呵呵，那麼大家動手寫寫吧！(大家完全可以參考我給大家的那位外國牛人寫的程序，裡面有源碼，通過參考源碼，相信大家花些時間完全可以輕易的實現自己的A*)
接著，我將自己寫好的曼哈頓A*尋徑所有代碼封裝在QX.Game.PathFinder這個命名空間中，那麼到此才進入本文的關鍵，如何通過C#來模擬角色尋路：
首先當然是引用：using QX.Game.PathFinder;
接著我們初始化需要的變量：
Rectangle rect;
private IPathFinder PathFinder = null;
private byte[,] Matrix = new byte[1024, 1024]; //尋路用二維矩陣
private int GridSize = 20; //單位格子大小
private System.Drawing.Point Start = System.Drawing.Point.Empty; //移動起點坐標
private System.Drawing.Point End = System.Drawing.Point.Empty; //移動終點坐標
這裡要特別講解一下GridSize這個變量，它定義了窗口坐標系中以多大一個尺寸來確定游戲坐標系的一個單元格(大家可以這樣理解這兩種不同的坐標系：假如游戲窗口大小為800*600像素，那麼窗口坐標系中的(80,100)這個坐標，根據GridSize = 20來換算，在游戲坐標系中的坐標則為(80/20,100/20)=(4,5))。大家同時可以聯想一下SLG類型游戲，人物處於的每個單元格都是由N*N像素組成的方塊，GridSize就相當於N了；而該格子在游戲坐標系中的顯示坐標則為((N/20), (N/20))，這樣應該很好理解了吧。這樣根據不同的需要來使用GridSize對坐標系進行縮小(/GridSize)和放大(*GridSize)操作，從而可以非常方便的實現各種效果並且被不同的情況所調用，後面的內容及章節會涉及到相關知識。
那麼接下來我們在窗體構造函數中初始化二維矩陣，代碼如下：
public Window7() {
InitializeComponent();
ResetMatrix(); //初始化二維矩陣
}
private void ResetMatrix() {
for (int y = 0; y < Matrix.GetUpperBound(1); y++) {
for (int x = 0; x < Matrix.GetUpperBound(0); x++) {
//默認值可以通過(非障礙物)在矩陣中用1表示
Matrix[x, y] = 1;
}
}
//構建障礙物(舉例)
for (int i = 0; i < 18; i++) {
//障礙物在矩陣中用0表示
Matrix[i, 12] = 0;
rect = new Rectangle();
rect.Fill = new SolidColorBrush(Colors.Red);
rect.Width = GridSize;
rect.Height = GridSize;
Carrier.Children.Add(rect);
Canvas.SetLeft(rect, i * GridSize);
Canvas.SetTop(rect, 12 * GridSize);
}
//構建其他障礙物……(省略)
Start = new System.Drawing.Point(1, 1); //設置起點坐標
}
那麼有了我們前面6節的知識基礎並結合相應的注釋，這些代碼應該很容易可以接受。主要作用是定義起點，初始化矩陣中所有元素（默認都是可以通行的賦值1），然後我們可以設置些障礙物來測試我們尋徑的效果，即根據需要將矩陣中需要變成障礙物的元素賦值0，這樣我們就將所有的准備工作做好了。
最後就是如何實現尋徑啦，代碼如下：
private void Carrier_MouseLeftButtonDown(object sender, MouseButtonEventArgs e) {
Point p = e.GetPosition(Carrier);
int x = (int)p.X / GridSize;
int y = (int)p.Y / GridSize;
End = new System.Drawing.Point(x, y); //計算終點坐標
PathFinder = new PathFinderFast(Matrix);
PathFinder.Formula = HeuristicFormula.Manhattan; //使用我個人覺得最快的曼哈頓A*算法
PathFinder.SearchLimit = 2000; //即移動經過方塊(20*20)不大於2000個(簡單理解就是步數)
List<PathFinderNode> path = PathFinder.FindPath(Start, End); //開始尋徑
if (path == null) {
MessageBox.Show("路徑不存在！");
} else {
string output = string.Empty;
for (int i = path.Count - 1; i >= 0; i--) {
output = string.Format(output
+ "{0}"
+ path[i].X.ToString()
+ "{1}"
+ path[i].Y.ToString()
+ "{2}",
"(", ",", ") ");
rect = new Rectangle();
rect.Fill = new SolidColorBrush(Colors.Green);
rect.Width = GridSize;
rect.Height = GridSize;
Carrier.Children.Add(rect);
Canvas.SetLeft(rect, path[i].X * GridSize);
Canvas.SetTop(rect, path[i].Y * GridSize);
}
MessageBox.Show("路徑坐標分別為:" + output);
}
}
這裡我將鼠標左鍵點擊的點作為尋徑的動態終點，然後創建尋徑類PathFinder，接著定義好參數後就可以通過List<PathFinderNode> path = PathFinder.FindPath(Start, End);來實現尋徑了。最後通過MessageBox將我們找到的路徑點逐一打印出來，至此就完成了我們完美的曼哈頓A*尋徑了。
上圖為程序運行圖，綠色代表找到的路徑，紅色代表障礙物，找到的路徑同樣如此的完美！是不是很有成就感？
有了這A*算法尋徑類，可以說地圖引擎就好比完成了一半不為過；那麼下一節我將介紹如何通過此節獲取的List<PathFinderNode> path列表來實現按照此列表實現的動態關鍵幀動畫，敬請期待。
