C语言-手把手教你写贪吃蛇AI(中)

一时失言乱红尘 2022-10-01 04:44 180阅读 0赞

**1. 目标**

这一部分主要是讲解编写贪吃蛇AI所需要用到的算法基础。

**2. 问题分析**

贪吃蛇AI说白了就是寻找一条从蛇头到食物的一条最短路径，同时这条路径需要避开障碍物，这里仅有的障碍就是蛇身。而A star 算法就是专门针对这一个问题的。在A star 算法中需要用到排序算法，这里采用堆排序（当然其他排序也可以），如果对堆排序不熟悉的朋友，请移步到这里——[堆排序][Link 1]，先看看堆排序的内容。

**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点。

![Center][]

3.2 算法流程图

![Center 1][]

**4. 源代码**

代码中假定起始点A(5,10)，食物B(5,15)，如下图。其中‘X’代表障碍物，‘O’代表的就是寻找到的从A到B的路径。

![Center 2][]

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

[Link 1]: http://blog.csdn.net/kuweicai/article/details/54710409
[Center]: /images/20220705/2052e0d88bb544efacbd35f6dafc6db3.png
[Center 1]: /images/20220705/f7c93273476e4f15a41d90a9726188bd.png
[Center 2]: /images/20220705/0db450766a69497fbf4c5ec83af1634b.png