A星算法C++实现_a星 c++代码

关于A*算法的详细原理在此不再介绍，详情见https://blog.csdn.net/m0_37290785/article/details/93203624
结合详细原理和本代码中的备注来阅读最佳，本代码中的备注非常详细，可读性很强。
首先是每个节点的.h文件和.cpp
node.h

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
using namespace std;
class node
{
public:
	node * father;//父节点用于
	int x, y, gval, hval, fval;//节点位置x，y
	//gval代表了从该节点到父节点的移动代价
	//hval代表了从该节点到终点的距离（该距离的计算方法有多种可详细查找）
	//fval=gval+hval，显然fval越小代表移动代价与该点距离终点的和越小，也就是我们越希望出现的情况
	node(pair<int,int> point,pair<int,int> target,node* father=NULL);
	void show();
	~node();
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

node.cpp

#include "node.h"

node::node(pair<int, int> point, pair<int, int> target, node * parent)
{
	x = point.first; y = point.second;
	father = parent;
	if (parent == NULL) {//没有父节点时
		gval = -1;
		fval = -1;
		hval = -1;
	}
	else {//计算gval\hval\fval
		//本例中使用的hval计算方法为|deltaX|+|deltaY|，本例中的移动方式包含了对角线的移动
		if (abs(father->x - x) + abs(father->y - y) == 1) { gval = 10; }
		else { gval = 14; }
		hval = abs(target.first - x) * 10 + abs(target.second - y) * 10;
		fval = gval + hval;
	}
}

void node::show()
{
	printf("Location: (%d,%d); Gval: %d ; Hval: %d ; Fval: %d .\n", x, y, gval, hval, fval);
}

node::~node()
{
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

然后就是main.cpp

#include"node.h"
const int mapsize = 24;//地图的尺寸
const int barrier = 1;//阻碍物为1
const pair<int, int> start = { 0,0 };//起点
const pair<int, int> target = { 23,23 };//终点
using namespace std;
//设置地图的阻碍物
void setMap(vector<vector<int>>& map, vector<int> rows, vector<int> cols) {
	for (int i = rows[0]; i <= rows[1]; i++) {
		vector<int>& temp = map[i];
		if (cols.size() == 1)temp[cols[0]] = barrier;
		else {
			for (int j = cols[0]; j <= cols[1]; j++) { temp[j] = barrier; }
		}
	}
}
//打印地图：其中阻碍物为1，打印的时候显示为'S'，
//0为可以走的块，打印为'.'，X为最终的行走路线
void showMap(vector<vector<int>>& map) {
	for (auto i : map) {
		for (auto j : i) {
			if (j == 0) { cout << ". "; }
			else if (j == 1) { cout << "S "; }
			else { cout << "X "; }
		}
		cout << endl;
	}
}
//初始化地图，在这里可以设置阻碍物
void initMap(vector<vector<int>>& map) {
	for (int i = 0; i < mapsize; i++) {
		vector<int> t(mapsize, 0);
		map.push_back(t);
	}
	setMap(map, { 2,2 }, { 0,5 });
	setMap(map, { 0,5 }, { 8,8 });
	setMap(map, { 5,5 }, { 3,10 });
	setMap(map, { 7,7 }, { 1,20 });
	setMap(map, { 15,15 }, { 12,23 });
	setMap(map, { 10,20 }, { 11 });
}
//找到openlist中的fval最小的节点
node* findMinF(vector<node*> openlist) {
	int minF = INT_MAX;
	int minIndex=0;
	for (int i = 0; i < openlist.size(); i++) {
		if (openlist[i]->fval == -1) { continue; }
		if (openlist[i]->fval < minF) { minIndex = i; minF = openlist[i]->fval; }
	}
	return openlist[minIndex];
}
//判断cur节点是否存在与list中
node* nodeIn(node*  cur, vector<node*> list) {
	if (list.size() == 0)return NULL;
	for (auto i : list) {
		if (i->x == cur->x&&i->y == cur->y) {
			return i;
		}
	}
	return NULL;
}
//处理cur节点及其周围的8个节点
void listAppend(node* cur, vector<node*>& openlist, vector<node*>& closelist, vector<vector<int>> tarmap) {
	vector<pair<int, int>> points;
	vector<pair<int, int>> temp = { { 0,1 },{ 1,0 },{ -1,0 },{ 0,-1 },{ 1,1 },{ -1,-1 },{ 1,-1 },{ -1,1 } };
	for (auto i : temp) {
		points.push_back({ cur->x + i.first,cur->y + i.second });
	}
	for (auto i : points) {//遍历这八个周围的节点
		int tx = i.first, ty = i.second;
		if (tx < mapsize&&tx >= 0 && ty < mapsize&&ty >= 0) {
			node* t = new node(i, target, cur);
			node* t1 = nodeIn(t, openlist);//当前节点是否在openlist中
			node* t2 = nodeIn(t, closelist);//当前节点是否在closelist中
			if (tarmap[tx][ty] == 1 || t2) { continue; }//如果当前节点是阻碍物，就直接看下一个节点
			if (t1&&t1->gval > t->gval) {//如果当前节点的gval比openlist中的该节点小，
			//这说明之前的路径走到的此节点不如当前的路径走到此节点的代价小，
			//那么就更新当前的节点（非常重要的一个步骤）
				for (int i = 0; i < openlist.size(); i++) {
					node* &temp = openlist[i];
					if (temp->x == t1->x&&temp->y == t1->y) {
						temp = t1; break;
					}
				}
			}
			if (!t1)//如果当前节点不在openlist中，就直接加入到openlist中
				openlist.push_back(t);
		}
	}
}
void getres(node* res, vector<vector<int>>& tarmap) {//打印路径
//从最终的节点来找到起点，通过res=res->father的方式
	vector<pair<int, int>> reslist;
	auto cur = res;
	while (!(cur->x == start.first&&cur->y == start.second)) {
		reslist.push_back({ cur->x,cur->y });
		cur = cur->father;
	}
	reslist.push_back({ cur->x,cur->y });
	for (auto i : reslist) {
		tarmap[i.first][i.second] = 2;
	}
	cout << "------------------------------------------" << endl;
	showMap(tarmap);
	return;
}
void showList(vector<node*> list) {//打印openlist或者closelist用于调试
	for (auto i : list) { printf("(%d,%d):F:%d\n", i->x, i->y, i->fval); }
}
//主函数
int main()
{
	vector<vector<int>> tarmap;
	initMap(tarmap);//初始化地图
	showMap(tarmap);//打印一开始的地图
	vector<node*> openlist;
	vector<node*> closelist;
	openlist.push_back(new node(start, target));//将起点放入openlist
	clock_t startTime, endTime;//计算一下找终点的过程所花的时间
	startTime = clock();
	while (openlist.size() != 0 && nodeIn(new node(target, target), closelist) == NULL) {
	//当openlist不为空并且还没有在closelist中找到终点节点的时候一直循环
		node* temp = findMinF(openlist);//找到当前openlist中的fval最小的值
		temp->show();//把当前节点的信息打印出来看看
		//在openlist中删除当前节点
		int tsize = openlist.size();
		for (int i = 0; i < tsize; i++) {
			node* t = openlist[i];
			if (t->x == temp->x&&t->y == temp->y) {
				openlist.erase(openlist.begin() + i); break;
			}
		}
		//如果当前节点不在closelist中就加入进去
		if (!nodeIn(temp, closelist))
			closelist.push_back(temp);
		listAppend(temp, openlist, closelist, tarmap);//处理当前节点周围的八个节点
	}
	endTime = clock();
	cout << "------------------------------------------" << endl;
	cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;

	auto res = nodeIn(new node(target, target), closelist);
	//没找到的情况：
	if (!res) { cout << "No correct path!" << endl; }
	else { getres(res, tarmap); }
	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

此为运行结果，还有打印的每一个temp节点的信息没有截图下来。

最后需要注意的一点是，本例中的openlist和closelist都是用stl里的vector实现的，但是当查找时还要去遍历list，在考虑到STL的set是使用红黑树实现的，在这一点上可以通过使用set来实现，但是在实现后发现运行时间反而增长了，想了很久没想通为什么。
贴出使用set时的代码
main.cpp(set版本）

#include"node.h"
#include<set>
const int mapsize = 24;
const int barrier = 1;
const pair<int, int> start = { 0,0 };
const pair<int, int> target = { 23,23 };
using namespace std;
//初始化地图
void setMap(vector<vector<int>>& map,vector<int> rows,vector<int> cols) {
	for (int i = rows[0]; i <= rows[1];i++) {
		vector<int>& temp = map[i];
		if (cols.size() == 1)temp[cols[0]] = barrier;
		else {
			for (int j = cols[0]; j <= cols[1]; j++) { temp[j] = barrier; }
		}
	}
}
void showMap(vector<vector<int>>& map) {
	for (auto i : map) {
		for (auto j : i) {
			if (j == 0 ) { cout <<". "; }
			else if (j == 1) { cout << "S "; }
			else { cout << "X "; }
		}
		cout << endl;
	}
}
void initMap(vector<vector<int>>& map) {
	for (int i = 0; i < mapsize; i++) {
		vector<int> t(mapsize, 0);
		map.push_back(t);
	}
	setMap(map, { 2,2 }, { 0,5 });
	setMap(map, { 0,5 }, { 8,8 });
	setMap(map, { 5,5 }, { 3,10 });
	setMap(map, { 7,7 }, { 1,20 });
	setMap(map, { 15,15 }, { 12,23 });
	setMap(map, { 10,20 }, { 11 });
}
node* findMinF(set<node*> openlist) {
	int minF = INT_MAX;
	node* res=*openlist.begin();
	for (auto i : openlist) {
		if (i->fval == -1)continue;
		if (i->fval < minF) { minF = i->fval; res=i;}
	}
	return res;
}
node* nodeIn(node*  cur, set<node*> list) {
	if (list.empty())return NULL;
	for (auto i : list) {
		if (i->x == cur->x&&i->y == cur->y) {
			return i;
		}
	}
	return NULL;
}
void listAppend(node* cur,set<node*>& openlist, set<node*>& closelist, vector<vector<int>> tarmap) {
	vector<pair<int,int>> points;
	vector<pair<int, int>> temp = { {0,1},{1,0},{-1,0},{0,-1},{1,1},{-1,-1},{1,-1},{-1,1} };
	for (auto i : temp) {
		points.push_back({ cur->x + i.first,cur->y + i.second });
	}
	for (auto i : points) {
		int tx = i.first, ty = i.second;
		if (tx < mapsize&&tx >= 0 && ty < mapsize&&ty >= 0) {
			node* t = new node(i, target, cur);
			node* t1 = nodeIn(t, openlist);
			node* t2 = nodeIn(t, closelist);
			if (tarmap[tx][ty] == 1 || t2) { continue; }
			if (t1&&t1->gval > t->gval) {
				openlist.erase(t1);
				openlist.insert(t);
			}
			if (!t1)
				openlist.insert(t);
		}
	}
}
void getres(node* res, vector<vector<int>>& tarmap) {
	vector<pair<int, int>> reslist;
	auto cur = res;
	while (!(cur->x==start.first&&cur->y==start.second)) {
		reslist.push_back({ cur->x,cur->y });
		cur = cur->father;
	}
	reslist.push_back({ cur->x,cur->y });
	for (auto i : reslist) {
		tarmap[i.first][i.second] = 2;
	}
	cout << "------------------------------------------" << endl;
	showMap(tarmap);
	return;
}
void showList(vector<node*> list) {
	for (auto i : list) { printf("(%d,%d):F:%d\n", i->x, i->y, i->fval); }
}
int main()
{
	vector<vector<int>> tarmap;
	initMap(tarmap);
	showMap(tarmap);
	set<node*> openlist;
	set<node*> closelist;
	openlist.insert(new node(start, target));
	clock_t startTime, endTime;
	startTime = clock();
	while (openlist.size() != 0 && nodeIn(new node(target, target), closelist)==NULL) {
		node* temp = findMinF(openlist);
		temp->show();
		int tsize = openlist.size();
		openlist.erase(temp);
		if(!nodeIn(temp,closelist))
			closelist.insert(temp);
		listAppend(temp, openlist,closelist, tarmap);
	}
	endTime = clock();
	cout << "------------------------------------------" << endl;
	cout << "The run time is: " << (double)(endTime - startTime) / CLOCKS_PER_SEC << "s" << endl;
	auto res = nodeIn(new node(target, target), closelist);
	if (!res) { cout << "No correct path!" << endl; }
	else {getres(res, tarmap);}
	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125