A*搜尋算法

A*搜尋算法俗稱A星算法。這是一種在圖形平面上，有多個節點的路徑。求出最低通過成本的算法。經常使用于遊戲中的NPC的移動計算，或線上遊戲的BOT的移動計算上。

這樣的算法的所獲得的路徑并不一定是最短路徑但一定是我們所關注的某一方面價值最“優”的路徑。我們将地圖劃分為一個個節點，從出發點到目标的路徑就能夠使用一個節點清單來表示。

那麼怎樣獲得的這個節點清單才算是“最優”呢？這就要用到我們前面提到的啟示式函數，詳細表示啟示式函數例如以下：

F（p） =  G（p） +  H（p）

當中F值表示對象從起點經過目前節點p到達目标節點估計總消耗值，G值表示對象從起點到達目前節點p時須要消耗值，H值則表示對象從目前節點p估計到達目标節點須要消耗值。這裡須要說明的是，H值是一個估價值，是對象從p點到目标點時，對我們關心的屬性定義依照既定計算方式的一種消耗估計，不考慮障礙。能夠用棋盤格距離度量，是以這個值并不一定準确。僅僅是起到一個預期的評價。我的了解是H的作用是起到指引作用。指導下次搜尋的方向盡可能向目标靠近。當我們對H值得估算給出不同的計算方案時。經過A星得到的路徑優勢點也就不同。可能是最短路徑。也可能是最節省資金的路徑……總之就是我們關心的這一屬性上消耗最小的一條路徑。

#include "stdafx.h"
#include<vector>
#include<set>
#include<algorithm>
#include<iostream>

using namespace std;
#define N 10
#define STARPOINT   1  
#define ENDPOINT    2  
#define BARRIER     3 
#define ROAD        0
//數組中1代表起點，2代表終點，0代表能夠通過，3代表障礙物
int landscape[N][N] = {           
	{ 1, 0, 0, 3, 0, 3, 0, 0, 0, 0 },
	{ 0, 0, 3, 0, 0, 0, 0, 3, 0, 3 },
	{ 3, 0, 0, 0, 0, 3, 3, 3, 0, 3 },
	{ 3, 0, 3, 0, 0, 3, 0, 2, 0, 3 },
	{ 3, 0, 0, 0, 0, 3, 0, 0, 0, 3 },
	{ 3, 0, 0, 3, 0, 0, 3, 3, 0, 3 },
	{ 3, 0, 0, 0, 0, 3, 3, 0, 0, 0 },
	{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
	{ 3, 3, 3, 0, 0, 3, 0, 3, 0, 3 },
	{ 3, 0, 0, 0, 0, 3, 3, 3, 0, 3 },
};
set<pair<int, int>>close_table;
pair<int, int>endpoint(3, 7);
vector<pair<int, int>>path;
bool UDless(pair<pair<int, int>, int> elem1, pair<pair<int, int>, int> elem2)
{
	return elem1.second > elem2.second;
}
vector<pair<pair<int, int>, int>>get_opentable(pair<int,int>current_point)
{
	vector<pair<pair<int, int>, int>>ve;
	if (current_point.first - 1 >= 0 && current_point.second - 1 >= 0 && landscape[current_point.first - 1][current_point.second - 1] != BARRIER
		&&close_table.find(pair<int, int>(current_point.first - 1, current_point.second - 1) )== close_table.end())
	{
		int k = abs(endpoint.first - current_point.first + 1) +
			abs(endpoint.second - current_point.second + 1)+14;
		pair<pair<int, int>, int>cc(pair<int, int>(current_point.first - 1, current_point.second - 1), k);
		ve.push_back(cc);//左上
	}
	if (current_point.first - 1 >= 0 && landscape[current_point.first - 1][current_point.second] != BARRIER &&
		close_table.find(pair<int, int>(current_point.first - 1, current_point.second)) == close_table.end())
	{
		int k = abs(endpoint.first - current_point.first + 1) +
			abs(endpoint.second - current_point.second)+10;
		pair<pair<int, int>, int>cc(pair<int, int>(current_point.first - 1, current_point.second), k);
		ve.push_back(cc);//正上
		
	}
	if (current_point.first - 1 >= 0 && current_point.second + 1 <N&& landscape[current_point.first - 1][current_point.second + 1] != BARRIER &&
		close_table.find(pair<int, int>(current_point.first - 1, current_point.second + 1)) == close_table.end())
	{
		int k = abs(endpoint.first - current_point.first + 1) +
			abs(endpoint.second - current_point.second - 1)+14;
		pair<pair<int, int>, int>cc(pair<int, int>(current_point.first - 1, current_point.second + 1), k);
		ve.push_back(cc);//右上
	}
	if (current_point.second + 1 < N&& landscape[current_point.first][current_point.second + 1] != BARRIER &&
		close_table.find(pair<int, int>(current_point.first, current_point.second + 1)) == close_table.end())
	{
		int k = abs(endpoint.first - current_point.first) +
			abs(endpoint.second - current_point.second-1)+10;
		pair<pair<int, int>, int>cc(pair<int, int>(current_point.first, current_point.second+1), k);
		ve.push_back(cc);//正右
	}
	if (current_point.first + 1 <N && current_point.second + 1 <N&& landscape[current_point.first + 1][current_point.second + 1] != BARRIER &&
		close_table.find(pair<int, int>(current_point.first+1, current_point.second + 1)) == close_table.end())
	{
		int k = abs(endpoint.first - current_point.first - 1) +
			abs(endpoint.second - current_point.second - 1) + 14;
		pair<pair<int, int>, int>cc(pair<int, int>(current_point.first +1, current_point.second + 1), k);
		ve.push_back(cc);//右下
	}
	if (current_point.first + 1 <N && landscape[current_point.first + 1][current_point.second] != BARRIER &&
		close_table.find(pair<int, int>(current_point.first + 1, current_point.second)) == close_table.end())
	{
		int k = abs(endpoint.first - current_point.first - 1) +
			abs(endpoint.second - current_point.second ) + 10;
		pair<pair<int, int>, int>cc(pair<int, int>(current_point.first + 1, current_point.second), k);
		ve.push_back(cc);//正下
	}
	if (current_point.first + 1 <N && current_point.second - 1 >= 0 && landscape[current_point.first + 1][current_point.second - 1] != BARRIER &&
		close_table.find(pair<int, int>(current_point.first + 1, current_point.second - 1)) == close_table.end())
	{
		int k = abs(endpoint.first - current_point.first - 1) +
			abs(endpoint.second - current_point.second + 1) + 14;
		pair<pair<int, int>, int>cc(pair<int, int>(current_point.first  +1, current_point.second - 1), k);
		ve.push_back(cc);//左下
	}
	if (current_point.second - 1 >= 0 && landscape[current_point.first][current_point.second - 1] != BARRIER &&
		close_table.find(pair<int, int>(current_point.first , current_point.second - 1)) == close_table.end())
	{
		int k = abs(endpoint.first - current_point.first ) +
			abs(endpoint.second - current_point.second + 1) + 10;
		pair<pair<int, int>, int>cc(pair<int, int>(current_point.first, current_point.second - 1), k);
		ve.push_back(cc);//正左
	}
	sort(ve.begin(), ve.end(), UDless);
	return ve;
}


bool A_star_search(pair<int,int>startpoint)
{
	path.push_back(startpoint);
	close_table.insert(path.back());
	vector<pair<pair<int, int>, int>>open_table;
	vector<vector<pair<pair<int, int>, int>>>aa;
	open_table = get_opentable(startpoint);
	if (open_table.empty())
		return false;
	path.push_back(open_table.back().first);
	close_table.insert(path.back());
	open_table.pop_back();
	aa.push_back(open_table);
	while (!aa.empty())
	{
		open_table = get_opentable(path.back());
		if (!open_table.empty())
		{
			path.push_back((open_table.back()).first);
			close_table.insert(path.back());
			vector<pair<pair<int, int>, int>>::iterator it;
			for (it = open_table.begin(); it != open_table.end(); it++)
				if (landscape[(*it).first.first][(*it).first.second] == ENDPOINT)
				{
					path.push_back(endpoint);
					return true;
				}
			open_table.pop_back();
			aa.push_back(open_table);
		}
		if (open_table.empty())
		{
			
			while ((aa.back()).empty())
			{
				close_table.erase(path.back());
				path.pop_back();
				aa.pop_back();
				if (aa.empty())
					return false;
			}
			close_table.erase(path.back());
			path.pop_back();
			path.push_back(aa.back().back().first);
			close_table.insert(path.back());
			aa.back().pop_back();
		}
	}

}






int _tmain(int argc, _TCHAR* argv[])
{
	vector<pair<int, int>>::iterator it;
	if (A_star_search(pair<int, int>(0, 0)))
		for (it = path.begin(); it != path.end(); it++)
			cout << "(" << (*it).first << "," << (*it).second << ")" << endl;

	system("pause");
	return 0;
}