C语⾔⼿把⼿教你实现贪吃蛇AI（中）
⼿把⼿教你实现贪吃蛇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的路径。
#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\n",temp->x, temp->y);
temp=temp->ParentNode;
}while(temp);
return 0;
}
以上就是本⽂的全部内容，希望对⼤家的学习有所帮助，也希望⼤家多多⽀持。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。