C語言手把手教你實現(xiàn)貪吃蛇AI（中）-創(chuàng)新互聯(lián)

手把手教你實現(xiàn)貪吃蛇AI，具體內(nèi)容如下

站在用戶的角度思考問題，與客戶深入溝通，找到元江縣網(wǎng)站設計與元江縣網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗，讓設計與互聯(lián)網(wǎng)技術結合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：網(wǎng)站設計、做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣、域名注冊、網(wǎng)絡空間、企業(yè)郵箱。業(yè)務覆蓋元江縣地區(qū)。

1. 目標

       這一部分主要是講解編寫貪吃蛇AI所需要用到的算法基礎。

2. 問題分析

        貪吃蛇AI說白了就是尋找一條從蛇頭到食物的一條最短路徑，同時這條路徑需要避開障礙物，這里僅有的障礙就是蛇身。而A star 算法就是專門針對這一個問題的。在A star 算法中需要用到排序算法，這里采用堆排序（當然其他排序也可以），如果對堆排序不熟悉的朋友，請移步到這里——堆排序，先看看堆排序的內(nèi)容。

3. A*算法

      A star(也稱A*)搜尋算法俗稱A星算法。這是一種在圖形平面上，有多個節(jié)點的路徑，求出最低通過成本的算法。常用于游戲中對象的移動計算上。A* 算法是一種啟發(fā)式搜尋算法，有別于DFS， BFS搜索。可以這樣理解“啟發(fā)式”的涵義，比如從起點A到達目的地B的路線，并不是直接告訴你，從A出發(fā)，向東行駛200米，右轉進入XX路，直行500米到達B；而是從A出發(fā)，直行，直到遇到第一家肯德基，右轉直到看到B大廈。而A*算法中用來啟發(fā)的線索就是移動成本，也就是權重。

3.1 移動成本

       如下圖所示，從A點出發(fā)，可以有四個方向可走（由于貪吃蛇僅僅可以走上下左右四個方向，所以這里不考慮走斜線的情況），假設每個方向移動一格的成本為10，A*算法中采用的F值來評價移動成本，F(xiàn)=G+H。假設節(jié)點C是待考察的一個點，G代表的是從起點A到C的移動成本，如下圖的情況G=10。那么H代表的就是從C點到目標B點的移動代價的預估值，如下圖的情況H=50，那么F=60。為什么說是預估，因為現(xiàn)在對于從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;//節(jié)點的x,y坐標 
 int y; 
 int G;//該節(jié)點的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;//該節(jié)點的父節(jié)點 
} 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; 
 
//根據(jù)指針所指向的節(jié)點的F值，按大頂堆進行調(diào)整 
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)//如果已經(jīng)在opentable中,但是不是最優(yōu)路徑 
  { 
   mapnode[x1][y1].G=pcurtnode->G+W;//把G值更新 
   mapnode[x1][y1].ParentNode=pcurtnode;//把該鄰點的雙親節(jié)點更新 
   //由于改變了opentable中一個點的F值，需要對opentable中的點的順序進行調(diào)整，以滿足有序 
   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個節(jié)點加入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已經(jīng)為空，即沒有找到路徑 
  { 
   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; 
}

另外有需要云服務器可以了解下創(chuàng)新互聯(lián)建站bm7419.com，海內(nèi)外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

網(wǎng)站標題：C語言手把手教你實現(xiàn)貪吃蛇AI（中）-創(chuàng)新互聯(lián)
文章起源：http://bm7419.com/article32/gjcsc.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、網(wǎng)站內(nèi)鏈、企業(yè)建站、網(wǎng)站收錄、響應式網(wǎng)站、關鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉載內(nèi)容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)