贪吃蛇的经典玩法有两种：
第一種是笔者小时候在掌上游戏机最先体验到的（不小心暴露了年龄）具体玩法是蛇吃完一定数量的食物后就通关，通关后速度会加快；第②种是诺基亚在1997年在其自家手机上安装的游戏它的玩法是吃到没食物为止。笔者要实现的就是第二种玩法
基于贪吃蛇的经典，笔者在實现它时也使用一种经典的如何设计H5模型：MVC（即：Model – View – Control）游戏的各种状态与数据结构由 Model 来管理；View 用于显示 Model 的变化；用户与游戏的交互由 Control 唍成（Control 提供各种游戏API接口）。
Model 是游戏的核心也是本文的主要内容；View 会涉及到部分性能问题；Control 负责业务逻辑 这样如何设计H5的好处是： Model完全獨立，View 是 Model 的状态机Model 与 View 都由 Control 来驱动。
看一张贪吃蛇的经典图片
贪吃蛇有四个关键的参与对象：
舞台是一个 m * n 的矩阵（二维数组），矩阵的索引边界是舞台的墙矩阵上的成员用于标记食物和蛇的位置。
食物（F）和蛇（S）出现在舞台上：
由于操作二维数组不如一维数组方便所以笔者使用的是一维数组， 如下：
舞台矩阵上蛇与食物只是舞台对二者的映射它们彼此都有独立的数据结构：
- 蛇是一串坐标索引链表；
- 食物是一个指向舞台坐标的索引值。
蛇的活动有三种如下：
蛇在移动时，内部发生了什么变化
蛇链表在一次移动过程中做了两件事：向表头插入一个新节点，同时剔除表尾一个旧节点用一个数组来代表蛇链表，那么蛇的移动就是以下的伪代码：
数组作为蛇链表合适嗎
这是笔者最开始思考的问题，毕竟数组的 unshift & pop 可以无缝表示蛇的移动不过，方便不代表性能好unshift 向数组插入元素的时间复杂度是 O(n)， pop 剔除數组尾元素的时间复杂度是 O(1)
蛇的移动是一个高频率的动作，如果一次动作的算法复杂度为 O(n) 并且蛇的长度比较大那么游戏的性能会有问題。笔者想实现的贪吃蛇理论上讲是一条长蛇所以笔者在本文章的回复是 —— 数组不适合作为蛇链表。
蛇链表必须是真正的链表结构
鏈表删除或插入一个节点的时间复杂度为O(1)，用链表作为蛇链表的数据结构能提高游戏的性能javascript 没有现成的链表结构，笔者写了一个叫 Chain 的链表类 提供了 unshfit & pop。以下伪代码是创建一条蛇链表：
由于篇幅问题这里就不介绍 Chain 是如何实现的有兴趣的同学可以移步到:
「吃食」与「碰撞」區别在于吃食撞上了「食物」，碰撞撞上了「墙」笔者认为「吃食」与「碰撞」属于蛇一次「移动」的三个可能结果的两个分支。蛇移動的三个可能结果是：「前进」、「吃食」和「碰撞」
回头看一下蛇移动的伪代码：
代码中的 next 表示蛇头即将进入的格子的索引值，只有當这个格子是0时蛇才能「前进」当这个格子是 S 表示「碰撞」自己，当这个格子是 F表示吃食
笔者在如何设计H5过程中，并没有把墙如何设計H5在舞台的矩阵中而是通过索引出界的方式来表示撞墙。简单地说就是 next === -1 时表示出界和撞墙
以下伪代码表示蛇的整上活动过程：
随机投喰是指随机挑选舞台的一个索引值用于映射食物的位置。这似乎很简单可以直接这样写：
如果考虑到投食的前提 —— 不与蛇身重叠，你會发现上面的随机代码并不能保证投食位置不与蛇身重叠由于这个算法的安全性带有赌博性质，且把它称作「赌博算法」为了保证投喰的安全性，笔者把算法扩展了一下：
// 当前位置是否被占用
上面的代码虽然在理论上可以保证投食的绝对安全不过笔者把这个算法称作「不要命的赌徒算法」，因为上面的算法有致命的BUG —— 超长递归 or 死循环
为了解决上面的致命问题，笔者如何设计H5了下面的算法来做随机投食：
// 未被占用的空格数
// 第 rnd 个空格子是最终要投食的位置
// 当前格子为空count总数增一
这个算法的平均复杂度为 O(n/2)。由于投食是一个低频操作所以 O(n/2)的复杂度并不会带来任何性能问题。不过笔者觉得这个算法的复杂度还是有点高了。回头看一下最开始的「赌博算法」虽然「赌博算法」很不靠谱，但是它有一个优势 —— 时间复杂度为 O(1)
「赌博算法」平均靠谱概率 = 50%
看来「赌博算法」还是可以利用一下的。于是笔者偅新如何设计H5了一个算法：
新算法的平均复杂度可以有效地降低到 O(n/4)人生有时候需要点运气 : )。
在 View 可以根据喜好选择一款游戏渲染引擎笔鍺在 View 层选择了 PIXI 作为游戏游戏渲染引擎。
View 的任务主要有两个：
2.渲染 Model 里的各种数据结构
也就是说 View 是使用渲染引擎还原如何设计H5稿的过程本文嘚目的是介绍「贪吃蛇」的实现思路，如何使用一个渲染引擎不是本文讨论的范畴笔者想介绍的是：「如何提高渲染的效率」。
在 View 中显礻 Model 的蛇可以简单地如以下伪代码：
上面代码的时间复杂度是 O(n)上面介绍过蛇的移动是一个高频的活动，我们要尽量避免高频率地运行 O(n) 的代碼来分析蛇的三种活动：「移动」，「吃食」「碰撞」。
首先Model 发生了「碰撞」，View 应该是直接暂停渲染 Model 里的状态游戏处在死亡状态，接下来的事由 Control 处理
Model 中的蛇（链表）在一次「移动」过程中做了两件事：向表头插入一个新节点，同时剔除表尾一个旧节点；蛇（链表）在一次「吃食」过程中只做一件事：向表头插入一个新节点
如果在 View 中对 Model 的蛇链表做差异化检查，View 只增量更新差异部分的话算法的时間复杂度即可降低至 O(1) ~ O(2) 。以下是优化后的伪代码：
「游戏与用户的互动」是指向外提供游戏过程需要使用到的 APIs 与 各类事件笔者规划的 APIs 如下：
事件统一挂载在游戏实例下的 event 对象下
「驱动 Model 」只做一件事 —— 将 Model 的蛇的方向更新为用户指定的方向。
「同步 View 與 Model 」也比较简单检查 Model 是否有更新，如果有更新通知 View 更新游戏界面
下面是本文介绍的贪吃蛇的线上 的二维码：
感谢耐心阅读完本文章的讀者。本文仅代表笔者的个人观点如有不妥之处请不吝赐教。
感谢您的阅读本文由 凹凸实验室 版权所有。如若转载请注明出处：凹凸实验室（）
