- 1:游戏规则
- 2:胜负判定
- 3:代码实现
- 3.1:machine_move 函数
- 3.2:check 函数
- 4:评测方法
- 5:提示
- 6:诚信要求
- 7:思路及问题
- 8:代码
- 9:最终成绩
贪吃蛇大作战——数据结构课程设计B题
游戏规则
游戏在一张二维地图上展开,地图上有蛇、墙和障碍物、道具、食物,如图 1 所示。蛇有 2 条:白蛇(□□□)和粉蛇(■■■),初始长度为 3 格。
食物由●表示。墙和障碍物由■ 表示。
道具分为两种:第 1 种为“倍速道具▲”,全场 1 个,吃该道具后,速度加倍,50 步后 恢复原速度;
第二种道具为“斜走道具★”,全场 2 个,正常情况下,蛇移动方向为上、下、 左、右 4 个方向,但吃该道具后,还可以斜着走,即上、下、左、右、上左、下左、上右、下 右 8 个方向都可以行进,该道具吃后永久有效。
蛇头碰到墙或障碍物、自己的身体、对方的身 体均被判定为死亡。
游戏每面(也可以称为关卡)随机放置 10 个食物。第一面只有食物没有障碍物和道具, 第二面开始出现随机放置的障碍物和道具。
胜负判定
先吃到 35 个食物的一方获胜,在此期间若任何一条蛇死亡,判对方获胜。
此外,若距任意一方吃到食物后 200 步内双方均未再吃到食物,则判超时,此时吃食物多的一方获胜,若两条蛇吃的食物一样多,则判为平局。
代码实现
老师提供程序框架和图形显示,学生只需按接口要求编写相关函数,实现操控贪吃蛇的核 心算法即可,无需负责图形显示。
实现语言为 C/C++,不限编译器与开发环境。
本题程序由命令行界面模拟图形界面,用命令行界面的 n+2 行 m+4 列二维网格表示游戏 地图,通过 printf(“■”)等画游戏地图中的一个点格。
这里需特别注意的是,由于“■”等特殊字 符在命令行中占 2 个字符的宽度,所以命令行的每 2 列对应游戏地图的 1 列。
综上,游戏地图 的坐标系如图 2 所示,其相邻两点的列坐标值相差 2 而不是 1。
例如图 2 中粉蛇由 3 个点组 成,其坐标分别为(3,6)、(3,4)、(3,2)。第 0 行、第 n+1 行、第 0 列、第 m+2 列为四周的墙。
你的任务是编写程序控制贪吃蛇,即根据当前的游戏地图和蛇的位置,做出决策,给出下一步贪吃蛇行进的方向,从而吃掉食物并躲避障碍物和对方。
为此你至少需要编写如下 2 个函数:
machine_move 函数
(后4个方向只有吃到斜走道具后才有效):
行进方向 |
下 |
右 |
左 |
上 |
下右 |
上右 |
上左 |
下左 |
数值 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
结构体GamePanel表示当前游戏地图。其定义如下:
struct GamePanel{ int n; //地图规模, 含义如上所示 int m; //地图规模, 含义如上所示 int success_num; //游戏获胜所需吃的食物数,默认为35 int totalfoodnum; //地图中的食物总数,每进入新的一面/关置10 int currentfoodnum; //当前地图中所剩食物数, 食物每被吃一个该值减1, 0 ≤ currentfoodnum ≤ totalfoodnum point food[20]; //地图中所有食物(food[0]......food[totalfoodnum-1] )的坐标 int wallnum; //地图中障碍物(不算四周的墙,只算地图内部的障碍物)总数 point wall[20]; //地图中所有障碍物(wall[0]......wall[wallnum-1] )的坐标 int speednum; //地图中倍速道具数, 第1面/关卡为0, 进入第2面值变为1, 被蛇吃掉后值变为0 int speedowner; //表示倍速道具的拥有者, 值为0或1; 若两方均未吃该道具, 则值等于-1 int step_speed; //玩家吃倍速道具后, 走的步数, 任意蛇吃该道具后置0, 此变量值不超过50 point speedprops; //当前地图中倍速道具的坐标 int obliquenum; //地图中斜走道具数, 第1面/关为0, 进入第2面值变为2 int obliqueowner[5]; //斜走道具的拥有者,obliqueowner[t]=1表示蛇t拥有斜走道具,等于0表示蛇t没吃斜走道具 point obliqueprops[2]; //当前地图中斜走道具的坐标 int panel[50][100]; //panel[i][j]的值为0,1,2,3,4分别表示地图中点[i, j]为空,食物,障碍物,倍速道具,斜走道具 };
check 函数
bool check(point snake[5][100], int len[5], int t, GamePanel gp, int direction )
该函数的功能是:判断在贪吃蛇当前位置和游戏地图下,下一步若以 direction 方向行进,是否 可行。
如可行则返回 true,如不可行(即按此方向前进会导致贪吃蛇死亡)则返回 false。
参数 中 snake、len、t、gp 的含义同(1),direction 表示下一步拟行进的方向,含义如表 1 所示。
这里需注意的是,当贪吃蛇能斜走的时候,类似图 3 的情形,贪吃蛇是不能向右上方通过 的,无论点格 1 和 2 是障碍物还是蛇自己或对方的身体。
但图 4 的情形贪吃蛇则可以向右上方 通过。其他方向同理。
评测方法
以比赛的方式进行评测,比赛分为两阶段,均为程序自动对战,老师提供评测程序,无需人工参与。
- ➢ 第一阶段:(1)每班内部采用双循环赛方式,即每名同学都与本班其他同学比赛 2 场,一场使用白蛇,一场使用粉蛇。如1个班有31人,则每人需进行60场比赛。胜一场得3分, 平一场得 1 分,负一场得 0 分。(2)循环赛后,依据积分排出每班的名次,积分相同则所 吃食物总数多者排名靠前。每班排名前 10%记 100 分,前 20%记 90 分,前 30%记 80 分, 前 50%记 70 分,前 70%记 60 分,前 80%记 50 分,前 90%记 40 分,剩余能正常编译运行 者记 30 分。若程序编译出错或无法正常运行,记 0 分。
- ➢ 第二阶段:诸神之战。第一阶段产生的各班冠军(计算机学院25个班,软件学院10个班) 共 25 人,再进行双循环赛,决出两院总冠军。第二阶段仅供娱乐,与本课程成绩无关。
- ➢ 所有比赛的对战记录均完全公开,将以附件2中rec文件的形式发布,大家可运行、播放, 看到自己每场比赛的比赛画面。
提示
本题没有标准答案,同学们可以充分发挥想象力给出自己的解法。
任何基础、任何层次 的学生都有能力给出解决方案。
只要程序无明显 bug,能正常编译运行,得分大于 0 分即可 及格。
你的程序只需给出蛇前进的方向,至于蛇按该方向前进后身体位置如何变化,将由老师的主程序负责处理,你无需考虑,你只需重点考虑蛇头的位置。
你需要考虑如何通过从蛇头到食物的最短路径,最快吃到食物。
当然如果仅考虑直线最 短路径,还不够,还需考虑障碍物和蛇身。
如图 5 所示的情况,如果你直接向上走,会碰到 自己。
再如图 6 的情况,当蛇吃掉食物后自己也就憋死了。
另外,当有多个食物和道具在你面前时,你如何抉择?如果你选择吃某一个,那么另一个 就会被对方得到。也许你要根据对方的位置进行抉择。
有的时候,道具也许是一把双刃剑,比 如斜走道具,由于方向的增加,可能会增加你编程的难度。而倍速道具也只能用 50 步。
当你吃的食物越多身体会越长,越难以控制。所以可能你所吃的食物数一直领先对方,但最后却由于自身太长难以控制而死亡,将胜利让给对方。
甚至可以思考能否采用一些主动攻击策略,比如把对方逼入死角等。
诚信要求
允许查阅资料、文献,但不允许照抄代码。
老师已经收集了网络上与本题相关的所有代码 作为查重对比母板,与网上代码或其他同学代码雷同者,均被视为抄袭。
修改变量名或函数名, 变换语句结构或函数位置等均无效。
抄袭者与被抄袭者双方通论,不做区分。任何形式的破解、 攻击及其他不正当竞争行为,包括在提交的代码中植入恶意代码等均视为作弊。
抄袭作弊者取消本题成绩并按情节轻重倒扣分。
思路及问题
首先,对于目标的确定,当有加速道具时,优先将加速道具作为目标,当没有加速道具时将最近的斜走道具作为目标,两种道具都没有的话就将最近的食物定作目标。
对于食物的寻找,计算每个点距离食物的欧几里得距离和曼哈顿距离的和,并从中选择最小的格子,从而达到和食物之间不断缩短距离的目的。
当初步完成了贪吃蛇的基本功能后,发现在蛇到达一定长度之后容易自己缠死自己,即出现蛇体呈一螺旋状导致蛇头前方是自己身体的情况。
在上网查询资料后发现可以使用BFS寻找到达尾巴的通路,若有通路,则代表蛇至少有一条路可以活下去,以此来避免自己缠死自己的情况。
当写完了BFS后,发现会报错Stack Overflow,而且是自己看不懂的界面(经上网查询资料后发现是汇编语言)。
在多方查询资料以及询问老师同学后发现在本题中用递归来写BFS会出现BUG,于是转换为while(栈非空)的形式,使用数据来模拟队列,两个整数head和rear来表示队头和队尾。
当其他基本功能全部做完后,我开始思考新的提升胜率的方法,在多次试验中,我发现有多次一条蛇无意间卡死另外一条蛇的情况,这给了我启发,于是我添加了Kill函数。Kill函数的思路与围棋很像,我们假设蛇头有九口气,当蛇头的上下左右四口气全部被堵死的时候,对方就无力翻天了。于是我按照这个思路设计了Kill函数,当对方的头仅有一口气(指上下左右四口)时,并且自己的蛇头刚好可以到达对方剩下的那口气的位置时,直接到达位置即可结束游戏,因为下一步对方必死。
既然我们可以击杀对面的蛇,那相对而言我们也会被击杀,于是有意识的回避危险就显得尤为重要了。于是我添加了Danger和Next_Death两个函数,用来判断上述与Kill相同的情况,只不过是以“受害者”的角度去考虑,要避免这种情况出现。
另外,在与同学讨论时,我得知了一个新的方法,那就是在第一面的时候,当吃够5个食物,也就是蛇的长度达到8时,可以紧紧围绕一个食物,这样比赛就会因为超时而结束,而对方只能吃到4个食物,也就是说只要我能够开始围住食物,那我就赢了,我将其扩展到了后几面,只要达成len[mine]>len[enemy]+FoodLeft-1的条件,在这时将食物围起来就是必胜局了。
代码
长度过长,若有需要可以下方评论
最终成绩
在班级比赛中获得了老二的好成绩(本来应该是100分但是因为马虎有个地方变量名没有改导致扣了5分。。。。不过第一名也是这个原因扣了五分[滑稽])
(我是11号)