C语言手把手教你实现贪吃蛇AI（下）

本文实例为大家分享了C语言实现贪吃蛇AI的具体代码，供大家参考，具体内容如下

1. 目标

        这一部分的目标是把之前写的贪吃蛇加入AI功能，即自动的去寻找食物并吃掉。

2. 控制策略

        为了保证蛇不会走入“死地”，所以蛇每前进一步都需要检查，移动到新的位置后，能否找到走到蛇尾的路径，如果可以，才可以走到新的位置；否则在当前的位置寻找走到蛇尾的路径，并按照路径向前走一步，开始循环之前的操作，如下图所示。这个策略可以工作，但是并不高效，也可以尝试其他的控制策略，比如易水寒的贪吃蛇AI

        运行效果如下:

3. 源代码

需要注意的是，由于mapnode的数据量比较大，这里需要把栈的大小设置大一点，如下图所示，否则会出现栈溢出的情况。

整个项目由以下三个文件组成：

a. snake AI.h

#ifndef SNAKE_H_
#define SNAKE_H_
#include<stdio.h>
#include<Windows.h> //SetConsoleCursorPosition, sleep函数的头函数
#include<time.h> //time()的头函数
#include<malloc.h>  //malloc()的头函数
#define N 32 //地图大小
#define snake_mark '#'//表示蛇身
#define food_mark '$'//表示食物
#define sleeptime 50//间隔时间

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

extern starnode (*mapnode)[N + 4];
extern pstarnode opentable[N*N / 2];
extern pstarnode closetable[N*N / 2];

extern int opennode_count;
extern int closenode_count;

/*表示蛇身坐标的结构体*/
typedef struct SNAKE{
  int x; //行坐标
  int y; //列坐标
  struct SNAKE* next;
}snake_body, *psnake;
extern psnake snake;
extern psnake food;
extern psnake snaketail;
extern psnake nextnode;

void set_cursor_position(int x, int y);
void initial_map();
void initial_mapnode();
void update_mapnode();
void printe_map();
void initial_snake();
void create_food();
int is_food();
void heapadjust(pstarnode a[], int m, int n);
void swap(pstarnode a[], int m, int n);
void crtheap(pstarnode a[], int n);
void heapsort(pstarnode a[], int n);
void insert_opentable(int x1, int y1, pstarnode pcurtnode, psnake endnode);
void find_neighbor(pstarnode pcurtnode, psnake endnode);
int search_short_road(psnake snakehead, psnake endnode);
int search_snaketail(psnake snakehead);
void update_snaketail(psnake snakehead);
void snake_move();
psnake create_tsnake();
void snake_control();
#endif

b. source.cpp

#include"Snake AI.h"

/*控制光标的坐标*/
void set_cursor_position(int x, int y)
{
  COORD coord = { x, y };//x表示列，y表示行。
  SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), coord);
}


/*初始化后的地图为 N列 N/2行*/
/*游戏的空间为2至N+1列，1至N/2行*/
void initial_map()
{
  int i = 0;

  //打印上下边框（每个■占用一行两列）
  for (i = 0; i<N / 2 + 2; i++)
  {
    set_cursor_position(22 * i, 0);
    printf("■");
    set_cursor_position(22 * i, N / 2 + 1);
    printf("■");
  }
  for (i = 0; i<N / 2 + 2; i++)  //打印左右边框
  {
    set_cursor_position(0, i);
    printf("■");
    set_cursor_position(N + 2, i);
    printf("■");
  }
}

//初始化mapnode
void initial_mapnode()
{
  int i = 0, j = 0;
  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;
    }
}

//初始化mapnode
void update_mapnode()
{
  psnake temp = snake;
  int x, y;


  initial_mapnode();//初始化mapnode

  while (temp)
  {
    x = temp->x;
    y = temp->y;
    mapnode[x][y].is_snakebody = 1;
    temp = temp->next;
  }
}

void printe_map()
{
  psnake temp = snake;
  while (temp)
  {
    set_cursor_position(temp->y, temp->x);
    printf("%c", snake_mark);
    temp = temp->next;
  }
  if (food)
    set_cursor_position(food->y, food->x);
  printf("%c", food_mark);
  set_cursor_position(0, N / 2 + 2);
}

/*初始化蛇身*/
/*蛇身初始化坐标为（8,5）,(8,4), (8,3) */
void initial_snake()
{
  int i = 5;//列
  int j = N / 4;//行
  psnake tsnake = NULL, temp = NULL;

  snake = (psnake)malloc(sizeof(snake_body));
  (snake)->x = j;
  (snake)->y = i;
  (snake)->next = NULL;
  tsnake = snake;

  for (i = 4; i >2; i--)
  {
    temp = (psnake)malloc(sizeof(snake_body));
    (temp)->x = j;
    (temp)->y = i;
    (temp)->next = NULL;
    (tsnake)->next = (temp);
    (tsnake) = (tsnake)->next;
  }

  snaketail = tsnake;
}

//生成食物
void create_food()
{
  srand((unsigned)time(NULL));
  food->y = rand() % N + 2;//列
  food->x = rand() % (N / 2) + 1;//行

  //检查食物是否和蛇身重回
  update_mapnode();
  if (mapnode[food->x][food->y].is_snakebody)
  {
    create_food();
  }
}

//判断是否吃到食物，吃到食物返回 1，否则返回 0；
int is_food()
{
  if (snake->x == food->x && snake->y == food->y)
    return 1;
  return 0;
}

//根据指针所指向的节点的F值，按大顶堆进行调整
void heapadjust(pstarnode a[], int m, int n)
{
  int i;
  pstarnode temp = a[m];
  for (i = 22 * 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是当前点坐标
//endnode是目标点坐标
void insert_opentable(int x1, int y1, pstarnode pcurtnode, psnake endnode)
{
  int i = 1;
  if (!mapnode[x1][y1].is_snakebody && !mapnode[x1][y1].in_close_table)//如果不是蛇身也不在closetable中
  {
    if (mapnode[x1][y1].in_open_table)//如果已经在opentable中
    {
      if (mapnode[x1][y1].G > pcurtnode->G + W)//但是不是最优路径
      {
        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中
    {
      opentable[++opennode_count] = &mapnode[x1][y1];

      mapnode[x1][y1].G = pcurtnode->G + W;
      mapnode[x1][y1].H = (abs(endnode->x - x1) + abs(endnode->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, psnake endnode)
{
  int x;
  int y;
  x = pcurtnode->x;
  y = pcurtnode->y;

  if (x + 1 <= N / 2)
  {
    insert_opentable(x + 1, y, pcurtnode, endnode);
  }
  if (x - 1 >= 1)
  {
    insert_opentable(x - 1, y, pcurtnode, endnode);
  }
  if (y + 1 <= N + 1)
  {
    insert_opentable(x, y + 1, pcurtnode, endnode);
  }
  if (y - 1 >= 2)
  {
    insert_opentable(x, y - 1, pcurtnode, endnode);
  }
}


int search_short_road(psnake snakehead, psnake endnode)
{
  int is_search_short_road = 0;
  opennode_count = 0;
  closenode_count = 0;
  pstarnode pcurtnode;
  pstarnode temp;
  pstarnode startnode = &mapnode[snakehead->x][snakehead->y];//startnode指向蛇头所对应的结点

  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;

  while (1)
  {
    //取出opentable中第1个节点加入closetable中
    if (!opennode_count)//如果opentable已经为空，即没有找到路径
    {
      //printf("No way");
      return is_search_short_road;
    }
    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_short_road = 1;
      break;
    }

    find_neighbor(pcurtnode, endnode);

  }
  if (is_search_short_road)//如果找到，则用nextnode记录蛇头下一步应该移动的位置
  {

    temp = closetable[closenode_count];
    while (temp->ParentNode->ParentNode)
    {
      temp = temp->ParentNode;
    }
    nextnode->x = temp->x;
    nextnode->y = temp->y;
    nextnode->next = NULL;
  }

  return is_search_short_road;
}

int search_snaketail(psnake snakehead)
{
  int t = 0;
  update_mapnode();
  mapnode[snaketail->x][snaketail->y].is_snakebody = 0;
  t = search_short_road(snakehead, snaketail);
  mapnode[snaketail->x][snaketail->y].is_snakebody = 1;
  return t;
}

//蛇尾向前移动一格，并把原来的蛇尾注销
void update_snaketail(psnake snakehead)
{
  psnake temp;
  temp = snakehead;
  while (temp->next->next)
  {
    temp = temp->next;
  }
  snaketail = temp;
  temp = temp->next;
  mapnode[temp->x][temp->y].is_snakebody = 0;//将蛇尾注销掉
}

//将蛇身移动到指定的位置(nextnode)，并打印出来
void snake_move()
{
  psnake snake_head = (psnake)malloc(sizeof(snake_body));

  snake_head->x = nextnode->x;
  snake_head->y = nextnode->y;
  snake_head->next = snake;
  snake = snake_head;

  if (is_food())//如果是食物
  {
    create_food();
    printe_map();
  }

  else//不是食物
  {
    psnake temp = snake_head;
    while (temp->next->next)//寻找蛇尾
    {
      temp = temp->next;
    }
    snaketail = temp;//更新snaketail的位置

    set_cursor_position(temp->next->y, temp->next->x);
    printf(" ");//把蛇尾用空格消掉
    free(temp->next);//释放蛇尾的内存空间
    temp->next = NULL;//将temp的next置成NULL
    printe_map();
  }
  snake=snake_head;
}

psnake create_tsnake()
{
  psnake tsnake = (psnake)malloc(sizeof(snake_body));
  tsnake->x = nextnode->x;
  tsnake->y = nextnode->y;
  tsnake->next = NULL;
  psnake temp1 = snake;
  psnake temp2 = tsnake;

  while (temp1!=snaketail)
  {
    temp2->next = (psnake)malloc(sizeof(snake_body));
    temp2->next->x = temp1->x;
    temp2->next->y = temp1->y;
    temp2->next->next = NULL;
    temp1 = temp1->next;
    temp2 = temp2->next;
  }
  return tsnake;
}

void snake_control()
{
  int r, t, x, y;
  psnake tsnake = NULL;;

  while (1)
  {

    r = 0;
    t = 0;
    x = 0;
    y = 0;

    update_mapnode();
    r = search_short_road(snake, food);
    if (r == 1)//如果能找到到达食物的路径
    {

      x = nextnode->x;
      y = nextnode->y;

      tsnake=create_tsnake();

      mapnode[x][y].is_snakebody = 1;

      t = search_snaketail(tsnake);//走到下一个节点后，能否找到更新后的蛇尾

      if (t==1)//如果按照路径走到下一个位置，可以找到蛇尾，就把蛇头移动到下一个位置
      {
        nextnode->x = x;
        nextnode->y = y;
        Sleep(sleeptime);
        snake_move();
      }
      else//否则，从该点出发去找蛇尾
      {
        mapnode[x][y].is_snakebody = 0;
        search_snaketail(snake);
        Sleep(sleeptime);
        snake_move();
      }
      free(tsnake);
    }
    else//如果找不到食物
    {
      search_snaketail(snake);
      Sleep(sleeptime);
      snake_move();
    }
  }
}

c. main.cpp

#include"Snake AI.h"

psnake snake = NULL;
psnake food = NULL;
psnake snaketail = NULL;
psnake nextnode = NULL;//蛇头下一步该走的结点

starnode (*mapnode)[N+4]=(starnode(*)[N+4])malloc(sizeof(starnode)*(N/2+2)*(N+4));
pstarnode opentable[N*N / 2];
pstarnode closetable[N*N / 2];

int opennode_count = 0;
int closenode_count = 0;

int main(void)
{
  initial_map();
  initial_snake();
  food = (psnake)malloc(sizeof(snake_body));
  nextnode = (psnake)malloc(sizeof(snake_body));
  food->next = NULL;
  create_food();
  food->x = 1;
  food->y = 3;

  printe_map();
  snake_control();

  free(food);
  free(snake);
  free(mapnode);
  return 0;
}

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

原文链接：http://blog.csdn.net/kuweicai/article/details/69487351