概要
A*算法是一种启发式寻路算法，BFS是一种盲目的无目标的搜索算法，相比于BFS，A*算法根据适应度构建优先队列，根据适应度值可以很好的向目标点移动，具体详情，请看搜索相关文档，我在只是实现了在无障碍的情况下的A*算法，有障碍的情况类似。
开发环境
visual studio 2017 + eaysX
实现
1 #include<stdio.h>
2 #include<vector>
3 #include<queue>
4 #include<graphics.h>
5 #include<stdlib.h>
6 #include<time.h>
7 #include<unordered_set>
8
9 using namespace std;
10
11 const int WIDTH_BLOCK_NUM =
20;
12 const int HEIGHT_BLOCK_NUM =
20;
13 const int WINDOWS_WIDTH =
800;
14 const int WINDOWS_HEIGHT =
800;
15 const int MAX_MARK =
20;
16 const int MIN_MARK =
0;
17
18 int dir_x[] = {
1,
1,
1,
0,
0,-
1,-
1,-
1 };
19 int dir_y[] = {
1,-
1,
0,
1,-
1,
1,-
1,
0 };
20
21 struct Block
22 {
23 public:
24 int x, y;
25 int f;
26 int g;
27 Block(
int x,
int y,
int f,
int g)
28 {
29 this->x =
x;
30 this->y =
y;
31 this->f =
f;
32 this->g =
g;
33 }
34 Block() {}
35 friend
bool operator<
(Block a, Block b) {
36 return a.f + a.g > b.f +
b.g;
37 }
38 };
39 priority_queue<Block>
pq;
40 vector<Block>
vec;
41 vector<Block>
local_vec;
42 unordered_set<
int>
us;
43 Block start_block, end_block;
44
45
46
47 int randInt(
int left,
int right);
48 void init();
49 void draw();
50 void position2rectangle(
struct Block&b,
int rect[][
2]);
51 bool is_valid(
int x,
int y);
52 int position2mark(
int x,
int y);
53
54
55 int main()
56 {
57 srand(time(NULL));
58 init();
59 initgraph(WINDOWS_WIDTH, WINDOWS_HEIGHT);
60 Block temp =
start_block;
61 pq.push(temp);
62 us.insert(position2mark(temp.x, temp.y));
63
64 while (!(temp.x == end_block.x&&temp.y ==
end_block.y))
65 {
66 temp =
pq.top();
67 pq.pop();
68 vec.push_back(temp);
69 for (
int i =
0; i <
8; ++
i) {
70 int temp_x = temp.x +
dir_x[i];
71 int temp_y = temp.y +
dir_y[i];
72 if (is_valid(temp_x, temp_y) && !
us.count(position2mark(temp_x, temp_y))) {
73 Block b;
74 b.x =
temp_x;
75 b.y =
temp_y;
76 b.f = temp.f + (abs(dir_x[i]) + abs(dir_y[i])) >
1 ?
14 :
10;
77 b.g = (abs(temp_x - end_block.x) + abs(temp_y - end_block.y)) *
10;
78 pq.push(b);
79 us.insert(position2mark(temp_x, temp_y));
80 local_vec.push_back(b);
81 }
82 }
83 draw();
84 }
85 closegraph();
86 return 0;
87 }
88
89 int randInt(
int left,
int right)
90 {
91 return rand() % (right - left +
1) +
left;
92 }
93
94 void init()
95 {
96 start_block.x =
randInt(MIN_MARK, MAX_MARK);
97 start_block.y =
randInt(MIN_MARK, MAX_MARK);
98 end_block.x =
randInt(MIN_MARK, MAX_MARK);
99 end_block.y =
randInt(MIN_MARK, MAX_MARK);
100 while (start_block.x==end_block.x||start_block.y==
end_block.y)
101 {
102 end_block.x =
randInt(MIN_MARK, MAX_MARK);
103 end_block.y =
randInt(MIN_MARK, MAX_MARK);
104 }
105 }
106
107 void draw()
108 {
109 int width = WINDOWS_WIDTH /
WIDTH_BLOCK_NUM;
110 int height = WINDOWS_HEIGHT /
HEIGHT_BLOCK_NUM;
111 for (
int i =
0; i < WINDOWS_WIDTH; i +=
width)
112 {
113 line(i,
0, i, WINDOWS_HEIGHT);
114 }
115
116 for (
int i =
0; i < WINDOWS_HEIGHT; i +=
height)
117 {
118 line(
0, i, WINDOWS_WIDTH, i);
119 }
120 int arr[
2][
2];
121 COLORREF prev_color =
getfillcolor();
122
123 setfillcolor(BLUE);
124 for (Block b : local_vec)
125 {
126 position2rectangle(b, arr);
127 fillrectangle(arr[
0][
0], arr[
0][
1], arr[
1][
0], arr[
1][
1]);
128 }
129
130
131 setfillcolor(RED);
132 for (Block b : vec)
133 {
134 position2rectangle(b, arr);
135 fillrectangle(arr[
0][
0], arr[
0][
1], arr[
1][
0], arr[
1][
1]);
136 }
137
138
139
140 setfillcolor(GREEN);
141 position2rectangle(start_block, arr);
142 fillrectangle(arr[
0][
0], arr[
0][
1], arr[
1][
0], arr[
1][
1]);
143 position2rectangle(end_block, arr);
144 fillrectangle(arr[
0][
0], arr[
0][
1], arr[
1][
0], arr[
1][
1]);
145
146 setfillcolor(prev_color);
147 Sleep(
1000);
148 }
149
150 void position2rectangle(
struct Block&b,
int rect[][
2])
151 {
152 int width = WINDOWS_WIDTH /
WIDTH_BLOCK_NUM;
153 int height = WINDOWS_HEIGHT /
HEIGHT_BLOCK_NUM;
154 int temp_x = b.x*
width;
155 int temp_y = b.y*
height;
156 rect[
0][
0] =
temp_x;
157 rect[
0][
1] =
temp_y;
158 rect[
1][
0] = temp_x +
width;
159 rect[
1][
1] = temp_y +
height;
160 }
161
162 bool is_valid(
int x,
int y)
163 {
164 if (x <
0 || y <
0 || x >= WIDTH_BLOCK_NUM || y >=
HEIGHT_BLOCK_NUM) {
165 return false;
166 }
167 return true;
168 }
169
170 int position2mark(
int x,
int y)
171 {
172 return x + y *
WIDTH_BLOCK_NUM;
173 }
运行展示
转载于:https://www.cnblogs.com/oldBook/p/9900221.html
相关资源：A星寻路算法 MFC写的动态演示程序
