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;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

您可能感兴趣的文章:

• 贪吃蛇C语言代码实现（难度可选）
• C语言手把手教你实现贪吃蛇AI（上）
• C语言贪吃蛇经典小游戏
• C语言链表实现贪吃蛇游戏
• C语言结构数组实现贪吃蛇小游戏
• 基于C语言实现的贪吃蛇游戏完整实例代码
• C语言手把手教你实现贪吃蛇AI（下）