高效尋路算法——A*（A-Star）

在資料結構中我們學過圖，而圖中一個很重要的課題就是與最短路徑、最優路徑相關的尋路問題，包括Dijkstra、深度優先搜尋，都是其中的經典算法；

同時，在遊戲開發中，也常常需要設計合适的尋路算法來實作怪物AI的移動、人物自動尋路等常用功能，在各種算法中，A*無疑是最常用也是最經典的一種，作為進一步了解遊戲尋路機制的基礎，A*的學習很有必要，是以接下來這篇文章會從原理入手，一步步解析算法的過程并且實作它

圖0

經典RPG中人物NPC的移動往往就需要合适的尋路算法，地圖的網格化就是為了實作這點

一、算法介紹

       A*算法是靜态網絡中求解最短路徑時最有效的直接搜尋算法，也是許多算法的啟發式算法。因其簡單高效的特點，常常會用作遊戲中的尋路算法。當然要注意，在直接搜尋算法中它是最有效的，後來也出現了許多預處理算法（如ALT，CH，HL等等），線上查詢效率是A*算法的數千甚至上萬倍。

二、算法原理

        A*算法的本質似乎是一種貪心選擇政策，即走的每一步都是目前狀況下的最優選擇，而A*算法的貪心選擇依據主要是三個值F、H和G和兩個表openList和closeList；首先先來解釋一下它們各自的含義：

        G——從起點到達目前位置點的移動代價/距離，這個值是會不斷累加并更新的；我們将橫向或縱向（即上下左右）移動一格的代價定為10，那麼斜向移動一格的代價可以定為14（即

），使用10作為機關代價是為了避免小數計算。不同的路徑會使得起點到達目前位置的移動代價并不相同，但是我們總是傾向于更小的G值，這是由貪心選擇政策導緻的，後面會看到這一點。

        H——從目前位置到達終點的估計代價/距離，計算估計代價的方法有很多，我們這裡僅讨論一種較為簡單且常用的方法即曼哈頓(Manhattan)距離，曼哈頓距離表示兩個點的絕對軸距總和，如圖1所示。

圖1

       F——目前位置的總代價，也是進行貪心選擇的最終依據，其值為移動代價與估計代價的值的和，即F = G + H。

       openList——開放清單，用于儲存目前可以到達的所有位置節點；我們每次都要從openList中尋找F值最小的節點作為目前節點，然後再将目前節點周圍所有可到達的點加入到openList當中并将目前節點設定為它們的父節點，如果已經在openList當中，則需要判斷從這個點到目前節點的代價是否更小，有必要則進行更新。這樣，當把終點加入到openList中時，就可以回溯父節點找到一條最短路徑；如果到openList為空時，終點仍未添加進去，則說明查找失敗，無法到達終點。

       closeList——關閉清單，用于儲存開放清單中處理完的節點，保證處理過的節點不再處理，通常可以和圖中不可到達的位置記錄在同一個表中。

三、算法過程

1、将起點加入到openList中（每次将點加入到openList當中時，都要計算并儲存它們的F值，後面不再贅述），将所有不可到達的點記錄在closeList當中

2、重複進行下面步驟，直到openList為空或者将終點添加至openList中：

（1）從openList中取出F值最小的節點，将該點作為目前要處理的節點；

（2）周遊該目前點周圍的可到達點（即八個方向且不在closeList中的點），如果這個可到達點不在openList中，直接将其加入進來，并将它的父節點設定為目前點；如果這個可到達點已經在openList當中，那麼需要比較經由這個點到達目前處理點的路徑代價是否會更小（因為H值不變，是以主要目标是比較G值大小），如果代價更小，那麼就改變目前處理點的父節點為這個點，否則不作任何處理，這樣是為了保證到達目前處理點的路徑是最短的；

圖2

例如圖2所示，考察目前處理點周圍的可加入點時，因為其上方的格子已經在openList當中，是以需要比較經由其上方格子到達目前格子的代價是否更小，很明顯

Ga = 10 + 10 = 20;

Gb = 14;

Gb < Ga;

是以比較而言路線b的代價更小，目前待處理格子不需要作任何改變

（3）将該處理點記錄到closeList當中

3、從終點開始，開始沿着父節點周遊至起點，就是利用A*算法所得到的最短路徑

如圖3456，以一個執行個體的形式展現了尋找從起點A到終點B的最短路徑的過程

圖3

一開始openList當中隻有A一個節點，是以取出F值最小的節點也就是A作為目前的待處理節點

圖4

處理節點A，将其周圍所有的可到達節點加入到openList中，因為這些可到達節點一開始都不在openList當中，是以不需要比較G值直接加入并将A設定為他們的父節點，然後取出openList中F值最小等于34的節點即右下角的節點作為下一個待處理節點；這樣節點A處理完畢，将A加入到closeList當中

圖5

處理目前F值等于34的節點，先考察其周圍的節點，節點A因為已經處理完畢置于closeList當中，其右上角和右邊的節點是不可到達節點，是以這些點無需考慮；其下方三個節點并不在openList當中，是以直接将他們加入openList，最後考察剩下兩個點，比較可得經過他們的G值均大于原來的G值，是以它們并非是更優路徑，不作任何改變；如此一來目前F值等于34的這個節點也處理完畢，我們将其加入到closeList當中

圖6

反複重複上面的步驟，最終将B節點加入到openList當中，表示搜尋成功，然後我們從終點B開始，通路它們的父節點，就可以得到一條從A到B的最短路徑啦！即圖中棕色箭頭表示的路徑

四、代碼實作

#define MAX 10
#include<iostream>
#include<math.h>
#include<string.h>
#include<stack>
#include"priorQue.h"

using namespace std;

typedef struct vector2 {
	int x, y;
}vector2;
//定義一個二維向量結構體

typedef struct AStarNode {
	vector2 pos, parent;
	int F, G, H;  //節點的位置和代價

	AStarNode() {}
	AStarNode(int x1, int y1, int x2, int y2) {
		parent = { -1, -1 };  pos = { x1, y1 };
		H = abs(x1 - y1) + abs(x2 - y2);
		G = 0;  F = H;
	}
	//構造函數，用于初始化位置坐标和計算估計代價

	bool operator<(const AStarNode &n)const {
		return this->F < n.F;
	}
	//重載運算符小于号，這樣才能用最小堆進行存儲
}AStarNode;
//A*節點

bool AStar(int visit[][MAX], int x1, int y1, int x2, int y2) //傳入的參數分别是地圖資訊、起點的xy坐标、終點的xy坐标
{
	/*
	visit數組用于記錄圖中點的目前狀态
	如果等于0，代表這個點不可到達或者已經被置入closeList當中，是以visit數組實作了closeList表的功能
	如果等于1，為正常狀态，說明這個點能走通
	如果等于2，說明見目前這個點位于openList當中
	*/

	AStarNode a[MAX][MAX];
	//開一個與圖等大的節點數組
	vector2 around[8] = { {-1, 1}, {0, 1}, {1, 1}, {-1, 0}, {1, 0}, {-1, -1}, {0, -1}, {1, -1} }, tmp = { 0, 0 };
	//around數組表示一個點周圍的八個方向
	AStarNode start(x1, y1, x2, y2), current;
	a[x1][y1] = start;
	//初始化起點和目前待處理的節點
	bool flag = false;
	//記錄終點是否被加入到openList當中
	stack<AStarNode> record;

	priorQue<AStarNode> openList;
	openList.enQueue(start);
	//将openList用優先級隊列來表示，這樣隊列首部第一個節點自然就是F值最小的節點
	//先将起點加入到openList中去

	while (!openList.empty() && !flag) 
	{
		current = openList.deQueue();  //從openList中選出F值最小的作為目前待處理的節點
		for (int i = 0; i < 8; i++) 
		{
			tmp.x = current.pos.x + around[i].x;
			tmp.y = current.pos.y + around[i].y;
			if (tmp.x < 0 || tmp.x > MAX - 1 || tmp.y < 0 || tmp.y > MAX - 1 || visit[tmp.x][tmp.y] == 0) continue;
			//得到目前待處理點周圍的一個點，若這個點超出邊界或者為不可到達點，則跳過不作處理
                        if (around[i].x != 0 && around[i].y != 0 && 
                            visit[current.pos.x + around[i].x][current.pos.y] == 0 && visit[current.pos.x][current.pos.y + around[i].y] == 0) continue;
                        //另外一種情況，即側向雖然可達，但無法直接到達，也應跳過

			if (visit[tmp.x][tmp.y] == 1) {
				//如果visit等于1
				AStarNode n(tmp.x, tmp.y, x2, y2);
				n.parent = current.pos;
				if (abs(around[i].x) + abs(around[i].y) > 1) n.G = current.G + 14;
				else n.G = current.G + 10;
				n.F = n.G + n.H;
				//計算這個點的G值和F值
				openList.enQueue(n);
				a[tmp.x][tmp.y] = n;
				visit[tmp.x][tmp.y] = 2;
				//直接加入openList當中
				if (tmp.x == x2 && tmp.y == y2) {
					flag = true;
					current = n;
				}
				//如果這個加入點為終點，将标記記為true
			}
			else {
				//如果visit等于2
				AStarNode n = a[tmp.x][tmp.y];
				int price = 10;
				if (abs(around[i].x) + abs(around[i].y) > 1) price = 14;
				if (n.G + price < current.G) {
					current.G = n.G + price;
					current.parent = n.pos;
				}
				//需要判斷從這個點到達待處理點是否為更優路徑,如果是則進行改動
			}
		}
	}
	if (flag) {
		while (current.pos.x != x1 || current.pos.y != y1) {
			record.push(current);
			current = a[current.parent.x][current.parent.y];
		}
		record.push(current);
		while (!record.empty()) {
			cout << "(" << record.top().pos.x << " ," << record.top().pos.y << ") " << record.top().F << endl;
			record.pop();
		}
	}
	//終點加入openList中，說明搜尋成功，從終點開始通路父節點至起點并用棧來儲存；之後再周遊一遍棧将路徑列印出來

	return flag;
}
//A*算法主體

int main()
{
	int map[MAX][MAX] = {
		1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
		1, 1, 1, 1, 1, 0, 1, 1, 0, 1,
		1, 1, 0, 1, 1, 1, 0, 1, 1, 1,
		1, 1, 1, 1, 0, 1, 1, 1, 1, 1,
		1, 1, 1, 1, 1, 0, 0, 0, 1, 1,
		1, 0, 1, 1, 0, 0, 1, 1, 0, 1,
		1, 1, 1, 1, 0, 1, 0, 1, 1, 1,
		1, 0, 1, 0, 1, 1, 1, 0, 1, 1,
		1, 0, 1, 1, 1, 1, 1, 1, 1, 1,
		1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	};
	cout << AStar(map, 4, 4, 9, 9) << endl;

	system("pause");
}
//編造資料進行測試
           

五、結果示範

将最短路徑的節點坐标和F值依次列印出來（測試資料較少，有錯誤歡迎随時指正）。

結果如圖7所示：

圖7

圖8 根據程式運作結果畫出的最優路徑

參考文章

https://blog.csdn.net/hitwhylz/article/details/23089415