A*算法示例代码和详解

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;

char maze[10][10] = {'.','.','.','.','.','.','.','.','.','.',
                     '.','.','*','*','*','.','.','.','.','.',
                     '.','.','.','.','*','.','.','.','.','.',
                     '.','.','.','.','*','.','.','.','.','.',
                     '.','S','.','.','*','.','.','.','.','.',
                     '.','.','.','.','.','.','.','.','.','.',
                     '.','.','.','.','*','.','.','.','.','.',
                     '.','.','.','.','*','.','.','.','E','.',
                     '.','.','*','*','*','*','*','*','*','.',
                     '.','.','.','.','.','.','.','.','.','.',};
class point
{
public:
	char val;
	int x, y;
	int f,g,h;
	int prex, prey;
	bool isopen;
	bool isclose;
};

struct pointcmp
{
	bool operator() (point x, point y)
	{
		if(x.f == y.f)
			return x.h > y.h;
		else
			return x.f > y.f;
	}
};

int xx[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
point ma[10][10];
priority_queue<point, vector<point>,pointcmp> open_list;
priority_queue<point> close_list;

void getpath()
{
	ma[4][1].h = 10;
	ma[4][1].f = 10;
	ma[4][1].isopen = true;
	open_list.push(ma[4][1]);
	point node1, node2;
	int px, py, g;
	while(!open_list.empty())
	{
		node1 = open_list.top();
		open_list.pop();
		ma[node1.x][node1.y].isclose = true;
		g = node1.g + 1;
		for(int i = 0; i < 4; i++)
		{
			px = node1.x + xx[i][0];
			py = node1.y + xx[i][1];
			if(px < 0 || py < 0 || px > 9 || py > 9) continue;
			if(ma[px][py].val == '.' && ma[px][py].isopen == false && ma[px][py].isclose == false)
			{
				ma[px][py].g = g;
				ma[px][py].h = abs(px - 7) + abs(py - 8);
				ma[px][py].f = g + ma[px][py].h;
				ma[px][py].isopen = true;
				ma[px][py].prex = node1.x;
				ma[px][py].prey = node1.y;
				open_list.push(ma[px][py]);
			}
			else if(ma[px][py].val == '.' && ma[px][py].isopen == true && ma[px][py].isclose == false)
			{
				if(g + abs(px - 7) + abs(py - 8) < ma[px][py].f)
				{
					ma[px][py].g = g;
					ma[px][py].h = abs(px - 7) + abs(py - 8);
					ma[px][py].f = g + ma[px][py].h;
					ma[px][py].prex = node1.x;
					ma[px][py].prey = node1.y;
				}
			}
			else if(ma[px][py].val == 'E')
			{
				ma[px][py].prex = node1.x;
				ma[px][py].prey = node1.y;
				node2 = ma[px][py];
				while(node2.val != 'S')
				{
					cout << "("<<node2.x<<", "<<node2.y<<")"<<endl;
					node2 = ma[node2.prex][node2.prey];
				}
				return;
			}
		}
	}
}

int main()
{
	for(int i = 0; i < 10; i++)
		for(int j = 0; j < 10; j++)
		{
			ma[i][j].val = maze[i][j];
			ma[i][j].f = 0;
			ma[i][j].g = 0;
			ma[i][j].h = 0;
			ma[i][j].isopen = false;
			ma[i][j].isclose = false;
			ma[i][j].x = i;
			ma[i][j].y = j;
		}
	getpath();
}

最后

以上就是欢呼小土豆为你收集整理的A*算法示例代码和详解的全部内容，希望文章能够帮你解决A*算法示例代码和详解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。