手把手教你實現貪吃蛇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; }以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。
新聞熱點
疑難解答
圖片精選
