程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> A*算法的簡單實現

A*算法的簡單實現

編輯:關於C語言

前幾天導師布置了個任務,讓做一個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

  1. ////////////////////////////////////////////////////////////////////////////////////// 
  2. // 
  3. //  FileName    :   A.h 
  4. //  Version     :   1.0 
  5. //  Creater     :   Ranger Cai 
  6. //  Date        :   2012-2-27 09:44:49 
  7. //  Comment     :   A* algorithm header file 
  8. // 
  9. ////////////////////////////////////////////////////////////////////////////////////// 
  10. #ifndef _A_FINDPATH_H 
  11. #define _A_FINDPATH_H 
  12.  
  13. #include <list> 
  14. #include <algorithm> 
  15.  
  16. //記錄地圖上每個節點的位置信息以及估值信息的結構體堆棧 
  17. typedef struct _Rect 
  18.     int x; 
  19.     int y; 
  20.     int h_value;  //h值為節點到終點的Manhattan距離 
  21.     int g_value;  //g值為起點到該點的移動代價 
  22.     struct _Rect *pre;  //指向父節點 
  23. }Rect; 
  24.  
  25. class AStart 
  26. public: 
  27.     //初始化傳入地圖二維數組、地圖寬、長,起始及終點在數組中的序號 
  28.     AStart(int *mapInfo, int width, int height, int start, int end); 
  29.     ~AStart(); 
  30.  
  31.     //A*查找,查找成功返回true,否則返回false 
  32.     bool Find(); 
  33.     //如果Find()函數成功,則可以調用此函數把結果路徑存入到result中 
  34.     void getResultPath(); 
  35.      
  36.     //計算pos節點的g值 
  37.     int get_g_value(int pos); 
  38.     //計算pos節點的h值 
  39.     int get_h_value(int pos); 
  40.     //判斷pos節點是否在地圖內 
  41.     bool isReachable(int pos); 
  42.     //測試節點是否更好並判斷是否已經找到路徑 
  43.     bool testRoad(int pos, int cur); 
  44.  
  45.     int  *map;  //地圖信息 
  46.     Rect *rect; //父子節點關系鏈 
  47.     std::list<Rect> result;  //查找成功後的結果路徑保存在此 
  48.  
  49. private: 
  50.     int Width; 
  51.     int Height; 
  52.     int Start; 
  53.     int End; 
  54.  
  55.     std::list<int> open_list;   //open表中的節點為待檢查的節點 
  56.     std::list<int> close_list;  //close表中的節點為暫時不關注的節點 
  57. }; 
  58.  
  59. #endif //_A_FINDPATH_H 

然後是實現A.cpp

 

  1. #include "stdafx.h" 
  2. #include "A.h" 
  3.  
  4.  
  5. AStart::AStart(int *mapInfo, int width, int height, int start, int end) 
  6.     Width  = width; 
  7.     Height = height; 
  8.     Start  = start; 
  9.     End    = end; 
  10.  
  11.     //把二維數組保存到一維數組中去,便於信息的處理 
  12.     map = new int[Width * Height]; 
  13.     for (int i = 0; i < Width * Height; i++) 
  14.     { 
  15.         //map[i] = mapInfo[i / width][i % width]; 
  16.         map[i] = mapInfo[i]; 
  17.     } 
  18.  
  19.     //記錄每一個節點的位置信息 
  20.     rect = new Rect[Width * Height]; 
  21.     for (int i = 0; i < (Width * Height); i++) 
  22.     { 
  23.         rect[i].x = i % Width; 
  24.         rect[i].y = i / Width; 
  25.     } 
  26.  
  27.     //初始化起點 
  28.     rect[Start].g_value = 0; 
  29.     rect[Start].h_value = get_h_value(Start); 
  30.     rect[Start].pre = NULL; 
  31.  
  32.     //把起點加入open_list中 
  33.     open_list.push_back(Start); 
  34.  
  35. AStart::~AStart() 
  36.     if (map != NULL) 
  37.     { 
  38.         delete[] map; 
  39.     } 
  40.     if (rect != NULL) 
  41.     { 
  42.         delete[] rect; 
  43.     } 
  44.  
  45. int AStart::get_g_value(int pos) 
  46.     //只允許玩家往上下左右四個方向行走,所以這裡的g值只需要在父節點的g值上加10 
  47.     return (rect[pos].pre->g_value + 10); 
  48.  
  49. int AStart::get_h_value(int pos) 
  50.     //返回該點到終點的Manhattan距離,乘以10是為了方便計算機計算 
  51.     return (10 * (abs(End / Width - pos / Width) + abs(End % Width - pos % Width))); 
  52.  
  53. void AStart::getResultPath() 
  54.     Rect *temp = &rect[End]; 
  55.     while (temp != NULL) 
  56.     { 
  57.         result.push_back(*temp); 
  58.         temp = temp->pre; 
  59.     } 
  60.     return; 
  61.  
  62. bool AStart::isReachable(int pos) 
  63.     if ((pos / Width < Height) && (pos / Width >= 0) && 
  64.         (pos % Width < Width)  && (pos % Width >= 0)) 
  65.     { 
  66.         return true; 
  67.     } 
  68.     else 
  69.     { 
  70.         return false; 
  71.     } 
  72.  
  73. //如果pos不可達或者它在close_list中則跳過它,否則,進行如下操作 
  74. //如果pos不在open_list中則加入open_list,並把當前方格設置為它的父親 
  75. //如果pos在open_list中則檢查g的大小,如果更小則把它的父親設置為當前方格 
  76. bool AStart::testRoad(int pos, int cur) 
  77.     if (isReachable(pos)) 
  78.     { 
  79.         if (pos == End) 
  80.         { 
  81.             rect[pos].pre = &rect[cur]; 
  82.             return true; 
  83.         } 
  84.         if (map[pos] != 1) //1代表障礙物,0則可通行 
  85.         { 
  86.             if (close_list.end() == find(close_list.begin(), close_list.end(), pos)) 
  87.             { 
  88.                 std::list<int>::iterator iter = find(open_list.begin(), open_list.end(), pos); 
  89.                 if (iter == open_list.end()) 
  90.                 { 
  91.                     open_list.push_back(pos); 
  92.                     rect[pos].pre = &rect[cur]; 
  93.                     rect[pos].h_value = get_h_value(pos); 
  94.                     rect[pos].g_value = get_g_value(pos); 
  95.                 } 
  96.                 else 
  97.                 { 
  98.                     if ((rect[cur].g_value + 10) < rect[pos].g_value) 
  99.                     { 
  100.                         rect[pos].pre = &rect[cur]; 
  101.                         rect[pos].g_value = get_g_value(pos); 
  102.                     } 
  103.                 } 
  104.             } 
  105.         } 
  106.     } 
  107.     return false; 
  108.  
  109. bool AStart::Find() 
  110.     //遍歷open_list,查找F值最小的節點作為當前要處理的節點 
  111.     //如果open_list為空,則表明沒有解決方案 
  112.     if (open_list.empty()) 
  113.     { 
  114.         return false; 
  115.     } 
  116.  
  117.     int f_value = 0; 
  118.     int min_f_value = -1; 
  119.     std::list<int>::iterator iter, save; 
  120.     for (iter = open_list.begin(); iter != open_list.end(); iter++) 
  121.     { 
  122.         f_value = rect[*iter].g_value + rect[*iter].h_value; 
  123.         //這裡的min==f也會重新給它賦值,導致open_list中靠後的元素具有更高的優先級 
  124.         //不過無關緊要 
  125.         if ((min_f_value == -1) || (min_f_value >= f_value)) 
  126.         { 
  127.             min_f_value = f_value; 
  128.             save = iter; 
  129.         } 
  130.     } 
  131.  
  132.     //把這個F值最小的節點移到close_list中 
  133.     int cur = *save; 
  134.     close_list.push_back(cur); 
  135.     open_list.erase(save); 
  136.  
  137.  
  138.     //對當前方格的上下左右相鄰方格進行測試 
  139.     //如果終點進入了open_list則結束 
  140.     int up    = cur - Width; 
  141.     int down  = cur + Width; 
  142.     int left  = cur - 1; 
  143.     int right = cur + 1; 
  144.     if (true == testRoad(up, cur)) 
  145.     { 
  146.         return true; 
  147.     } 
  148.     if (true == testRoad(down, cur)) 
  149.     { 
  150.         return true; 
  151.     } 
  152.     if (true == testRoad(left, cur)) 
  153.     { 
  154.         return true; 
  155.     } 
  156.     if (true == testRoad(right, cur)) 
  157.     { 
  158.         return true; 
  159.     } 
  160.      
  161.     return Find(); 

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

 

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

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

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved