智能寻路贪吃蛇

浅浅的花香味﹌ 2024-02-19 12:23 69阅读 0赞

初次探路出现的问题：[https://blog.csdn.net/helloworld\_cheng/article/details/50718719][https_blog.csdn.net_helloworld_cheng_article_details_50718719]

关于DFS与BFS：[https://blog.csdn.net/u011240016/article/details/59108307?utm\_source=blogxgwz6][https_blog.csdn.net_u011240016_article_details_59108307_utm_source_blogxgwz6]

关于智能蛇的思想：[https://www.cnblogs.com/ganhang-acm/p/5503848.html][https_www.cnblogs.com_ganhang-acm_p_5503848.html]

python贪吃蛇：[http://python.jobbole.com/84804/][http_python.jobbole.com_84804]

简单版python贪吃蛇：[https://www.cnblogs.com/infroad/p/9241267.html][https_www.cnblogs.com_infroad_p_9241267.html]

在网上参考了各大神的代码后,了解了BTS算法:  
要实现一定的智能,肯定就要用到相应的寻路算法.我采用的是最简单的宽度优先搜索的方式 (BFS算法)  
所以在具体的实现游戏之前,我们先来看一下BFS算法.  
该算法在<算法导论>中有详细解说,并给出了可行的伪代码,本系列的博文的重点不在于此,所以只是简单一说,然后给出代码.  
下面就给出一个例子来说明该算法的寻路过程  
(说明:我们将路径抽象化为一个二维数组,在二维数组中,我们用0表示未探索过的通路,用a表示探索过的通路,用1表示不通)  
具体到例子,比如说下面一个地图  
0 0 1 1  
1 0 0 0  
0 0 0 1  
1 1 0 0  
假设起始点为(0,0),终止点为(3,3),即从左下角到右下角..  
我们通过观察法得,最短的路径为:  
(0,0)->(0,1)->(1,1)->(2,1)->(2,2)->(3,2)->(3,3)  
下面我们就通过Bfs将该路径求出来,Bfs算法寻路过程如下所示(标蓝的字母是当前步骤搜索的节点):  
<0----->  
a 0 1 1  
1 0 0 0  
0 0 0 1  
1 1 0 0

<1----->  
a a 1 1  
1 0 0 0  
0 0 0 1  
1 1 0 0

<2----->  
a a 1 1  
1 a 0 0  
0 0 0 1  
1 1 0 0

<3----->  
a a 1 1  
1 a a 0  
0 a 0 1  
1 1 0 0

<4----->  
a a 1 1  
1 a a a  
a a a 1  
1 1 0 0  
<5----->  
a a 1 1  
1 a a a  
a a a 1  
1 1 a 0

<6----->  
a a 1 1  
1 a a a  
a a a 1  
1 1 a a

这样,经过7步,我们就能从起点搜索到终点了.  
然后,头文件:  
//Bfs.h  
//贪吃蛇基本寻路算法.  
  
\#ifndef BFS\_H\_H  
\#define BFS\_H\_H  
  
\#include <queue>  
using std::queue;  
  
struct XY  
\{  
int x;  
int y;  
\};  
  
class Bfs  
\{  
public:  
void InitBfs(bool \*\*chess,XY size);//初始化图.  
void CalcBfs(XY st,XY en);//计算Bfs路径.  
void EetBfs(XY st,XY en);//得到Bfs路径.  
void CalcQue(XY en);//计算队列.  
queue<XY> m\_que;  
private:  
bool \*\*m\_chess;//用矩阵表示的图.  
bool \*\*m\_visit;//节点是否被访问过.  
XY \*\*m\_parent;//每个访问过的节点的父节点.  
XY m\_size;//图的大小.  
  
\};  
  
\#endif //BFS\_H\_H  
下面就对Bfs类中的成员变量和函数做一下说明:  
m\_chess是一个二维数组,其中false表示通路,true表示不通,也就是我们要求最短路径的"地图"(跟前面的例子同理).  
m\_visit是一个跟m\_chess等大的数组,用来表示每个节点的访问情况.  
m\_parent用来表示每个节点的父节点,我们最终得到的路径就是通过该数组得出的.  
m\_size就是上面三个数组的尺寸了.  
还有一个公用队列m\_que用来存储最终求得的路径.  
InitBfs()函数用来初始化各个数组.  
ClacBfs是核心算法,通过该函数得到m\_parent数组.  
下面就来看一下Bfs.cpp源文件:  
\[cpp\] view plain copy  
//Bfs.cpp  
\#include "stdafx.h"  
\#include "Bfs.h"  
int dir\[4\]\[2\]=\{ \{0,1\},\{0,-1\},\{1,0\},\{-1,0\}\};  
  
void Bfs::InitBfs(bool \*\*chess,XY size)  
\{  
m\_size=size;  
m\_chess=new bool \*\[m\_size.x\];  
m\_visit=new bool \*\[m\_size.x\];  
m\_parent=new XY \*\[m\_size.x\];  
  
for(int i=0;i<m\_size.x;i++)  
\{  
m\_chess\[i\]=new bool \[m\_size.y\];  
m\_visit\[i\]=new bool \[m\_size.y\];  
m\_parent\[i\]=new XY \[m\_size.y\];  
\}  
for(int i=0;i<m\_size.x;i++)  
\{  
for(int j=0;j<m\_size.y;j++)  
\{  
m\_chess\[i\]\[j\]=\*((bool\*)chess+m\_size.y\*i+j);  
m\_visit\[i\]\[j\]=false;  
m\_parent\[i\]\[j\].x=-1;  
m\_parent\[i\]\[j\].y=-1;  
\}  
\}  
while(!m\_que.empty())  
m\_que.pop();  
\}  
  
void Bfs::CalcBfs(XY st,XY en)  
\{  
queue<XY> temque;  
m\_visit\[st.x\]\[st.y\]=true;  
temque.push(st);  
XY head,next;  
int quesize;  
  
while(!temque.empty())  
\{  
quesize=temque.size();  
while(quesize--)  
\{  
head=temque.front();  
temque.pop();  
if(head.x==en.x&&head.y==en.y)  
return;//已经达到目的了.  
for(int i=0;i<4;i++)  
\{  
next.x=head.x+dir\[i\]\[0\];  
next.y=head.y+dir\[i\]\[1\];  
if(next.x<0||(next.x>(m\_size.x-1))||  
next.y<0||(next.y>(m\_size.y-1))||  
m\_chess\[next.x\]\[next.y\])  
continue;  
if(!m\_visit\[next.x\]\[next.y\])  
\{  
m\_visit\[next.x\]\[next.y\]=1;  
temque.push(next);  
m\_parent\[next.x\]\[next.y\].x=head.x;  
m\_parent\[next.x\]\[next.y\].y=head.y;  
\}  
\}  
\}  
\}  
\}  
  
void Bfs::CalcQue(XY en)  
\{  
if(en.x!=-1&&en.y!=-1)  
\{  
CalcQue(m\_parent\[en.x\]\[en.y\]);  
m\_que.push(en);  
\}  
\}  
  
void Bfs::EetBfs(XY st,XY en)  
\{  
CalcBfs(st,en);  
CalcQue(en);  
m\_que.pop();//弹出没用的起始点..  
\}

需要说明的一点是Dir数组,该数组表示的是上下左右四个方向.  
只要看过算法导论的BFS算法部分,其他的地方就非常好理解了,所以不多说了.下面我们就将该算法应用到我们的游戏中..

首先,我们可以设置一个变量,用来标记到底是人在玩还是电脑在玩,并在适当的地方更新这个值..

下一个问题是,怎样得到m\_chess数组呢?  
其实很简单,除了蛇的身体,剩下的部分都是通路,所以通过如下代码,我们就能得到m\_chess了  
\[cpp\] view plain copy  
bool maze\[15\]\[25\];  
memset(maze,0,sizeof(maze));  
list<SnakeNode>::iterator iter=m\_snake.m\_snake.begin();  
for(unsigned i=0;i<m\_snake.m\_snake.size();i++,iter++)  
\{  
XY curpo;  
curpo.y=iter->rc.left/m\_po.x;  
curpo.x=(iter->rc.top-50)/m\_po.y;  
maze\[curpo.x\]\[curpo.y\]=1;  
\}

至于起始点和终点就更简单了,起始点就是蛇头,终点就是食物..  
所以我们可以编写这样一个函数,用来得到路径:  
\[cpp\] view plain copy  
void CSnakeDlg::SetDire()  
\{  
XY size;  
size.x=15;  
size.y=25;  
bool maze\[15\]\[25\];  
memset(maze,0,sizeof(maze));  
list<SnakeNode>::iterator iter=m\_snake.m\_snake.begin();  
for(unsigned i=0;i<m\_snake.m\_snake.size();i++,iter++)  
\{  
XY curpo;  
curpo.y=iter->rc.left/m\_po.x;  
curpo.x=(iter->rc.top-50)/m\_po.y;  
maze\[curpo.x\]\[curpo.y\]=1;  
\}  
  
RECT rect=m\_snake.m\_snake.back().rc;  
XY st;  
st.y=rect.left/m\_po.x;  
st.x=(rect.top-50)/m\_po.y;  
XY en;  
en.y=m\_food.left/m\_po.x;  
en.x=(m\_food.top-50)/m\_po.y;  
m\_bfs.InitBfs((bool\*\*)maze,size);  
m\_bfs.EetBfs(st,en);  
\}  
在每次吃到食物以后,我们就重新执行一下这个函数,用来得到新的路径.  
得到路径之后,我们在OnTimer()函数中添加如下代码即可自动地改变贪吃蛇的移动方向了..  
\[cpp\] view plain copy  
if(m\_ispc)  
\{  
XY cur=m\_bfs.m\_que.front();  
m\_bfs.m\_que.pop();  
  
RECT rc=m\_snake.m\_snake.back().rc;  
XY head;  
head.y=rc.left/m\_po.x;  
head.x=(rc.top-50)/m\_po.y;  
if(cur.x==head.x)  
\{  
if(cur.y-head.y==1)  
m\_dr=DR\_RIGHT;  
else if(cur.y-head.y==-1)  
m\_dr=DR\_LEFT;  
\}  
else if(cur.y==head.y)  
\{  
if(cur.x-head.x==1)  
m\_dr=DR\_DOWN;  
else if(cur.x-head.x==-1)  
m\_dr=DR\_UP;  
\}  
\}

这样,贪吃蛇就可以欢快的吃一段时间的食物了..  
但是,过一段时间后,可爱的小蛇就自己撞墙死了,跟第一篇博文中贴出来的那只蛇相比,一点都不高大上..  
我总结了一下,目前来说这只蛇还有两个很大的问题:

1.由于每次都是吃到食物之后才执行一下Bfs函数,所以,得到的路径就是那一瞬间的最短路径,但是可能在蛇移动的过程中,当前的格局发生了变化,可能会有更短的路径出现,虽然这个问题不是致命的,但是也浪费了蛇吃东西的时间.  
2.随着蛇身的增长,蛇的身体很可能将地图分为互不相通的几个部分,所以,当食物和蛇的头部出现在不同的部分时,Bfs算法就没辙了,这个问题是致命的!

OK,智障蛇死了......  
\---------------------  
原文：https://blog.csdn.net/mrzhangxx/article/details/78926589?utm\_source=copy

[https_blog.csdn.net_helloworld_cheng_article_details_50718719]: https://blog.csdn.net/helloworld_cheng/article/details/50718719
[https_blog.csdn.net_u011240016_article_details_59108307_utm_source_blogxgwz6]: https://blog.csdn.net/u011240016/article/details/59108307?utm_source=blogxgwz6
[https_www.cnblogs.com_ganhang-acm_p_5503848.html]: https://www.cnblogs.com/ganhang-acm/p/5503848.html
[http_python.jobbole.com_84804]: http://python.jobbole.com/84804/
[https_www.cnblogs.com_infroad_p_9241267.html]: https://www.cnblogs.com/infroad/p/9241267.html