A*搜索算法

深碍√TFBOYSˉ_ 2022-08-03 13:49 206阅读 0赞

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;
    }

这是一个简易版本，不保证路径最短，后面我会实现一个最短路径的版本。