在復雜的 3D 游戲環境中如何能使非玩家控制角色準確實作自動尋路功能成為了 3D 游戲開 發技術中一大研究熱點，其中 A*演算法得到了大量的運用，A*演算法較之傳統的路徑規劃演算法,實時性更高、靈活性更強,尋路 結果更加接近人工選擇的路徑結果. A*尋路演算法并不是找到最優路徑，只是找到相對近的路徑，因為找最優要把所有可行 路徑都找出來進行對比，消耗性能太大，尋路效果只要相對近路徑就行了，
1.A* 演算法的原理（如顯示不全 重繪重試）
我們假設在推箱子游戲中人要從站里的地方移動到右側的箱子目的地，但是這兩點之間被一堵墻隔開，
我們下一步要做的便是查找最短路徑，既然是 AI 演算法， A* 演算法和人尋找路徑的做法十分類似，當我們離目標較遠時，我 們的目標方向是朝向目的點直線移動，但是在近距離上因為各種障礙需要繞行（走彎路）！而且已走過的地方就無須再次 嘗試，
為了簡化問題，我們把要搜尋的區域劃分成了正方形的格子，這是尋路的第一步，簡化搜索區域，就像推箱子游戲一樣， 這樣就把我們的搜索區域簡化為了 2 維陣列，陣列的每一項代表一個格子，它的狀態就是可走 (walkalbe) 和不可走 (unwalkable) ，通過計算出從起點到終點需要走過哪些方格，就找到了路徑，一旦路徑找到了，人物便從一個方格的中心 移動到另一個方格的中心，直至到達目的地，
簡化搜索區域以后，如何定義小人當前走要走的格子離終點是近是遠呢？我們需要兩個指標來表示：
- G 表示從起點移動到網格上指定方格的移動距離 (暫時不考慮沿斜向移動，只考慮上下左右移動)，
- H 表示從指定的方格移動到終點的預計移動距離，只計算直線距離 (H 有很多計算方法, 這里我們設定只可以上 下左右移動，即該點與終點的直線距離)，
令 F = G + H ，F 即表示從起點經過此點預計到終點的總移動距離接下來我們從起點開始，按照以下尋路步驟，直至找到目標，
2.尋路步驟
1. 從起點開始, 把它作為待處理的方格存入一個預測可達的節點串列，簡稱 openList, 即把起點放入“預測可達節點串列”， 可達節點串列 openList 就是一個等待檢查方格的串列，
2. 尋找 openList 中 F 值最小的點 min（一開始只有起點）周圍可以到達的方格（可到達的意思是其不是障礙物，也不存 在關閉串列中的方格,即不是已走過的方格），計算 min 周圍可到達的方格的 F 值，將還沒在 openList 中點放入其中, 并 設定它們的"父方格"為點 min,表示他們的上一步是經過 min 到達的，如果 min 下一步某個可到達的方格已經在 openList 串列那么并且經 min 點它的 F 值更優,則修改 F 值并把其"父方格"設為點 min，
3. 把 2 中的點 min 從"開啟串列"中洗掉并存入"關閉串列"closeList 中, closeList 中存放的都是不需要再次檢查的方格，如 果 2 中點 min 不是終點并且開啟串列的數量大于零，那么繼續從第 2 步開始，如果是終點執行第 4 步，如果 openList 列 表數量為零，那么就是找不到有效路徑，
4.如果第 3 步中 min 是終點，則結束查找，直接追溯父節點到起點的路徑即為所選路徑
具體尋路步步驟如下所示：
3.演算法實作
Astar.h
1 #pragma once 2 3 #include <list> 4 5 const int kCost1 = 10; //直移一格消耗 6 const int kCost2 = 14; //斜移一格消耗 7 8 typedef struct _Point 9 { 10 int x,y; //點坐標，這里為了方便按照 C++的陣列來計算，x 代表橫排，y 代表豎列 11 int F,G,H; //F=G+H 12 struct _Point *parent; //parent 的坐標 13 }Point; 14 15 /*分配一個節點(格子)*/ 16 Point* AllocPoint(int x, int y); 17 18 /*初始化地圖*/ 19 void InitAstarMaze(int *_maze, int _lines, int _colums); 20 21 /*通過 A* 演算法尋找路徑*/ 22 std::list<Point *> GetPath(Point *startPoint, Point *endPoint); 23 24 /*清理資源，結束后必須呼叫*/ 25 void ClearAstarMaze();
Astar.cpp
1 #include <math.h> 2 #include "Astar.h" 3 #include <iostream> 4 #include <vector> 5 6 static int *maze; //迷宮對應的二維陣列，使用一級指標表示 7 static int cols; //二維陣列對應的列數 8 static int lines; //二維陣列對應的行數 9 static std::list<Point *> openList; //開放串列 10 static std::list<Point *> closeList; //關閉串列 11 12 /*搜索從起點到終點的最佳路徑*/ 13 static Point* findPath(Point *startPoint,Point *endPoint) ; 14 /*從開啟串列中回傳 F 值最小的節點*/ 15 static Point *getLeastFpoint(); 16 /*獲取當前點周圍可達的節點*/ 17 static std::vector<Point *> getSurroundPoints(const Point *point); 18 /*判斷某點是否可以用于下一步判斷 */ 19 static bool isCanreach(const Point *point,const Point *target); 20 /*判斷開放/關閉串列中是否包含某點*/ 21 static Point *isInList(const std::list<Point *> &list,const Point *point); 22 //計算 FGH 值 23 static int calcG(Point *temp_start,Point *point); 24 static int calcH(Point *point,Point *end); 25 static int calcF(Point *point); 26 27 /*分配一個節點(格子)*/ 28 Point* AllocPoint(int x, int y) 29 { 30 Point *temp = new Point; 31 memset(temp, 0, sizeof(Point)); //初始值清零 32 temp->x = x; 33 temp->y = y; 34 return temp; 35 } 36 37 /*初始化 A*搜索的地圖*/ 38 void InitAstarMaze(int *_maze, int _lines, int _colums) 39 { 40 maze = _maze; 41 lines = _lines; 42 cols = _colums; 43 } 44 45 /*通過 A* 演算法尋找路徑*/ 46 std::list<Point *> GetPath(Point *startPoint, Point *endPoint) 47 { 48 Point *result=findPath(startPoint, endPoint); 49 std::list<Point *> path; 50 51 //回傳路徑，如果沒找到路徑，回傳空鏈表 52 while(result) 53 { 54 path.push_front(result); 55 result=result->parent; 56 } 57 return path; 58 } 59 60 /*搜索從起點到終點的最佳路徑*/ 61 static Point* findPath(Point *startPoint,Point *endPoint) 62 { 63 openList.push_back(AllocPoint(startPoint->x, startPoint->y)); //置入起點,拷貝開辟一個節點，內外隔離 64 while(!openList.empty()) 65 { 66 //第一步，從開放串列中取最小 F 的節點 67 Point *curPoint = getLeastFpoint(); //找到 F 值最小的點 68 69 //第二步，把當前節點放到關閉串列中 70 openList.remove(curPoint); 71 closeList.push_back(curPoint); 72 73 //第三步，找到當前節點周圍可達的節點，并計算 F 值 74 std::vector<Point *> surroundPoints = getSurroundPoints(curPoint); 75 std::vector<Point *>::const_iterator iter; 76 77 for(iter=surroundPoints.begin();iter!=surroundPoints.end(); iter++) 78 { 79 Point *target = *iter; 80 81 //對某一個格子，如果它不在開放串列中，加入到開啟串列，設定當前格為其父節點，計算 F G H 82 Point *exist = isInList(openList, target); 83 if(!exist) 84 { 85 target->parent=curPoint; 86 target->G=calcG(curPoint,target); 87 target->H=calcH(target,endPoint); 88 target->F=calcF(target); 89 openList.push_back(target); 90 } 91 else 92 { 93 int tempG = calcG(curPoint, target); 94 if(tempG<target->G) 95 { 96 exist->parent = curPoint; 97 exist->G=tempG; 98 exist->F=calcF(target); 99 } 100 delete target; 101 } 102 }//end for 103 104 surroundPoints.clear(); 105 Point *resPoint = isInList(openList, endPoint); 106 if(resPoint) 107 { 108 return resPoint; 109 } 110 } 111 return NULL; 112 } 113 114 /*從開啟串列中回傳 F 值最小的節點*/ 115 static Point *getLeastFpoint() 116 { 117 if(!openList.empty()) 118 { 119 Point *resPoint = openList.front(); 120 std::list<Point*>::const_iterator itor; 121 122 for(itor = openList.begin(); itor!= openList.end(); itor++) 123 { 124 if((*itor)->F < resPoint->F) 125 { 126 resPoint = *itor; 127 } 128 } 129 return resPoint; 130 } 131 return NULL; 132 } 133 134 /*獲取當前點周圍可達的節點*/ 135 static std::vector<Point *> getSurroundPoints(const Point *point) 136 { 137 std::vector<Point *> surroundPoints; 138 for(int x=point->x-1; x<=point->x+1; x++) 139 { 140 for(int y=point->y-1; y<=point->y+1; y++) 141 { 142 Point *temp = AllocPoint(x, y); 143 if(isCanreach(point, temp)) 144 { 145 surroundPoints.push_back(temp); 146 } 147 else 148 { 149 delete temp; 150 } 151 } 152 } 153 return surroundPoints; 154 } 155 156 /*判斷某點是否可以用于下一步判斷 */ 157 static bool isCanreach(const Point *point,const Point *target) 158 { 159 if(target->x<0||target->x>(lines-1) 160 ||target->y<0||target->y>(cols-1) 161 ||maze[target->x *cols + target->y]==1 162 ||maze[target->x *cols + target->y]==2 163 ||(target->x==point->x && target->y==point->y) 164 ||isInList(closeList, target)) 165 { 166 return false; 167 } 168 if(abs(point->x-target->x)+abs(point->y-target->y)==1) 169 { 170 return true; 171 } 172 else 173 { 174 return false; 175 } 176 } 177 static Point* isInList(const std::list<Point *> &list,const Point *point) 178 { 179 //判斷某個節點是否在串列中，這里不能比較指標，因為每次加入串列是新開辟的節點，只能比較坐標 180 std::list<Point *>::const_iterator itor; 181 for(itor = list.begin(); itor!=list.end();itor++) 182 { 183 if((*itor)->x==point->x&&(*itor)->y==point->y) 184 { 185 return *itor; 186 } 187 } 188 return NULL; 189 } 190 191 /*計算節點的 G 值*/ 192 static int calcG(Point *temp_start, Point *point) 193 { 194 int extraG=(abs(point->x-temp_start->x)+abs(point->y-temp_start->y))==1?kCost1:kCost2; 195 196 //如果是初始節點，則其父節點是空 197 int parentG=(point->parent==NULL? NULL:point->parent->G); 198 199 return parentG+extraG; 200 } 201 202 static int calcH(Point *point,Point *end) 203 { 204 //用簡單的歐幾里得距離計算 H，可以用多中方式實作 205 return (int)sqrt((double)(end->x-point->x)* 206 (double)(end->x-point->x)+(double)(end->y-point->y)* 207 (double)(end->y-point->y))*kCost1; 208 } 209 210 /*計算節點的 F 值*/ 211 static int calcF(Point *point) 212 { 213 return point->G+ point->H; 214 } 215 216 /*清理資源，結束后必須呼叫*/ 217 void ClearAstarMaze() 218 { 219 maze = NULL; 220 lines = 0; 221 cols = 0; 222 std::list<Point *>::iterator itor; 223 224 //清除 openList 中的元素 225 for(itor = openList.begin(); itor!=openList.end();) 226 { 227 delete *itor; 228 itor = openList.erase(itor);//獲取到下一個節點 229 } 230 231 //清理 closeList 中的元素 232 for(itor = closeList.begin(); itor!=closeList.end();) 233 { 234 delete *itor; 235 itor = closeList.erase(itor); 236 } 237 }
main.cpp
1 #include "Astar.h" 2 #include <list> 3 #include <iostream> 4 #include <windows.h> 5 6 using namespace std; 7 8 //定義地圖陣列,二維陣列在記憶體順序存盤的 9 int map[13][13] = { 10 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }, 11 { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, }, 12 { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, }, 13 { 0, 1, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 0, }, 14 { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, }, 15 { 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, }, 16 { 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, }, 17 { 2, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 2, }, 18 { 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, }, 19 { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, }, 20 { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, }, 21 { 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, }, 22 { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, } 23 }; 24 25 void AStarTest() 26 { 27 InitAstarMaze(&map[0][0], 13, 13); 28 29 //設定起始和結束點 30 Point* start = AllocPoint(12, 4); 31 Point* end = AllocPoint(0, 0); 32 33 //A*演算法找尋路徑 34 list<Point *> path = GetPath(start, end); 35 cout<<"尋路結果:"<<endl; 36 list<Point *>::const_iterator iter; 37 38 for(iter=path.begin(); iter!=path.end(); iter++) 39 { 40 Point *cur = *iter; 41 cout<<'('<<cur->x<<','<<cur->y<<')'<<endl; 42 Sleep(800); 43 } 44 45 ClearAstarMaze(); 46 } 47 48 int main(void) 49 { 50 AStarTest(); 51 system("pause"); 52 return 0; 53 }
============================================================================================================
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/233834.html
標籤：其他