“Let us go！！！ ”
前言
这是我上学期的大作业，要求是用easyx去开发一个贪吃蛇游戏，这个项目本身的难度是不大的，再不依靠ai的情况下也能很快写完，但是后续我给它加了几个有意思的小功能，便是加入能寻找最佳路径的机器人小蛇，随机地图并且支持了双人，甚至加上ai可以实现无数多人的 但是说到底有意义去分享的只有这个寻路算法，底层思想是树和递归
–
正文
其实自己创建一个ai小蛇类，让它不断判断最佳路径，要求步数最少并且不会把自己绕进死路，由于地图是不规则并且玩家的干扰，这并不是一件很简单的事，这里先讲一下我首先想到的最为简单的方法
假如食物在蛇左下方，那就先向左与食物同一列，然后再向下吃到食物 假如食物在蛇右上方，那就先向右与食物同一列，然后再向上吃到食物
这个思路好像很清晰，但由于地图会绕出一部分死路，很容易就造成两种情况
- ai小蛇撞到玩家小蛇直接死亡
- 比如食物在正下方但是有墙堵着
我其实是加了一个保护机制，如果蛇本身预定的路线可能会死亡，那就会强行改变为不会出现死路的方向，但是，没错还有但是，这种机制下ai小蛇在遇到很多情况都会出现原地打转，保护机制告诉它一定要向右，但是寻路机制马上又把它带回来， 周而复始，到这里我也发现了，如果要让小蛇实现在不同复杂的地形都能找到正确的路，要不只能通过大量的if语句。要不只能每次都计算完整的最佳路径保证两种机制的平衡
接下来的思路的灵感来源于过河卒和贪心算法，方法主要是四叉树的遍历和递归
贪心算法总结一下便是每一次都选择最优的情况那么最后的结果就是最优的情况，过河卒这里不另做介绍，因为下面便是它的变形
假设地图由一张字符二维表构成，蛇头为’@’，墙壁为’#’，蛇身为’=’，食物为’*’
我们首先来分析一下，我们的起始点就是@，目标是*，中间要避开=和#，那么我们就在创建一个int形的二维数组，@的位置设置为1，=和#设置为-1，其他位置初始化为0，第一次给1周围相邻的四个格子设置为1+1=2,第二次就给这四个格子相连的格子赋值为2+1=3，已经赋值过的不再一次赋值， 周而复始 前言
这是我上学期的大作业，要求是用easyx去开发一个贪吃蛇游戏，这个项目本身的难度是不大的，再不依靠ai的情况下也能很快写完，但是后续我给它加了几个有意思的小功能，便是加入能寻找最佳路径的机器人小蛇，随机地图并且支持了双人，甚至加上ai可以实现无数多人的 但是说到底有意义去分享的只有这个寻路算法，底层思想是树和递归
–
正文
其实自己创建一个ai小蛇类，让它不断判断最佳路径，要求步数最少并且不会把自己绕进死路，由于地图是不规则并且玩家的干扰，这并不是一件很简单的事，这里先讲一下我首先想到的最为简单的方法
假如食物在蛇左下方，那就先向左与食物同一列，然后再向下吃到食物 假如食物在蛇右上方，那就先向右与食物同一列，然后再向上吃到食物
这个思路好像很清晰，但由于地图会绕出一部分死路，很容易就造成两种情况
ai小蛇撞到玩家小蛇直接死亡
比如食物在正下方但是有墙堵着
我其实是加了一个保护机制，如果蛇本身预定的路线可能会死亡，那就会强行改变为不会出现死路的方向，但是，没错还有但是，这种机制下ai小蛇在遇到很多情况都会出现原地打转，保护机制告诉它一定要向右，但是寻路机制马上又把它带回来， 周而复始，到这里我也发现了，如果要让小蛇实现在不同复杂的地形都能找到正确的路，要不只能通过大量的if语句。要不只能每次都计算完整的最佳路径保证两种机制的平衡
接下来的思路的灵感来源于过河卒和贪心算法，方法主要是四叉树的遍历和递归
贪心算法总结一下便是每一次都选择最优的情况那么最后的结果就是最优的情况，过河卒这里不另做介绍，因为下面便是它的变形
假设地图由一张字符二维表构成，蛇头为’@’，墙壁为’#’，蛇身为’=’，食物为’*’
我们首先来分析一下，我们的起始点就是@，目标是*，中间要避开=和#，那么我们就在创建一个int形的二维数组，@的位置设置为1，=和#设置为-1，其他位置初始化为0
第一次给1周围相邻的四个格子设置为1+1=2,第二次就给这四个格子相连的格子赋值为2+1=3，已经赋值过的不再一次赋值周而复始，这个数值的含义是从出发点到所在点位需要的最少步数-1
到这里相信大家也有了一点眉目，我们首先确定了食物所在位置对应的二维数组数值为13，蛇头的位置为1，那么最短路径即为从1->13依次增加的路线，如下图
OK到这里也是我们一个大致的思路已经成行了。第一步初始化二维数组，第二步依次找到最佳路径。下面我们便来具体实现一下这两个功能
给二维数组赋值
这一步就是根据上述说的规则进行第一次初始化-1,0,1，然后我们利用递归，具体的思路为
创建一个if语句，如果将要赋值的地方已经被赋值过，那么就跳过并return这次操作，下面我简写为赋值判断
我们首先给1直接相邻的四个格子赋值为2，然后这个四个格子分别给他们直接相邻的四个格子赋值为3,这里同样要进行上述的if语句判断，这四个格子还没有进行赋值判断，这里如何去赋值是第一个难点了，我采用的是递归的方法
我们首先给这个函数传一个值，这个值是需要给它周围格子赋值的坐标，比如说我已经给（1,1）这个格子赋了值，我需要把它周围的格子赋值，那么我就传入（1,1）这个坐标，然后再给周围的格子加一赋值
- 我这里还提供一个比较巧妙的方法，由于递归的性能并不是很好，我在其中加入一个全局变量map<int,int>容器，下面我们称为m1
我们首先把蛇头的位置丢进去，然后创建一个函数，下面我成为f1，创建一个临时map<int,int>容器，下面我们称为m2
先遍历m1，每得到一个坐标那就把它周围的格子赋值+1，并把这个格子记录在m2，直到遍历完，我们删除m1里面的全部数据,然后把m2的数据全部交给m1，然后在下一次调用这个函数的时候，又可以对新的格子赋值。
我们可以另起一个函数为initarray,利用while(true)来不断调用f1，直到食物所在位置被赋值过，即不为0就退出循环
至此我们需要的数据已经初始化完成，有些格子可能还没有被初始化，但是由于节约性能，这些格子并没有实际意义并且不影响我们后续的操作，当然全部初始化也是完全没有问题的。
寻路
我们再来回顾一下接下来要做的事。假如食物的位置数值为14，那么我们需要找到一条路，这条路必须从1->14依次递增，保证是最短路径
这里为了好理解我讲解四叉树的做法，可能名字有点吓人但是后续的思路真的很简单，我们接着往下说
首先创建一个四叉树的类，这里不作过多讲解，四个子节点分别代表向上，向左，向下，向右。
将蛇头的位置初始化为这颗树的根结点，给它周围的格子比它大一添加到这颗树上，直到食物所在格子被加到了这颗树上，创建树结束
为了更好的性能，我们来从叶节点来倒推到根节点，把这个中间遍历过的格子坐标填加到stack中，由于它先进后出的特性，我们只需要把这个容器的数据依次读出，便是从蛇头到食物的最佳路径
总结
好了这就是我对这个寻路算法的大致介绍，因为c++极高的效率，我上面的逻辑去不断寻路对游戏流畅度影响可以忽律不计（我测试过让ai小蛇自己迅速移动，似乎感受不到这个算法耗时了哈哈哈），代码我并没有详细列出来，后续我会上传源码到网盘，我的完整版本有easyx界面，和高度自定义的游戏难度，有兴趣可以下载试玩一下
