Chinaunix首页 | 论坛 | 博客
  • 博客访问: 153367
  • 博文数量: 83
  • 博客积分: 2571
  • 博客等级: 少校
  • 技术积分: 701
  • 用 户 组: 普通用户
  • 注册时间: 2010-01-19 15:04
个人简介

重新开始,做回自我,爱拼的男人最牛!

文章分类
文章存档

2020年(1)

2019年(17)

2014年(1)

2011年(1)

2010年(63)

我的朋友

分类: C/C++

2019-12-06 16:59:22

本文链接:https://blog.csdn.net/kuweicai/article/details/60780693

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

1. 目标
        编写一个贪吃蛇AI,也就是自动绕过障碍,去寻找最优路径吃食物。
2. 问题分析
        为了达到这一目的,其实很容易,总共只需要两步,第一步抓一条蛇,第二步给蛇装一个脑子。具体来说就是,首先我们需要有一条普通的贪吃蛇,也就是我们常玩儿的,手动控制去吃食物的贪吃蛇;然后给这条蛇加入AI,也就是通过算法控制,告诉蛇怎么最方便的绕开障碍去吃食物。为了讲清楚这个问题,文章将分为三部分:上,写一个贪吃蛇程序;中,算法基础(需要运用到什么算法);下,运用算法基础中的算法编写一个贪吃蛇AI。
        在动手写贪吃蛇之前,我们需要想清楚以下几个问题,就非常容易了:
        a. 蛇身。由于蛇在吃食物的过程中会不断的长大,所以很适合用单链表表示,并且吃食物的过程就是用头插法插入元素的过程
        b. 食物。食物直接用随机生成函数,随机生成食物,但是需要检查,所生成的食物的位置不可以和蛇身重合
        c. 显示。我们需要实时的显示出蛇身的移动,但事实上,我们不用每次都打印整个蛇身,因为蛇身每走一步,仅仅是蛇头和蛇尾的位置移动一格,其他的地方都没有变化,所以只需要打印一个新的蛇头,并把蛇尾的位置抹掉,那么视觉效果就是蛇身先前移动了一格,这个过程中,我们需要用到SetConsoleCursorPosition(),将光标移到到指定的位置(比如蛇尾),完成相应的操作(比如打印空格抹掉蛇尾)
        d.控制。我们需要用键盘来控制蛇身的移动,这个程序中是利用上下左右方向键来实现的,这里需要用到GetAsyncKeyState(),来实时监测按键的状态

3. 运行效果


4. 源代码
        总共由三个文件组成gluttonous.h,source.c & main.cpp。由于这个贪吃蛇是用于后面加AI,所以并没有加入一些错误检测,比如是否撞到边界,是否撞到蛇身等。
需要注意的是,这个程序中用到了比较特殊的字符('■')来表示游戏空间的边界,在VS2013中可以正常编译,但是在codeblock中会乱码。
        另外还有一点容易混淆的是,我们通常都是用(x,y)坐标表示第x行,第y列,但是在SetConsoleCursorPosition(x,y)中,表示把光标移动到第y行,第x列

4.1 gluttonous.h

#ifndef SNAKE_H_
#define SNAKE_H_
#include
#include //SetConsoleCursorPosition, sleep函数的头函数
#include //time()的头函数
#include //malloc()的头函数
#define N 32 //地图大小
#define snake_mark '#'//表示蛇身
#define food_mark '$'
#define sleeptime 500
 
/*表示蛇身坐标的结构体*/
typedef struct SNAKE{
int x; //行坐标
int y; //列坐标
struct SNAKE* next;
}snake_body, *psnake;
extern psnake food;
 
typedef enum Direction{
U,D,L,R} direction;//蛇头的朝向
extern direction snake_direction;
 
void set_cursor_position(int x, int y);
void initial_map();
psnake initial_snake();
void create_food(psnake snake,psnake food);
void printe_map(psnake snake, psnake food);
int is_food(psnake snake_head, psnake food);
int is_boundary(psnake snake_head, psnake food);
int is_snakebody(psnake snake_head, psnake food);
psnake snake_move(psnake sanke, psnake food);
void control_snake();
#endif

4.2 source.cpp

#include"gluttonous.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
{
set_cursor_position(2*i, 0);
printf("■");
set_cursor_position(2*i, N/2+1);
printf("■");
}
for (i = 0; i
{
set_cursor_position(0, i);
printf("■");
set_cursor_position(N+2, i);
printf("■");
}
}
 
/*初始化蛇身*/
/*蛇身初始化坐标为(5,8),(4,8), (3,8) */
psnake initial_snake()
{
int i=5;//列
int j = N / 4;//行
psnake snake = NULL, tsnake = NULL, temp = NULL;
 
snake = (psnake)malloc(sizeof(snake_body));
(snake)->x = i;
(snake)->y = j;
(snake)->next = NULL;
tsnake = snake;
 
for (i = 4; i >2; i--)
{
temp = (psnake)malloc(sizeof(snake_body));
(temp)->x = i;
(temp)->y = j;
(temp)->next = NULL;
(tsnake)->next = (temp);
(tsnake) = (tsnake)->next;
}
return snake;
}
 
void create_food(psnake snake, psnake food)
{
static int i=1;
psnake head = snake;
srand((unsigned)time(NULL));
food->x = rand() % N + 2;
food->y = rand() % (N/2) + 1;
 
//检查食物是否和蛇身重回
while (head)
{
if (head->x == food->x && head->y == food->y)
{
free(food);
food = NULL;
create_food(snake,food);
}
else
{
head = head->next;
}
}
}
 
void printe_map(psnake snake, psnake food)
{
psnake temp=snake;
while (temp)
{
set_cursor_position(temp->x, temp->y);
printf("%c",snake_mark);
temp = temp->next;
}
if (food)
set_cursor_position(food->x,food->y );
printf("%c",food_mark);
set_cursor_position(0, N/2+2);
}
 
//判断是否吃到食物,吃到食物返回 1,否则返回 0;
int is_food(psnake snake_head, psnake food)
{
if (snake_head->x == food->x && snake_head->y == food->y)
return 1;
return 0;
}
 
//判断是否撞到墙,撞到墙返回 1,否则返回 0;
int is_boundary(psnake snake_head)
{
if (snake_head->y <= 0 || snake_head->y >= N / 2 + 1 || snake_head->x <= 1 || snake_head->x >= N + 1)
return 1;
return 0;
}
 
//判断是否撞到自己,撞到自己返回 1,否则返回 0;
int is_snakebody(psnake snake_head)
{
psnake temp=snake_head->next;
while (temp)
{
if (snake_head->x == temp->x && snake_head->y == temp->y)
return 1;
else
temp = temp->next;
}
return 0;
}
 
//将蛇身移动到合适的位置,并打印出来
psnake snake_move(psnake snake, psnake food)
{
psnake snake_head = (psnake)malloc(sizeof(snake_body));
if (snake_direction == U)
{
snake_head->y = snake->y-1;
snake_head->x = snake->x;
snake_head->next = snake;
}
else if (snake_direction == D)
{
snake_head->y = snake->y + 1;
snake_head->x = snake->x;
snake_head->next = snake;
}
else if (snake_direction == L)
{
snake_head->y = snake->y;
snake_head->x = snake->x - 1;
snake_head->next = snake;
}
else if (snake_direction == R)
{
snake_head->y = snake->y;
snake_head->x = snake->x + 1;
snake_head->next = snake;
}
 
if (is_food(snake_head, food))//如果是食物
{
create_food(snake_head, food);
printe_map(snake_head, food);
}
else if (is_boundary(snake_head) == 0 && is_snakebody(snake_head) == 0)//不是食物,不是边界,也不是蛇身
{
psnake temp = snake_head;
while (temp->next->next)//寻找蛇尾
{
temp = temp->next;
}
set_cursor_position(temp->next->x, temp->next->y);
printf(" ");//把蛇尾用空格消掉
free(temp->next);//释放蛇尾的内存空间
temp->next = NULL;//将temp的next置成NULL
printe_map(snake_head, food);
}
else
{
free(snake_head);
snake_head = NULL;
}
return snake_head;
}
 
void control_snake()
{
if (GetAsyncKeyState(VK_UP) && snake_direction != D)
{
snake_direction = U;
}
else if (GetAsyncKeyState(VK_DOWN) && snake_direction != U)
{
snake_direction = D;
}
else if (GetAsyncKeyState(VK_LEFT) && snake_direction != R)
{
snake_direction = L;
}
else if (GetAsyncKeyState(VK_RIGHT) && snake_direction != L)
{
snake_direction = R;
}
}


4.3 main.cpp
#include"gluttonous.h"
direction snake_direction;
psnake food;
 
int main(void)
{
psnake snake;
 
initial_map();
snake=initial_snake();
food = (psnake)malloc(sizeof(snake_body));
food->next = NULL;
create_food(snake, food);
printe_map(snake, food);
snake_direction = R;
while (1)
{
Sleep(sleeptime);
control_snake();
snake=snake_move(snake, food);
}
return 0;
}



C语言-手把手教你写贪吃蛇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
#include
#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         for(j=0;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;



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

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

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


        运行效果如下:


    

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

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


a. snake AI.h


#ifndef SNAKE_H_
#define SNAKE_H_
#include
#include //SetConsoleCursorPosition, sleep函数的头函数
#include //time()的头函数
#include //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


2. 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 {
set_cursor_position(2 * i, 0);
printf("■");
set_cursor_position(2 * i, N / 2 + 1);
printf("■");
}
for (i = 0; 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 = 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是当前点坐标
//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();
}
}
}


3. 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;
}


————————————————
版权声明:本文为CSDN博主「kuweicai」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/kuweicai/article/details/69487351





阅读(110) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册