贪吃蛇c++程序(A*算法自动追踪功能)

2021/12/31 14:07:29

本文主要是介绍贪吃蛇c++程序(A*算法自动追踪功能),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

一、摘要

二、概述

三、方法论证和比较

1、方案一:深度学习算法

2、方案二:广度优先搜索算法

3、方案三:A*算法

四、理论分析即代码

 1、贪吃蛇的设计流程图

2、初始化地图算法

3、利用键盘控制蛇的移动

4、食物的生成

6、 贪吃蛇的自动追踪算法


一、摘要

       贪吃蛇是一款简单益智类的大众小游戏,自诞生以来,深受广大玩家喜爱。此次设计传统的贪吃蛇小游戏,将应用所学的理论知识解决一些复杂的工程问题:通过利用键盘的方向键控制蛇的移动,实现简单的贪吃蛇基本功能。同时,贪吃蛇的复杂度较低,算法编写上比较友好。

       在算法实现方面,我们通过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() 函数的功能:执行挂起一段时间,也就是等待一段时间再继续执行,可以理解为暂停了),这样使得在打印的过程中造成一种炫酷的打印效果。

 

初始化地图程序截图2

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

利用键盘控制蛇的移动3

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

蛇撞墙后死亡图2

6、 贪吃蛇的自动追踪算法

 1.把起始格添加到开启列表。
 2.重复如下的工作:
      a) 寻找开启列表中距离食物最近的。我们称它为当前格。
      b) 把它切换到关闭列表。
      c) 对相邻的8格中的每一个
          * 如果它不可通过或者已经在关闭列表中,略过它。反之如下。
          * 如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
          * 如果它已经在开启列表中,用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序,改变之后你可能需要重新对开启列表排序。

      d) 停止,当以下两种情况之一出现
          * 把目标格添加进了关闭列表(注解),这时候路径被找到
          * 没有找到目标格,开启列表已经空了。这时候,路径不存在。
   3.保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。这就是你的路径。

自动追踪算法图1

自动追踪算法图2

自动追踪算法图3

需要源程序的可以关注评论我 我会给大家邮箱的形式发送~



这篇关于贪吃蛇c++程序(A*算法自动追踪功能)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程