Jiahonzheng's Blog

智能贪吃蛇

字数统计: 1.1k阅读时长: 3 min
2017/12/25 Share

接着上一篇字符游戏-贪吃蛇,本篇博客介绍如何实现智能贪吃蛇,即贪吃蛇 AI。

游戏代码:Greedy-Snake

运行环境: Linux (后期会加入 Mac、Windows 支持)

VT100 控制码编程

VT100 是一个终端类型定义,VT100 控制码是用来在终端扩展显示的代码,比如在终端上任意坐标用不同的颜色显示字符、清屏、修改光标位置,是通过输出 esc 序列(转义序列)实现终端显示效果。

详细内容参见:C 语言与 VT100 控制码编程

实现非阻塞输入

C 标准输入函数 scanf 和 getchar 属于阻塞式函数,即如果用户没有输入,程序就会一直等待用户输入,而不是运行之后的语句,并且当用户输入内容后,需键入回车才能把内容传递给程序。如果对阻塞与非阻塞概念有些模糊,可以点击此处了解关于阻塞与非阻塞的入门知识。

在上篇博文中,我们的贪吃蛇游戏还做不到在不输入时使蛇自动向当前方向前进一步,还需要键入回车使输入命令回显,游戏体验很糟。

为了提高贪吃蛇的游戏体验,我们期待在游戏中能使用非阻塞式的输入,并且无需键入回车使内容回显,我们希望只要当键位被按下,程序能够立刻响应。

查阅相关资料后,我们在 Linux 环境下可以使用 kbhit 函数实现非阻塞式输入。

相关博客链接:linux 非阻塞键盘输入

编写贪吃蛇 AI

智能算法中最关键的函数是决定智能蛇接下来往哪个方向走的函数——即返回一个决定方向的字符的函数——其余则与正常贪吃蛇游戏(用户控制)没有太大区别。

基础算法

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Hx, Hy: 头的位置
// Fx, Fy: 食物的位置
function whereGoNext(Hx, Hy, Fx, Fy) {
move[4] = {'a', 'd', 'w', 's'}
distance[4] = {0, 0, 0, 0}

FOR i in range(4)
IF 蛇按照move[i]的方向走一步没有走到' '
IF 走到的是食物
return move[i]
ELSE
distance[i] = 9999
ELSE
// Hx_, Hy_: 头按照move[i]的方向运动的位置
distance[i] = |Fx - Hx_| + |Fy - Hy_|
ENDFOR

选出distance中最小的值对应下标 index

IF distance[index] = 9999
game over
ELSE
return move[index]
}

具体代码

由于篇幅的原因,具体代码可以点击此处跳转查看。

一些思考

目前的智能算法还有很大的改进空间,比如遇到下图所示的情况时,智能蛇就会“义无反顾”地向前运动,随后即被这个长度为 5 的障碍物困死。

网络不给力

面对这种情况,我们需要高级的智能贪吃蛇 AI。

高级算法的简单介绍

在本小节开始之前,笔者强烈向大家推荐阅读 Hawstein 大神的这篇文章: 如何用 Python 写一个贪吃蛇 AI

网络不给力

  • BFS 广度优先搜索算法

BFS 算法的思路可以大致概括为:探索蛇头周围的位置,然后迭代探索这些位置周围可能的位置……直到第一次找到食物,即找到了从当前位置到食物的最短路径。

算法能够保证蛇绝不死亡的前提是最短路径存在。我们可以参照下图了解这种算法的弊端:

网络不给力

BFS 算法弊端的本质是:没有考虑到场景是变化的,只要蛇运动了,场景也就发生变化了。

  • 哈密尔顿回路

在查阅相关资料后,笔者了解到,只要蛇头和蛇尾保持联通,那蛇就一定不会进入死胡同。

通过这种思考方式,我们可以这样设计贪吃蛇 AI:定义一条虚拟蛇,在每一次真实蛇去吃食物之前,先让虚拟蛇去吃,如果吃完之后的虚拟蛇蛇头与蛇尾是联通的,则说明这是一条安全路径,可以放心去吃;如果不能联通,则向远离蛇尾的方向“徘徊”。

这里,我给大家提供了一篇使用哈密尔顿回路思想解决贪吃蛇 AI 问题的博文:设计简单的贪吃蛇 AI

CATALOG
  1. 1. VT100 控制码编程
  2. 2. 实现非阻塞输入
  3. 3. 编写贪吃蛇 AI
    1. 3.1. 基础算法
      1. 3.1.1. 伪代码
      2. 3.1.2. 具体代码
      3. 3.1.3. 一些思考
    2. 3.2. 高级算法的简单介绍