A-Star 演算法 與 STL List問題

ahijup

小弟最近寫的A-star走迷宮配合 STL 的 List以下是我的程式碼 :

mClasses.h

1. /*自定義函式宣告*/
   
2. #include <iostream>
   
3. #include <list>
   
4. #include <math.h>
   
5. #include <algorithm>
   
6. using namespace std;
   
7. enum Direction {
   
8.         Right , Left , UP , Down , RD , LD , LU , RU
   
9. } ;
   
10. enum Way {
    
11.         FourWay = 2 , eightWay = 1
    
12. } ;
    
13. 
    
14. 
    
15. class mPoint {
    
16. public:
    
17.         int x , y ;
    
18.         Direction dir ;
    
19.         double h , f ;
    
20.         mPoint *ParentNode ;
    
21.         bool operator == (mPoint x ) ;
    
22. } ;
    
23. //定義出一個list裡面全部都包含mPoint
    
24. typedef list<mPoint> POINTList ;
    
25. //用list印出元素的函式呼叫
    
26. void print_list( mPoint x ) ;
    
27. //排序的比較方法
    
28. bool Comparer1 ( mPoint x , mPoint y ) ;
    
29. struct mSize {
    
30.         int width , height ;
    
31. } ;
    
32. 
    
33. class AStarSearch {
    
34. private:
    
35.         mSize mapSize ;
    
36.         mPoint startPT , endPT ;
    
37.         unsigned short **map ;
    
38. public :
    
39.         /*        初始化這個類別 ， mapSize -> 這個地圖的大小  , map -> 搜尋的地圖檔        */
    
40.         AStarSearch ( mSize mapSize  , unsigned short **map ) {
    
41.                 this->mapSize = mapSize ;
    
42.                 this->map = map ;
    
43.         } ;
    
44.         /*        開始搜尋路徑 ， startPT -> 起始座標點 , endPT -> 結束點 , isShifted -> 是否把點座標轉換成2維陣列的座標 ,         */
    
45.         mPoint * SearchRoute ( mPoint startPT , mPoint endPT , bool isShifted , Way w );
    
46.         ~AStarSearch() ;
    
47. } ;

複製代碼

mClasses.cpp

1. /*mClasses.h中實作方法*/
   
2. #include "mClasses.h"
   
3. void print_list( mPoint x ) {
   
4.         cout << x.x << " , " << x.y << " " ;
   
5. } ;
   
6. bool Comparer1 ( mPoint x , mPoint y ) {
   
7.         if ( x.h < y.h )
   
8.                 return 1 ;
   
9.         else               
   
10. return 0 ;
    
11. } ;
    
12. 
    
13. 
    
14. bool mPoint::operator == (mPoint x ) {
    
15.         if ( (this->x == x.x) && (this->y == x.y) )
    
16.                 return true ;
    
17.         return false ;
    
18. } ;
    
19. 
    
20. 
    
21. mPoint * AStarSearch::SearchRoute(mPoint startPT , mPoint endPT , bool isShifted , Way w) {
    
22.                 this->startPT = startPT ;
    
23.                 this->endPT = endPT ;
    
24. 
    
25.                 if ( !isShifted ) {
    
26.                         this->startPT.x += (int) (this->mapSize.width / 2) ;
    
27.                         this->startPT.y = (int) (this->mapSize.height / 2) - this->startPT.y ;
    
28.                         this->endPT.x += (int) (this->mapSize.width / 2) - 1 ;
    
29.                         this->endPT.y = (int) (this->mapSize.height / 2) - this->endPT.y - 1 ;
    
30.                 }
    
31. 
    
32.                 if ( this->map[this->startPT.x][this->startPT.y] == 1 ) {
    
33.                         return NULL ;
    
34.                 } else {
    
35.                         this->startPT.f = 0.0 ;
    
36.                         this->startPT.ParentNode = NULL ;
    
37.                         POINTList r  ;
    
38.                         r.push_back( this->startPT ) ;
    
39.                         POINTList closeList ;
    
40.                         while ( !r.empty() ) {
    
41.                                 mPoint * ExtendPoint = &(mPoint) *r.begin( ) ;
    
42.                                 //把最前面的資料pop出來
    
43.                                 //r.pop_front( ) ;
    
44.                                 r.remove( *ExtendPoint) ;
    
45.                                 //cout << "current pt -> " << ExtendPoint.x << " , " << ExtendPoint.y << endl ;
    
46.                                 //如果找到
    
47.                                 if ( *ExtendPoint == this->endPT ) {
    
48.                                                         return ExtendPoint ;
    
49.                                 }
    
50.                                 closeList.push_back(*ExtendPoint) ;
    
51.                                 closeList.sort( Comparer1 ) ;
    
52.                                 //8 - way Search
    
53.                                 mPoint x[8] ;
    
54.                                 x[0].x = (*ExtendPoint).x + 1 ;
    
55. 
    
56.                                 x[0].y = (*ExtendPoint).y ;
    
57.                                 x[0].dir = Direction::Right ;
    
58. 
    
59.                                 x[1].x = (*ExtendPoint).x + 1 ;
    
60.                                 x[1].y = (*ExtendPoint).y + 1 ;
    
61.                                 x[1].dir = Direction::RD ;
    
62.                                 x[2].x = (*ExtendPoint).x  ;
    
63.                                 x[2].y = (*ExtendPoint).y + 1;
    
64.                                 x[2].dir = Direction::Down ;
    
65.                                 x[3].x = (*ExtendPoint).x - 1 ;
    
66.                                 x[3].y = (*ExtendPoint).y + 1 ;
    
67.                                 x[3].dir = Direction::LD ;
    
68. 
    
69.                                 x[4].x = (*ExtendPoint).x - 1 ;
    
70.                                 x[4].y = (*ExtendPoint).y ;
    
71.                                 x[4].dir = Direction::Left ;
    
72.                                 x[5].x = (*ExtendPoint).x - 1 ;
    
73. 
    
74.                                 x[5].y = (*ExtendPoint).y - 1 ;
    
75.                                 x[5].dir = Direction::LU ;
    
76.                                 x[6].x = (*ExtendPoint).x ;
    
77.                                 x[6].y = (*ExtendPoint).y - 1 ;
    
78.                                 x[6].dir = Direction::UP ;
    
79. 
    
80.                                 x[7].x = (*ExtendPoint).x + 1 ;
    
81.                                 x[7].y = (*ExtendPoint).y - 1 ;
    
82.                                 x[7].dir = Direction::RU ;
    
83. 
    
84.                                 for ( int a = 0 ; a < 8 ; a += w ) {
    
85.                                         if ( ( x[a].x >= 0 && x[a].x < this->mapSize.height ) && ( x[a].y >= 0 && x[a].y < this->mapSize.width ) ) {                                                                        if ( !this->map[ x[a].y ][ x[a].x ] && !(x[a] == *ExtendPoint) ) {
    
86.                                                         x[a].f = (*ExtendPoint).f + 1.0 ;
    
87.                                                         x[a].h = x[a].f + sqrt( pow( (double)(endPT.x - x[a].x) , 2 ) + pow( (double)(endPT.y - x[a].y) , 2) ) ;                                                                //x[a].h = x[a].f + abs(endPT.x - x[a].x) + abs(endPT.y - x[a].y) ;
    
88.                                                         //if n' in OPEN list and new n' is not better, continue
    
89.                                                         //POINTList::iterator iter = lower_bound(r.begin() , r.end() , x[a] , Comparer1 ) ;
    
90.                                                         mPoint *tmp = NULL ;
    
91. 
    
92.                                                         POINTList::iterator iter = find(r.begin() , r.end() , x[a] ) ;
    
93. 
    
94.                                                         if ( iter != r.end() ) {
    
95.                                                                         tmp = & (mPoint) *iter ;
    
96.                                                                         if ( tmp->h < x[a].h )
    
97.                                                                                 continue ;
    
98.                                                          }                                                      
    
99.                                                         //if n' in CLOSED list and new n' is not better, continue
    
100.                                                         mPoint *tmp1 = NULL ;
     
101. 
     
102.                                                         iter = find(closeList.begin() , closeList.end() , x[a] ) ;
     
103.                                                         if ( iter != closeList.end() ) {
     
104.                                                                         tmp1 = & (mPoint) *iter ;
     
105.                                                                         if ( tmp1->h < x[a].h )
     
106.                                                                                 continue ;
     
107.                                                         }
     
108.                                                         //remove any n' from OPEN and CLOSED
     
109. 
     
110.                                                         //r.remove(x[a]) ;
     
111.                                                         //closeList.remove( x[a] ) ;
     
112. 
     
113.                                                         //add n as n's parent
     
114.                                                         x[a].ParentNode = ExtendPoint ;
     
115. 
     
116.                                                         //add n' to OPEN
     
117.                                                         if ( tmp != NULL ) {
     
118.                                                                 tmp = &x[a] ;
     
119.                                                         } else {
     
120.                                                                 r.push_back( x[a] ) ;
     
121.                                                         }
     
122.                                                         if ( tmp1 != NULL )
     
123.                                                                 closeList.remove( *tmp1 ) ;
     
124. 
     
125.                                                         r.sort( Comparer1 ) ;
     
126. 
     
127.                                                      }
     
128.                                         }
     
129.                                 }
     
130.                 }
     
131.         return NULL ;
     
132. }
     
133. } ;

複製代碼

main.cpp

1. #include <mClasses.h>
   
2. void main() {
   
3.         int x = 50 , y  = 50 , i ;
   
4.         //動態宣告出2-dim陣列
   
5.         unsigned short **input = new unsigned short* [ x ] ;
   
6. 
   
7.         for ( i = 0 ; i < x ; i ++ )
   
8.                 input[i] = new unsigned short[y] ;
   
9.         mSize size;
   
10. 
    
11.         size.height = x  ;
    
12.         size.width = y ;
    
13. 
    
14.         for ( i = 0 ; i < x ; i++ ) {
    
15.                 for ( int j = 0 ; j < y ; j++ )
    
16.                         input[i][j] = 0 ;
    
17.         }
    
18. 
    
19.         AStarSearch *ass = new AStarSearch( shiftSize , input ) ;
    
20. 
    
21.         mPoint start ;
    
22.         start.x = 0 ;
    
23.         start.y = 0 ;
    
24. 
    
25.         mPoint end ;
    
26.         end.x = 25 ;
    
27.         end.y = 20 ;
    
28. 
    
29.         mPoint *r = ass->SearchRoute( start , end , true , Way::FourWay) ;
    
30. 
    
31.         return;
    
32. }

複製代碼

問題1: 在main.cpp中回傳結果的 *r ， ParentNode 不知道為啥咪會一直指向目標點 ( end ) 。
問題2: 在A-star搜尋路徑的時候，好像有拓展過頭的現象，執行時間會非常的久。

A-star 演算法我是參考 :

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

編譯器 : vc++ 2008...

瀏覽完整內容，請先 註冊 或 登入會員

poorpoorpoor

你每次取節點有使用HEAP之類的優先隊列嗎?
這樣每次取g()+h()的最小值的點只要O(logn)

NTUKing

STL檔案格式有點複雜
我最近也在找相關資料 但完全沒有詳細的資料可以參考 ><