? ? 首先看一下效果吧：

????首先是點擊“打開”菜單導入了一張背景圖，接著點擊“設置”菜單設置地圖的大?。ㄒ簿褪菐仔袔琢校?，然后點擊“標記障礙”工具畫出了紅色的障礙物，再設置一下藍色的起點和綠色的終點并點擊“測試”就得出了黃色的路徑了。

????“導出”菜單用于導出地圖，也就是用二維數(shù)組表示的地圖，0表示可以通行，1表示障礙物。

導出的地圖數(shù)據(jù)放在同級目錄下的data.txt文件中，該文件是這樣的：

?????第一行是是地圖的行數(shù)m和列數(shù)n，其余數(shù)據(jù)有m行n列，對應地圖中的格子是否有障礙物。

????該程序是C#的WPF程序，而A*算法的功能在由C++實現(xiàn)的DLL中。

? ? 壓縮包可以在?https://github.com/WhiteOrangeChen/Projects 下載，名稱為“地圖制作”，包含了一個exe程序，AStar.dll及C++，WPF源碼及一個使用說明文檔。

????提示，可以用來做小游戲哦^_^。

A*算法的C++實現(xiàn)

????A*算法的主流程：

????

????如果找到路徑，則返回一個路徑的逆序單鏈表；否則否則空。

其中，Node的定義如下：

????Point是一個只包含 int x, y; 的結構體。

????Map是一個描述地圖的結構體：

????添加節(jié)點的函數(shù)：

????也就是只有沒訪問過的才會加入隊列中進行擴展，其中nodes是一個鏈表，保存了實際的節(jié)點數(shù)據(jù)，而隊列queue和visit中保存的都是節(jié)點指針，以便更高效。

????曼哈頓距離的求法，就是 |x1-x2| + |y1-y2|，對于不同的問題，需要的估計代價的函數(shù)不同，具體問題具體分析。

????擴展節(jié)點的函數(shù)

上下左右移動的函數(shù)

????判斷一個點是否有效的函數(shù)

????

最后

????需要幫助的話可以提出來的，也可以合作開發(fā)程序。