AI自動尋路AStar算法
背景
AI自動尋路的算法可以分為以下幾種：
1、A*算法：A*算法是一種啟發(fā)式搜索算法，它利用啟發(fā)函數(shù)（heuristic function）來評估節(jié)點的估價函數(shù)（estimated cost function），從而尋找最短路徑。A*算法綜合考慮了節(jié)點的實際代價和到目標(biāo)節(jié)點的預(yù)計代價，因此能夠快速而準(zhǔn)確地尋找最短路徑【不一定最短，A*算法并不一定能夠找到最短路徑，但它通常可以找到接近最短路徑的解決方案。】
2、Dijkstra算法：Dijkstra算法是一種貪心算法，它從起點開始，每次選擇當(dāng)前代價最小的節(jié)點作為下一個節(jié)點。通過不斷更新節(jié)點的代價，最終可以找到起點到終點的最短路徑。
3、Bellman-Ford算法：Bellman-Ford算法是一種動態(tài)規(guī)劃算法，它通過不斷更新節(jié)點的代價，直到收斂到最短路徑。相比于Dijkstra算法，Bellman-Ford算法能夠處理負(fù)權(quán)邊的情況。
4、Floyd-Warshall算法：Floyd-Warshall算法是一種動態(tài)規(guī)劃算法，它能夠計算出圖中任意兩點之間的最短路徑。Floyd-Warshall算法通過不斷更新節(jié)點之間的代價，直到收斂到最短路徑。
這些算法都可以用于AI自動尋路，具體選擇哪種算法需要根據(jù)具體的應(yīng)用場景和性能要求進(jìn)行選擇。
隨著 3D 游戲的日趨流行,在復(fù)雜的 3D 游戲環(huán)境中如何能使非玩家控制角色準(zhǔn)確實現(xiàn)自動尋路功能成為了 3D 游戲開
發(fā)技術(shù)中一大研究熱點。其中 A*算法得到了大量的運(yùn)用，A*算法較之傳統(tǒng)的路徑規(guī)劃算法,實時性更高、靈活性更強(qiáng),尋路
結(jié)果更加接近人工選擇的路徑結(jié)果. A*尋路算法并不是找到最優(yōu)路徑，只是找到相對近的路徑，因為找最優(yōu)要把所有可行
路徑都找出來進(jìn)行對比，消耗性能太大，尋路效果只要相對近路徑就行了。
所以對于自動尋路，A*算法是一個很不錯的選擇?。?！
AStar算法原理
我們假設(shè)在推箱子游戲中人要從站里的地方移動到右側(cè)的箱子目的地，但是這兩點之間被一堵墻隔開。
我們下一步要做的便是查找最短路徑。既然是 AI 算法， A* 算法和人尋找路徑的做法十分類似，當(dāng)我們離目標(biāo)較遠(yuǎn)時，我
們的目標(biāo)方向是朝向目的點直線移動，但是在近距離上因為各種障礙需要繞行（走彎路）！而且已走過的地方就無須再次
嘗試。
為了簡化問題，我們把要搜尋的區(qū)域劃分成了正方形的格子。這是尋路的第一步，簡化搜索區(qū)域，就像推箱子游戲一樣。
這樣就把我們的搜索區(qū)域簡化為了 2 維數(shù)組。數(shù)組的每一項代表一個格子，它的狀態(tài)就是可走 (walkalbe) 和不可走
(unwalkable) 。通過計算出從起點到終點需要走過哪些方格，就找到了路徑。一旦路徑找到了，人物便從一個方格的中心
移動到另一個方格的中心，直至到達(dá)目的地。
簡化搜索區(qū)域以后，如何定義小人當(dāng)前走要走的格子離終點是近是遠(yuǎn)呢？我們需要兩個指標(biāo)來表示：
1、 G 表示從起點移動到網(wǎng)格上指定方格的移動距離 (暫時不考慮沿斜向移動，只考慮上下左右移動)。
2、 H 表示從指定的方格移動到終點的預(yù)計移動距離，只計算直線距離 (H 有很多計算方法, 這里我們設(shè)定只可以上
下左右移動，即該點與終點的直線距離)。
令 F = G + H ，F(xiàn) 即表示從起點經(jīng)過此點預(yù)計到終點的總移動距離
AStar尋路步驟
1、從起點開始, 把它作為待處理的方格存入一個預(yù)測可達(dá)的節(jié)點列表，簡稱 openList, 即把起點放入“預(yù)測可達(dá)節(jié)點列表”，可達(dá)節(jié)點列表 openList 就是一個等待檢查方格的列表。
2、尋找 openList 中 F 值最小的點 min（一開始只有起點）周圍可以到達(dá)的方格（可到達(dá)的意思是其不是障礙物，也不存在關(guān)閉列表中的方格,即不是已走過的方格）。計算 min 周圍可到達(dá)的方格的 F 值。將還沒在 openList 中點放入其中, 并設(shè)置它們的"父方格"為點 min,表示他們的上一步是經(jīng)過 min 到達(dá)的。如果 min 下一步某個可到達(dá)的方格已經(jīng)在 openList列表那么并且經(jīng) min 點它的 F 值更優(yōu),則修改 F 值并把其"父方格"設(shè)為點 min。
3、把 2 中的點 min 從"開啟列表"中刪除并存入"關(guān)閉列表"closeList 中【當(dāng)自己對四周擴(kuò)散時，將自己放入到closeList中】, closeList 中存放的都是不需要再次檢查的方格。如果 2 中點 min 不是終點并且開啟列表的數(shù)量大于零，那么繼續(xù)從第 2 步開始。如果是終點執(zhí)行第 4 步，如果 openList 列表數(shù)量為零，那么就是找不到有效路徑。
4、如果第 3 步中 min 是終點，則結(jié)束查找，直接追溯父節(jié)點到起點的路徑即為所選路徑。
AStar具體尋路過程
最后通過父子關(guān)系將一條起點到終點的路徑完整的描述出來
AStar代碼實現(xiàn)
Astar.h
#pragma once
#include<list>//鏈表
#include<vector>
const int k_Cost1 = 10;//走一格消耗10
const int k_Cost2 = 14;//斜移走一個消耗14
typedef struct _Point {
int x, y; //x為行，y為列
int F, G, H; //F=G+H;
struct _Point* parent; //父節(jié)點的坐標(biāo)
}Point;
//分配一個節(jié)點
Point* AllocPoint(int x, int y);
//初始化地圖，地圖，行，列
void InitAstarMaze(int* _maze, int _line, int _colums);
//通過A*算法尋找路徑
std::list<Point*>GetPath(const Point* startPoint, const Point* endPoint);
//查找路徑的小方法,返回一個終點，根據(jù)終點可以回溯到起點
static Point* findPath(const Point* startPoint, const Point* endPoint);//用static是為了只能在函數(shù)內(nèi)部調(diào)用而不能單獨(dú)的使用
//返回開放列表中F的最小值的點
static Point* getLeastFPoint();
//獲取周圍的節(jié)點
static std::vector<Point*> getSurroundPoint(const Point* point);
//某個點是否可達(dá)
static bool isCanreach(const Point* point, const Point* target);
//是否存在某個list中，這里用作是否存在closeList/openList中
static Point* isInList(const std::list<Point*>& list, const Point* point);
//獲取G，H，F(xiàn)
static int caloG(const Point* temp_start, const Point* point);
static int caloH(const Point* point, const Point* end);
static int caloF(const Point* point);
//清理資源
void clearAstarMaze();
Astar.cpp
#include"Astar.h"
#include<cmath>
#include<iostream>
#include<vector>
//extern int k_Cost1;
//extern int k_Cost2;
static int* maze;//初始化迷宮
static int cols;//二維數(shù)組對應(yīng)的列
static int lines;//二維數(shù)組對應(yīng)的行
static std::list<Point*>openList; //開放列表
static std::list<Point*>closeList; //關(guān)閉列表
/*初始化地圖*/
void InitAstarMaze(int* _maze, int _line, int colums) {//一級指針保存二維數(shù)組
maze = _maze;
lines = _line;
cols = colums;
}
/*分配節(jié)點*/
Point* AllocPoint(int x, int y) {
Point* temp = new Point;
memset(temp, 0, sizeof(Point));//清理養(yǎng)成好習(xí)慣
temp->x = x;
temp->y = y;
return temp;
}
/*通過A*算法尋找路徑*/
std::list<Point*>GetPath(const Point* startPoint, const Point* endPoint) {
Point *result = findPath(startPoint, endPoint);
std::list<Point*>path;
//返回路徑
while (result) {
path.push_front(result);//這樣起點就是在這個鏈表的最前面了
result = result->parent;
}
return path;
}
/*查找路徑的小方法,返回一個終點，根據(jù)終點可以回溯到起點*/
static Point* findPath(const Point* startPoint, const Point* endPoint) {
openList.push_back(AllocPoint(startPoint->x, startPoint->y));//重新分配更加的安全，置入起點
while (!openList.empty()) {
//1、獲取開放表中最小的F值
Point* curPoint = getLeastFPoint();
//2、把當(dāng)前節(jié)點放到closeList中
openList.remove(curPoint);
closeList.push_back(curPoint);
//3、找到當(dāng)前節(jié)點周圍可到達(dá)的節(jié)點并計算F值
std::vector<Point*> surroundPoints = getSurroundPoint(curPoint);
std::vector<Point*>::const_iterator iter;
for (iter = surroundPoints.begin(); iter != surroundPoints.end(); iter++) {
Point* target = *iter;
//如果沒在開放列表中就加入到開放列表，設(shè)置當(dāng)前節(jié)點為父節(jié)點
Point* exist = isInList(openList, target);
if (!exist) {
target->parent = curPoint;
target->G = caloG(curPoint, target);//父節(jié)點的G加上某個數(shù)就好（自己設(shè)計的）
target->H = caloH(target, endPoint);
target->F = caloF(target);
openList.push_back(target);
}
else {//如果已存在就重新計算G值看要不要替代
int tempG = caloG(curPoint, target);
if (tempG < target->G) {//更新
exist->parent = curPoint;
exist->G = tempG;
exist->F = caloF(target);
}
delete *iter;
}
}//end for循環(huán)
surroundPoints.clear();
Point* resPoint = isInList(openList, endPoint);//終點是否在openList上
if (resPoint) {
return resPoint;
}
}
return NULL;
}
//返回開放列表中F的最小值的點
static Point* getLeastFPoint() {
//遍歷
if (!openList.empty()) {
Point* resPoint = openList.front();
std::list<Point*>::const_iterator itor;//定義迭代器，用于遍歷鏈表
//迭代器遍歷，C++特性,直接理解成平時我們用的for
for (itor = openList.begin(); itor != openList.end(); itor++) {
Point* p = *itor;//把元素拿出來
if (p->F < resPoint->F) {
resPoint = p;
}
}
return resPoint;
}
return NULL;
}
/*獲取周圍的節(jié)點*/
static std::vector<Point*> getSurroundPoint(const Point* point) {
std::vector<Point*>surroundPoints;
//周圍九個點都會進(jìn)行檢測
for (int x = point->x - 1; x <= point->x + 1; x++) {
for (int y = point->y - 1; y <= point->y + 1; y++) {
Point* temp = AllocPoint(x, y);
if (isCanreach(point, temp)) {
surroundPoints.push_back(temp);
}
else {
delete temp;
}
}
}
return surroundPoints;
}
/*某個點是否可達(dá)*/
static bool isCanreach(const Point* point, const Point* target) {
if (target->x<0 || target->x>(lines - 1)
|| target->y<0 || target->y>(cols - 1)
|| (maze[target->x * cols + target->y] == 1)//找到對應(yīng)的二維數(shù)組中的位置-》障礙物
|| (maze[target->x * cols + target->y] == 2)
|| (target->x == point->x && target->y == point->y)
|| isInList(closeList, target)) {
return false;
}
if (abs(point->x - target->x) + abs(point->y - target->y) == 1) {//我們現(xiàn)在只考慮上下左右4個點
return true;
}
else {
return false;
}
}
/*是否存在某個list中，這里用作是否存在closeList/openList中*/
static Point* isInList(const std::list<Point*>& list, const Point* point) {
std::list<Point*>::const_iterator itor;
for (itor = list.begin(); itor != list.end(); itor++) {
if ((*itor)->x == point->x && (*itor)->y == point->y) {
return *itor; //存在返回該節(jié)點
}
}
return NULL;
}
static int caloG(const Point* temp_start, const Point* point) {
int extraG = (abs(point->x - temp_start->x) + abs(point->y - temp_start->y)) == 1 ? k_Cost1 : k_Cost2;//周圍的點與擴(kuò)散點的差值,是否為斜邊
int parentG = (point->parent == NULL ? NULL : point->parent->G);//如果是初始值為null，其他的點是父類的G值
return parentG + extraG;//返回兩個量相加
}
static int caloH(const Point* point, const Point* end) {
//歐幾里得求斜邊
return (int)sqrt((double)(end->x - point->x) * (double)(end->x - point->x)) + (double)(end->y - point->y) * (double)(end->y - point->y) * k_Cost1;
}
static int caloF(const Point* point) {
return point->G + point->H;
}
/*清理資源*/
void clearAstarMaze() {
maze = NULL;
lines = 0;
cols = 0;
std::list<Point*>::iterator itor;
for (itor = openList.begin(); itor != openList.end();) {
delete* itor;
itor = openList.erase(itor);//獲取到下一個節(jié)點
}
for (itor = closeList.begin(); itor != closeList.end();) {
delete* itor;
itor = closeList.erase(itor);//獲取到下一個節(jié)點
}
}
main.cpp文章來源：http://www.zghlxwxcb.cn/news/detail-418453.html
#include<iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <windows.h>
#include"Astar.h"
using namespace std;
int map[13][13] = {
{0,0,0,0,0,0,0,0,0,0,0,0,0},
{0,1,0,1,0,1,0,1,0,1,0,1,0},
{0,1,0,1,0,1,0,1,0,1,0,1,0},
{0,1,0,1,0,1,2,1,0,1,0,1,0},
{0,1,0,1,0,1,0,1,0,1,0,1,0},
{0,1,0,1,0,0,0,1,0,1,0,1,0},
{0,0,0,0,0,1,0,1,0,0,0,0,0},
{2,0,1,1,0,0,0,1,0,1,0,0,2},
{0,0,0,0,0,1,1,1,0,0,0,0,0},
{0,1,0,1,0,1,0,1,0,1,0,1,0},
{0,1,0,1,0,1,0,1,0,1,0,1,0},
{0,1,0,1,0,0,0,0,0,1,0,1,0},
{0,0,0,0,0,1,3,1,0,0,0,0,0}
};
void astarTest() {
InitAstarMaze(&map[0][0], 13, 13);
//設(shè)置
Point* start = AllocPoint(12, 4);
Point* end = AllocPoint(0, 12);
//尋找路徑
list<Point*>path = GetPath(start, end);
//設(shè)置迭代器遍歷
list<Point*>::const_iterator iter;//迭代器
cout << "(" << start->x << "," << start->y << ")" << "------>(" << end->x << "," << end->y << ")" << endl;
cout << "****************** 尋路結(jié)果 ********************************" << endl;
for (iter = path.begin(); iter != path.end(); ) {
Point* cur = *iter;
cout << '(' << cur->x << "," << cur->y << ')' << endl;
//delete cur;//不用再進(jìn)行釋放了因為在openList和closeList鏈表中我們最后都有清理，如果再清理就會報錯
iter = path.erase(iter);
Sleep(800); //休眠
}
clearAstarMaze();
}
int main() {
astarTest();
system("pause");
return 0;
}
運(yùn)行結(jié)果
文章來源地址http://www.zghlxwxcb.cn/news/detail-418453.html
到了這里，關(guān)于AI自動尋路AStar算法【圖示講解原理】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
