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*)
