贪吃蛇c++程序（A*算法自动追踪功能）
需要源程序的可以关注评论我 我会给大家邮箱的形式发送~
目录
一、摘要
贪吃蛇是一款简单益智类的大众小游戏，自诞生以来，深受广大玩家喜爱。此次设计传统的贪吃蛇小游戏，将应用所学的理论知识解决一些复杂的工程问题：通过利用键盘的方向键控制蛇的移动，实现简单的贪吃蛇基本功能。同时，贪吃蛇的复杂度较低，算法编写上比较友好。
在算法实现方面，我们通过C++来实现贪吃蛇的单人对战、人机对战等功能；采用了A*算法用以实现AI蛇的自动追踪。
关键词：贪吃蛇 自动追踪 A*算法 C++
二、概述
贪吃蛇游戏
按照如下步骤实现：
•初始化地图。
•通过键盘控制蛇运动方向，注意重新设置运动方向操作。
•制造食物。
•让蛇移动，如果吃掉食物就重新生成一个食物，如果会死亡就break。
•Sleep(200)暂停200毫秒之后在进行上面的。
•进阶: 为该游戏开发外挂.外挂不能读取玩家无法正常得到的信息.
要求：
•界面友好，函数功能要划分好
•总体设计应画一流程图
•程序要加必要的注释
•要提供程序测试方案或无bug运行
三、方法论证和比较
1、方案一：深度学习算法
考虑到对深度学习有一定基础了解且深度学习是一个比较热门的AI编写方式，最初预备采用深度学习为主要方式。然而查阅资料后，我们发现深度学习对编写者要求十分高。无论是模型的建立还是模型的超参数优化，对没有相关经验的我们来算，难以完成。最终放弃此方案。
2、方案二：广度优先搜索算法
广度优先搜索算法是贪吃蛇自动追踪的一个常用算法。算法可以编写得简单完成，因此可以令我们根据自身能力，选择算法的复杂程度，调节AI的难度。并且算法的逻辑相对来说容易理解，使得我们可以在查阅资料上更为轻松，也使得我们对于算法的理解更为透彻。
3、方案三：A*算法
在A*算法实现中，搜索区域被划分成了方形网格。像这样，简化搜索区域，是寻路的第一步，把搜索区域简化成了一个二维数组。数组的每一个元素是网格的一个方块，方块被标记为可通过的和不可通过的。路径被描述为从A到B经过的方块的集合（即蛇头到食物的距离）。一旦路径被找到，贪吃蛇就从一个方格的中心走向另一个，直到到达目的地。
四、理论分析即代码
1、贪吃蛇的设计流程图
单人对战贪吃蛇流程图
2、初始化地图算法
首先我们会给界面和地图的做一个长度和宽度的规划。
初始化地图程序截图1
地图的显示可以用二维数组来进行存储打印，也可以用光标循环的定位来打印显示。确定好墙的长宽，通过for循环，在相应的控制台坐标上一个一个打印出“▓”，最终构成墙。在循环打印的过程中我加入了Windows.h 里的Sleep() 函数（Sleep() 函数的功能：执行挂起一段时间，也就是等待一段时间再继续执行，可以理解为暂停了），这样使得在打印的过程中造成一种炫酷的打印效果。
3、利用键盘控制蛇的移动
在设计过程中，优先完成了与蛇相关的部分，最后完成界面还原。设想并实现使用W A S D这四个键进行上下左右的控制而用Z键来作为蛇暂停的标志。具体过程为：用getch()来获取输入的字符，再用if对其进行判断，相比之下更容易实现上下左右控制以及暂停。但是我觉得在大多数情况下，一个简单的贪吃蛇的移动如果用“↑ ↓ ← →”这4个方向键，以及空格键暂停，会更符合大部分用户的习惯，但前面也提到了getch()获取方向键需要按两下，这肯定是不行的。因此在做界面的时候就了解到了Windows API中的GetAsyncKeyState函数，这个可以通过按一次键识别“↑ ↓ ← →”这4个方向键和空格键的函数（GetAsyncKeyState（VK_UP）、GetAsyncKeyState（VK_DOWN）、GetAsyncKeyState（VK_LEFT）、GetAsyncKeyState（VK_RIGHT）、GetAsyncKeyState（VK_SPACE）分别是获取这五个键的函数）。然而在游戏中蛇需要保存他目前所前进的方向，而GetAsyncKeyState函数的返回值只能为1或者0不能获取方向。而当用户按下空格时GetAsyncKeyState（VK_SPACE）返回值为1，立即进入暂停界面。
利用键盘控制蛇的移动1
移动的本质就是不断在头部生成一个新的头，然后删除尾部。定义一个新的蛇头，获取原来蛇头的坐标，将蛇头的坐标加上2或者1（因为在实际操作中发现 控制台的长宽1个单位的长度是不一样的。所以当蛇往左或者往有移动时需要对x加减2，而向上或者向下移动时对y加减1）,并把新的蛇头的next指向原来的蛇头同时打印出来，接着再遍历整个蛇的链表进行打印，当循环到原来蛇尾的时候，把其所在的位置打印为空格，这样就相当于尾部也往前走了一格。同时释放掉尾部，并把原来尾部的上一个结点作为新的尾部，并令其next=NULL ；这样也就实现了蛇的移动。
利用键盘控制蛇的移动2
4、食物的生成
可想而知，食物的生成是有随机性的。如果单纯的连续在某个地方按照一定规律进行食物的生成的，那么游戏的可玩性和乐趣性将会被降低，用户的体验也会极差，所以随机生成果实是非常有必要的。为达到这个目的运用到了#include<stdlib.h>中的rand()随机函数（rand函数不是真正的随机数生成器，而srand()会设置供rand()使用的随机数种子。如果你在第一次调用rand()之前没有调用srand()，那么系统会为你自动调用srand()。而使用同种子相同的数调用 rand()会导致相同的随机数序列被生成。因此还需要与#include<time.h>配套使用会增加随机的成功度）。运用rand()函数对过时的x,y进行随机生成。在生成过程中还要注意到果子的生成位置是否合理（不能生成在蛇身和墙壁上），因此我们在生成时要将其x，y与蛇身进行匹配（从蛇头到蛇尾对其进行遍历直到匹配成功或者到达蛇尾结束遍历），如果不满足规范，将会重新生成，直至到其合理位置。所以这个生成应该改放在永真循环里面，符合条件才跳出。此处无需控制和墙进行匹配，因为在随机生成时，已经对其进行了控制，rand()函数对长减4取模宽减2取模（保证不产生在右墙和下墙碰撞）再将得到的余数+1（目的是为了不让其为0，也就是不让果子产生在上墙和左墙），生成过程中还要注意生成的果子的列必须为偶数，不然会使得蛇吃到果子时，一半被吃，一半没被吃。最后注意的点是生成前要对果子是否存在进行判断，如果果子存在的话，就无需进行生成果子的操作。
随机食物图1
随机食物图2
5、判断蛇死亡算法
对于任何贪吃蛇游戏而言当蛇撞墙或者是咬到自己的时候，都会死亡，同时进入死亡界面。为了判定蛇时如何死亡的，我定义了一个整型变量gameover;作为蛇死亡方式的标记。（蛇咬到自己死亡gameover赋值为1，蛇撞墙死亡gameover赋值为2）。这样在进入死亡界面的时候根据gameover的不同值进而显示不同的提示语进而告知用户蛇死亡的方式。
蛇咬到自己死亡图1
6、 贪吃蛇的自动追踪算法
1.把起始格添加到开启列表。
2.重复如下的工作：
a) 寻找开启列表中距离食物最近的。我们称它为当前格。
b) 把它切换到关闭列表。
c) 对相邻的8格中的每一个
* 如果它不可通过或者已经在关闭列表中，略过它。反之如下。
* 如果它不在开启列表中，把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
* 如果它已经在开启列表中，用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样，就把这一格的父节点改成当前格，并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序，改变之后你可能需要重新对开启列表排序。
d) 停止，当以下两种情况之一出现
* 把目标格添加进了关闭列表(注解)，这时候路径被找到
* 没有找到目标格，开启列表已经空了。这时候，路径不存在。
3.保存路径。从目标格开始，沿着每一格的父节点移动直到回到起始格。这就是你的路径。
自动追踪算法图1
自动追踪算法图2
自动追踪算法图3