手把手教你实现贪吃蛇AI，具体内容如下
1. 目标
这一部分主要是讲解编写贪吃蛇AI所需要用到的算法基础。
2. 问题分析
贪吃蛇AI说白了就是寻找一条从蛇头到食物的一条最短路径，同时这条路径需要避开障碍物，这里仅有的障碍就是蛇身。而A star 算法就是专门针对这一个问题的。在A star 算法中需要用到排序算法，这里采用堆排序（当然其他排序也可以），如果对堆排序不熟悉的朋友，请移步到这里——堆排序，先看看堆排序的内容。
3. A*算法
A star(也称A*)搜寻算法俗称A星算法。这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中对象的移动计算上。A* 算法是一种启发式搜寻算法，有别于DFS， BFS搜索。可以这样理解“启发式”的涵义，比如从起点A到达目的地B的路线，并不是直接告诉你，从A出发，向东行驶200米，右转进入XX路，直行500米到达B；而是从A出发，直行，直到遇到第一家肯德基，右转直到看到B大厦。而A*算法中用来启发的线索就是移动成本，也就是权重。
3.1 移动成本
如下图所示，从A点出发，可以有四个方向可走（由于贪吃蛇仅仅可以走上下左右四个方向，所以这里不考虑走斜线的情况），假设每个方向移动一格的成本为10，A*算法中采用的F值来评价移动成本，F=G+H。假设节点C是待考察的一个点，G代表的是从起点A到C的移动成本，如下图的情况G=10。那么H代表的就是从C点到目标B点的移动代价的预估值，如下图的情况H=50，那么F=60。为什么说是预估，因为现在对于从C点到B点的情况还不清楚，因为中间可能存在障碍物，那么实际的移动代价就会大于预估的情况。而对于待考察点D，其F=80，显然在C 和D点中（当然这里待考察的点不止C和D点），A*算法会选择C点。
3.2 算法流程图
4. 源代码
代码中假定起始点A(5,10)，食物B(5,15)，如下图。其中‘X'代表障碍物，‘O'代表的就是寻找到的从A到B的路径。
|
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
#include<stdio.h> #include<stdlib.h> #define N 32 #define W 10 typedef struct STARNODE{ int x;//节点的x,y坐标 int y; int G;//该节点的G, H值 int H; int is_snakebody;//是否为蛇身，是为1，否则为0； int in_open_table;//是否在open_table中，是为1，否则为0； int in_close_table;//是否在close_table中，是为1，否则为0； struct STARNODE* ParentNode;//该节点的父节点 } starnode, *pstarnode; starnode mapnode[N/2+2][N+4]; pstarnode opentable[N*N/2]; pstarnode closetable[N*N/2]; int opennode_count=0; int closenode_count=0; starnode food; //根据指针所指向的节点的F值，按大顶堆进行调整 void heapadjust(pstarnode a[], int m, int n) { int i; pstarnode temp=a[m]; for(i=2*m;i<=n;i*=2) { if(i+1<=n && (a[i+1]->G+a[i+1]->H)>(a[i]->G+a[i]->H) ) { i++; } if((temp->G+temp->H)>(a[i]->G+a[i]->H)) { break; } a[m]=a[i]; m=i; } a[m]=temp; } void swap(pstarnode a[],int m, int n) { pstarnode temp; temp=a[m]; a[m]=a[n]; a[n]=temp; } void crtheap(pstarnode a[], int n) { int i; for(i=n/2;i>0;i--) { heapadjust(a, i, n); } } void heapsort(pstarnode a[], int n) { int i; crtheap(a,n); for(i=n;i>1;i--) { swap(a,1,i); heapadjust(a, 1,i-1); } } //x1, y1是邻域点坐标 //curtnode是当前点坐标 void insert_opentable(int x1, int y1, pstarnode pcurtnode) { int i; if(!mapnode[x1][y1].is_snakebody && !mapnode[x1][y1].in_close_table)//如果不是蛇身也不在closetable中 { if(mapnode[x1][y1].in_open_table && mapnode[x1][y1].G>pcurtnode->G+W)//如果已经在opentable中,但是不是最优路径 { mapnode[x1][y1].G=pcurtnode->G+W;//把G值更新 mapnode[x1][y1].ParentNode=pcurtnode;//把该邻点的双亲节点更新 //由于改变了opentable中一个点的F值，需要对opentable中的点的顺序进行调整，以满足有序 for(i=1;i<=opennode_count;i++) { if(opentable[i]->x==x1 && opentable[i]->y==y1) { break; } heapsort(opentable, i); } } else//把该点加入opentable中 { opentable[++opennode_count]=&mapnode[x1][y1]; mapnode[x1][y1].G=pcurtnode->G+W; mapnode[x1][y1].H=(abs(food.x-x1)+abs(food.y-y1))*W; mapnode[x1][y1].in_open_table=1; mapnode[x1][y1].ParentNode=pcurtnode; heapsort(opentable, opennode_count); } } } //寻找当前点的四邻域点，把符合条件的点加入opentable中 void find_neighbor(pstarnode pcurtnode) { int x=pcurtnode->x; int y=pcurtnode->y; if(x+1<=N/2) { insert_opentable(x+1, y, pcurtnode); } if(x-1>=1) { insert_opentable(x-1, y, pcurtnode); } if(y+1<=N+1) { insert_opentable(x,y+1, pcurtnode); } if(y-1>=2) { insert_opentable(x,y-1, pcurtnode); } } int search_road(pstarnode startnode, pstarnode endnode) { int is_search_road=0; opennode_count=0; closenode_count=0; pstarnode pcurtnode; opentable[++opennode_count]=startnode;//起始点加入opentable中 startnode->in_open_table=1; startnode->ParentNode=NULL; startnode->G=0; startnode->H=(abs(endnode->x-startnode->x)+abs(endnode->y-startnode->y))*W; if(startnode->x==endnode->x && startnode->y==endnode->y)//如果起点和终点重合 { is_search_road=1; return is_search_road; } while(1) { //取出opentable中第1个节点加入closetable中 pcurtnode=opentable[1]; opentable[1]=opentable[opennode_count--]; closetable[++closenode_count]=pcurtnode; pcurtnode->in_open_table=0; pcurtnode->in_close_table=1; if(pcurtnode->x==endnode->x && pcurtnode->y==endnode->y) { is_search_road=1; break; } find_neighbor(pcurtnode); if(!opennode_count)//如果opentable已经为空，即没有找到路径 { break; } } return is_search_road; } int main(void) { int i, j; pstarnode startnode; for(i=0;i<N/2+2;i++) for(j=0;j<N+4;j++) { mapnode[i][j].G=0; mapnode[i][j].H=0; mapnode[i][j].in_close_table=0; mapnode[i][j].in_open_table=0; mapnode[i][j].is_snakebody=0; mapnode[i][j].ParentNode=NULL; mapnode[i][j].x=i; mapnode[i][j].y=j; } startnode=&mapnode[5][10]; food.x=5; food.y=15; mapnode[5][13].is_snakebody=1; mapnode[6][13].is_snakebody=1; mapnode[4][13].is_snakebody=1; mapnode[4][12].is_snakebody=1; mapnode[6][12].is_snakebody=1; int flag; flag=search_road(startnode, &food); pstarnode temp=&mapnode[5][15]; do{ printf("%d %d ",temp->x, temp->y); temp=temp->ParentNode; }while(temp); return 0; } |
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://blog.csdn.net/kuweicai/article/details/66472548
