A*算法的簡單實現

前幾天導師布置了個任務，讓做一個C/S架構的小游戲。。其中設計到地圖上自動尋路的一個功能點，我一向對算法沒有愛，不過又特別喜歡那些神奇的算法。。。我這算不算變態。。又愛又無愛。。不管怎麼說，我先想的是DFS或者BFS，不過我想了想，如果真的這麼簡單那麼這尼瑪不是所有搜索通殺了嗎。。於是我懷著謙虛的心去問了下google大爺。。果然找到了很多有用的東西，比如A*算法。。。網上有個爺們把這個算法寫的異常清晰，真的是異常清晰。。。

原文在這裡：http://www.policyalmanac.org/games/aStarTutorial.htm

你說什麼！是英文的，廢話！！！牛逼的東西哪樣不是英文的，裝的最高境界就是滿嘴英文縮寫。對吧！！！

好了，開玩笑的，這裡有中文翻譯：

http://www.cppblog.com/christanxw/archive/2006/04/07/5126.html

這哥們翻譯的也還不錯。。不過還是建議看英文的。。算了，當我沒說。

文章裡作者用Basic和C++都實現了這個算法。不過就像所有網上下的東西一樣，沒一個是能夠直接拿來用的，就像你現在看我的代碼一樣，照樣不能直接用進你的工程裡。不過別人寫出來了，就一定有道理，看看對自己的實現多少有些幫助。

我用C++實現了下A*算法。當然，在原文裡作者智慧得指出了用二叉堆來維護open_list表會更加高效，能夠提高2~4倍。並給出另一篇他寫的用二叉堆來實現的A*算法。。http://www.policyalmanac.org/games/binaryHeaps.htm

別煩躁，中文翻譯當然有了：http://blog.vckbase.com/panic/archive/2005/03/28/4144.html

我當然是膜拜不已。。但是我這邊的程序要的非常急。。所以這裡我先用list做了open_list，等以後閒了我再自己寫一個BFS,DFS,A*和二叉堆A*的性能比較！！我是不是很牛！！。。。好吧。。當我沒說。。

文章附件裡我把那個老外的代碼和我自己的實現都放在下面了，我建議你都下載來看看，這樣能夠明白我寫的要更好！！！哈哈哈。。。。。而且我的代碼裡有不少注釋哦，並且測試程序都寫好了哦。。。。。是不是很誘惑。。。好吧。。我又泛濫了。。最後補充一點，我的代碼拿VS2005寫的工程，那個老外的是VC++的工程，如果你不能跑就把代碼貼出來到你的編譯環境裡改改就能跑了。你一定在想世界上要是只有一種編譯器多好啊。。。好吧，是我在想。。不過未來肯定能實現，直接用雲端編譯，我只需要本地編寫代碼，然後上傳遠端，把編譯結果返回給我，只要速度夠快我覺得這是一種非常好的處理代碼異構，編譯器異構的方式。。。好吧。。我又扯淡了。。。

下面show一下我的A*算法的類：

首先是A.h

////////////////////////////////////////////////////////////////////////////////////// 
// 
//  FileName    :   A.h 
//  Version     :   1.0 
//  Creater     :   Ranger Cai 
//  Date        :   2012-2-27 09:44:49 
//  Comment     :   A* algorithm header file 
// 
////////////////////////////////////////////////////////////////////////////////////// 
#ifndef _A_FINDPATH_H 
#define _A_FINDPATH_H 
 
#include <list> 
#include <algorithm> 
 
//記錄地圖上每個節點的位置信息以及估值信息的結構體堆棧 
typedef struct _Rect 
{ 
    int x; 
    int y; 
    int h_value;  //h值為節點到終點的Manhattan距離 
    int g_value;  //g值為起點到該點的移動代價 
    struct _Rect *pre;  //指向父節點 
}Rect; 
 
class AStart 
{ 
public: 
    //初始化傳入地圖二維數組、地圖寬、長，起始及終點在數組中的序號 
    AStart(int *mapInfo, int width, int height, int start, int end); 
    ~AStart(); 
 
    //A*查找，查找成功返回true，否則返回false 
    bool Find(); 
    //如果Find()函數成功，則可以調用此函數把結果路徑存入到result中 
    void getResultPath(); 
     
    //計算pos節點的g值 
    int get_g_value(int pos); 
    //計算pos節點的h值 
    int get_h_value(int pos); 
    //判斷pos節點是否在地圖內 
    bool isReachable(int pos); 
    //測試節點是否更好並判斷是否已經找到路徑 
    bool testRoad(int pos, int cur); 
 
    int  *map;  //地圖信息 
    Rect *rect; //父子節點關系鏈 
    std::list<Rect> result;  //查找成功後的結果路徑保存在此 
 
private: 
    int Width; 
    int Height; 
    int Start; 
    int End; 
 
    std::list<int> open_list;   //open表中的節點為待檢查的節點 
    std::list<int> close_list;  //close表中的節點為暫時不關注的節點 
}; 
 
#endif //_A_FINDPATH_H 

然後是實現A.cpp

#include "stdafx.h" 
#include "A.h" 
 
 
AStart::AStart(int *mapInfo, int width, int height, int start, int end) 
{ 
    Width  = width; 
    Height = height; 
    Start  = start; 
    End    = end; 
 
    //把二維數組保存到一維數組中去，便於信息的處理 
    map = new int[Width * Height]; 
    for (int i = 0; i < Width * Height; i++) 
    { 
        //map[i] = mapInfo[i / width][i % width]; 
        map[i] = mapInfo[i]; 
    } 
 
    //記錄每一個節點的位置信息 
    rect = new Rect[Width * Height]; 
    for (int i = 0; i < (Width * Height); i++) 
    { 
        rect[i].x = i % Width; 
        rect[i].y = i / Width; 
    } 
 
    //初始化起點 
    rect[Start].g_value = 0; 
    rect[Start].h_value = get_h_value(Start); 
    rect[Start].pre = NULL; 
 
    //把起點加入open_list中 
    open_list.push_back(Start); 
} 
 
AStart::~AStart() 
{ 
    if (map != NULL) 
    { 
        delete[] map; 
    } 
    if (rect != NULL) 
    { 
        delete[] rect; 
    } 
} 
 
int AStart::get_g_value(int pos) 
{ 
    //只允許玩家往上下左右四個方向行走，所以這裡的g值只需要在父節點的g值上加10 
    return (rect[pos].pre->g_value + 10); 
} 
 
int AStart::get_h_value(int pos) 
{ 
    //返回該點到終點的Manhattan距離，乘以10是為了方便計算機計算 
    return (10 * (abs(End / Width - pos / Width) + abs(End % Width - pos % Width))); 
} 
 
void AStart::getResultPath() 
{ 
    Rect *temp = &rect[End]; 
    while (temp != NULL) 
    { 
        result.push_back(*temp); 
        temp = temp->pre; 
    } 
    return; 
} 
 
bool AStart::isReachable(int pos) 
{ 
    if ((pos / Width < Height) && (pos / Width >= 0) && 
        (pos % Width < Width)  && (pos % Width >= 0)) 
    { 
        return true; 
    } 
    else 
    { 
        return false; 
    } 
} 
 
//如果pos不可達或者它在close_list中則跳過它，否則，進行如下操作 
//如果pos不在open_list中則加入open_list，並把當前方格設置為它的父親 
//如果pos在open_list中則檢查g的大小，如果更小則把它的父親設置為當前方格 
bool AStart::testRoad(int pos, int cur) 
{ 
    if (isReachable(pos)) 
    { 
        if (pos == End) 
        { 
            rect[pos].pre = &rect[cur]; 
            return true; 
        } 
        if (map[pos] != 1) //1代表障礙物，0則可通行 
        { 
            if (close_list.end() == find(close_list.begin(), close_list.end(), pos)) 
            { 
                std::list<int>::iterator iter = find(open_list.begin(), open_list.end(), pos); 
                if (iter == open_list.end()) 
                { 
                    open_list.push_back(pos); 
                    rect[pos].pre = &rect[cur]; 
                    rect[pos].h_value = get_h_value(pos); 
                    rect[pos].g_value = get_g_value(pos); 
                } 
                else 
                { 
                    if ((rect[cur].g_value + 10) < rect[pos].g_value) 
                    { 
                        rect[pos].pre = &rect[cur]; 
                        rect[pos].g_value = get_g_value(pos); 
                    } 
                } 
            } 
        } 
    } 
    return false; 
} 
 
bool AStart::Find() 
{ 
    //遍歷open_list，查找F值最小的節點作為當前要處理的節點 
    //如果open_list為空，則表明沒有解決方案 
    if (open_list.empty()) 
    { 
        return false; 
    } 
 
    int f_value = 0; 
    int min_f_value = -1; 
    std::list<int>::iterator iter, save; 
    for (iter = open_list.begin(); iter != open_list.end(); iter++) 
    { 
        f_value = rect[*iter].g_value + rect[*iter].h_value; 
        //這裡的min==f也會重新給它賦值，導致open_list中靠後的元素具有更高的優先級 
        //不過無關緊要 
        if ((min_f_value == -1) || (min_f_value >= f_value)) 
        { 
            min_f_value = f_value; 
            save = iter; 
        } 
    } 
 
    //把這個F值最小的節點移到close_list中 
    int cur = *save; 
    close_list.push_back(cur); 
    open_list.erase(save); 
 
 
    //對當前方格的上下左右相鄰方格進行測試 
    //如果終點進入了open_list則結束 
    int up    = cur - Width; 
    int down  = cur + Width; 
    int left  = cur - 1; 
    int right = cur + 1; 
    if (true == testRoad(up, cur)) 
    { 
        return true; 
    } 
    if (true == testRoad(down, cur)) 
    { 
        return true; 
    } 
    if (true == testRoad(left, cur)) 
    { 
        return true; 
    } 
    if (true == testRoad(right, cur)) 
    { 
        return true; 
    } 
     
    return Find(); 
} 

當然，在附件裡有測試例子。自己跑著玩吧，少年。。。

最後忘了提一句了，就在我以為A*很牛的時候，我看到另一個人的文章。。。http://qinysong.iteye.com/blog/678941

這家伙擺明了是惡心我的。。。我剛寫完A*他就來個B*，不過我覺得他寫的很有道理，如果你看到了我這篇文章的末尾，你就會發現這個B*，哈哈。。算不算一個彩蛋呢？好吧。我又2了。。。等下次我寫這幾個算法的對比的時候我一定要仔細研究下這個B*，爭取也把它拿來實現下。。。。

本文出自 “菜鳥浮出水” 博客，請務必保留此出處http://rangercyh.blog.51cto.com/1444712/792044