#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

#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();     }   } }

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