《貪吃蛇》--H5小遊戲開發

今天跟大家分享一份用H5做出來的小遊戲讓大家討論研究，很經典的小遊戲，貪吃蛇。貪吃蛇的經典玩法有兩種：一種是積分闖關，另一種是一吃到底。

第一種的具體玩法是蛇吃完一定數量的食物後就通關，通關後速度會加快；第二種是它的玩法是吃到沒食物為止。我們今天要實現的就是第二種玩法。

MVC設計模式

基於貪吃蛇的經典，我實現它時也使用經典的設計模型：MVC（即：Model – View – Control）。遊戲的各種狀態與資料結構由 Model 來管理；View 用於顯示 Model 的變更；使用者與遊戲的互動由 Control 完成（Control 提供各種遊戲API介面）。

Model 是遊戲的核心也是本文的主要內容；View 會牽涉到部分效能問題；Control 負責業務邏輯。 這樣設計的好處是： Model完全獨立，View 是 Model 的狀態機，Model 與 View 都由 Control 驅動。

Model

看一張貪吃蛇的經典圖片。

貪吃蛇有四個關鍵的參與對象：

蛇（snake）

食物（food）

牆（bounds）

階段（zone）

舞台是一個m * n 的矩陣（二維陣列），矩陣的索引邊界是舞台的牆，矩陣上的成員用來標記食物和蛇的位置。

空舞台如下：

[
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
]

食物（F）和蛇（S）出現在舞台上：

[
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,F,0,0,0,0,0,0,0],
[0,0,0,S,S,S,S,0,0,0],
[0,0,0,0,0,0,S,0,0,0],
[0,0,0,0,S,S,S,0,0,0],
[0,0,0,0,S,0,0,0,0,0],
[0,0,0,0,S,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
]

由於操作二維數組不如一維數組方便，所以我使用的是一維數組， 如下：

[
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,F,0,0,0,0,0,0,0,
0,0,0,S,S,S,S,0,0,0,
0,0,0,0,0,0,S,0,0,0,
0,0,0,0,S,S,S,0,0,0,
0,0,0,0,S,0,0,0,0,0,
0,0,0,0,S,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
]

舞台矩陣上蛇與食物只是舞台對二者的映射，它們彼此都有獨立的數據結構：

蛇是一串座標索引鍊錶；

食物是一個指向舞台座標的索引值。

蛇的活動

蛇的活動有三種，如下：

移動（move）

#吃食（ eat）

碰撞（collision）

移動

當蛇在移動時，內部發生了什麼變化？

蛇鍊錶在一次移動過程中做了兩件事：向表頭插入一個新節點，同時剔除表尾一個舊節點。用一個陣列來代表蛇鍊錶，那麼蛇的移動就是以下的偽代碼：

function move(next) {
   snake.pop() & snake.unshift(next);
}

陣列作為蛇鍊錶合適嗎？

這是我最開始思考的問題，畢竟陣列的 unshift & pop 可以無縫表示蛇的移動。不過，方便不代表效能好，unshift 向陣列插入元素的時間複雜度是 O(n)， pop 剔除陣列尾元素的時間複雜度是 O(1)。

蛇的移動是一個高頻率的動作，如果一次動作的演算法複雜度為 O(n) 且蛇的長度比較大，那麼遊戲的效能就會有問題。我者想實現的貪吃蛇理論上講是一條長蛇，所以我在本文章的回復是 —— 數組不適合作為蛇鍊錶。

蛇鍊錶必須是真正的鍊錶結構。

鍊錶刪除或插入一個節點的時間複雜度為O(1)，用鍊錶作為蛇鍊錶的資料結構能提升遊戲的效能。 javascript 沒有現成的鍊錶結構，我寫了一個叫 Chain 的鍊錶類，Chain 提供了 unshfit & pop。以下偽代碼是創建一條蛇鍊錶：

let snake = new Chain();

由於篇幅問題這裡就不介紹Chain 是如何實現的，有興趣的同學可以移步到: https://github.com/leeenx/es6- utils#chain

吃食& 碰撞

“吃食”與“碰撞”區別在於吃食撞上了“食物”，碰撞撞上了“牆”。我認為「吃食」與「碰撞」屬於蛇一次「移動」的三個可能結果的兩個分支。蛇移動的三個可能結果是：「前進」、「吃食」和「碰撞」。

回頭看一下蛇移動的偽代碼：

function move(next) {
    snake.pop() & snake.unshift(next);
}

代碼中的next 表示蛇頭即將進入的格子的索引值，只有當這個格子是0時蛇才能“前進”，當這個格子是S 表示「碰撞」自己，當這個格子是F表示吃食。

好像少了撞牆？

我在設計過程中，並沒有把牆設計在舞台的矩陣中，而是用索引出界的方式來表示撞牆。簡單來說就是 next === -1 時表示出界撞牆。

以下偽代碼表示蛇的整上活動過程：

// B 表示撞墙
let cell = -1 === next ? B : zone[next];
switch(cell) {
    // 吃食
    case F: eat(); break;
    // 撞到自己
    case S: collision(S); break;
    // 撞墙
    case B: collision(B): break;
    // 前进
    default: move;
}

隨機投食

#隨機投食是指隨機挑選舞台的一個索引值用於映射食物的位置。這似乎很簡單，可以直接這樣寫：

// 伪代码
food = Math.random(zone.length) >> 0;

如果考虑到投食的前提 —— 不与蛇身重叠，你会发现上面的随机代码并不能保证投食位置不与蛇身重叠。由于这个算法的安全性带有赌博性质，且把它称作「赌博算法」。为了保证投食的安全性，我把算法扩展了一下：

// 伪代码
function feed() {
    let index = Math.random(zone.length) >> 0;
    // 当前位置是否被占用
    return zone[index] === S ? feed() : index;
}
food = feed();

上面的代码虽然在理论上可以保证投食的绝对安全，不过我把这个算法称作「不要命的赌徒算法」，因为上面的算法有致命的BUG —— 超长递归 or 死循环。

为了解决上面的致命问题，我设计了下面的算法来做随机投食：

// 伪代码
function feed() {
    // 未被占用的空格数
    let len = zone.length - snake.length;
    // 无法投食
    if(len === 0) return ;
    // zone的索引
    let index = 0,
    // 空格计数器
    count = 0,
    // 第 rnd 个空格子是最终要投食的位置
    rnd = Math.random() * count >> 0 + 1;
    // 累计空格数
    while(count !== rnd) {
        // 当前格子为空，count总数增一
        zone[index++] === 0 && ++count;
    }
    return index - 1;
}
food = feed();

这个算法的平均复杂度为 O(n/2)。由于投食是一个低频操作，所以 O(n/2)的复杂度并不会带来任何性能问题。不过，我觉得这个算法的复杂度还是有点高了。回头看一下最开始的「赌博算法」，虽然「赌博算法」很不靠谱，但是它有一个优势 —— 时间复杂度为 O(1)。

「赌博算法」的靠谱概率 = (zone.length – snake.length) / zone.length。snake.length 是一个动态值，它的变化范围是：0 ~ zone.length。推导出「赌博算法」的平均靠谱概率是：

「赌博算法」平均靠谱概率 = 50%

看来「赌博算法」还是可以利用一下的。于是我重新设计了一个算法：

新算法的平均复杂度可以有效地降低到 O(n/4)，人生有时候需要点运气 : )。

View

在 View 可以根据喜好选择一款游戏渲染引擎，我在 View 层选择了 PIXI 作为游戏游戏渲染引擎。

View 的任务主要有两个：

绘制游戏的界面；

渲染 Model 里的各种数据结构

也就是说 View 是使用渲染引擎还原设计稿的过程。本文的目的是介绍「贪吃蛇」的实现思路，如何使用一个渲染引擎不是本文讨论的范畴，我想介绍的是：「如何提高渲染的效率」。

在 View 中显示 Model 的蛇可以简单地如以下伪代码：

上面代码的时间复杂度是 O(n)。上面介绍过蛇的移动是一个高频的活动，我们要尽量避免高频率地运行 O(n) 的代码。来分析蛇的三种活动：「移动」，「吃食」，「碰撞」。

首先，Model 发生了「碰撞」，View 应该是直接暂停渲染 Model 里的状态，游戏处在死亡状态，接下来的事由 Control 处理。

Model 中的蛇（链表）在一次「移动」过程中做了两件事：向表头插入一个新节点，同时剔除表尾一个旧节点；蛇（链表）在一次「吃食」过程中只做一件事：向表头插入一个新节点。

如果在 View 中对 Model 的蛇链表做差异化检查，View 只增量更新差异部分的话，算法的时间复杂度即可降低至 O(1) ~ O(2) 。以下是优化后的伪代码：

Control

Control 主要做 3 件事：

游戏与用户的互动

驱动 Model

同步 View 与 Model

「游戏与用户的互动」是指向外提供游戏过程需要使用到的 APIs 与 各类事件。我规划的 APIs 如下：

name

type

deltail

init    method    初始化游戏    

start    method    开始游戏    

restart    method    重新开始游戏    

pause    method    暂停    

resume    method    恢复    

turn    method    控制蛇的转向。如：turn(“left”)    

destroy    method    销毁游戏    

speed    property    蛇的移动速度    

事件如下：

name

detail

countdown    倒时计    

eat    吃到食物    

before-eat    吃到食物前触发    

gameover    游戏结束    

事件统一挂载在游戏实例下的 event 对象下。

「驱动 Model 」只做一件事 —— 将 Model 的蛇的方向更新为用户指定的方向。

「同步 View 与 Model 」也比较简单，检查 Model 是否有更新，如果有更新通知 View 更新游戏界面。

以上就是用H5做贪吃蛇小游戏的全部步奏，有兴趣的朋友可以深度研究一下。

推荐阅读：

最完整的HTML5標籤

#html5離線儲存與cookie儲存分析

################################# ##########幾種關於HTML 5 的動態效果製作方法######

以上是《貪吃蛇》--H5小遊戲開發的詳細內容。更多資訊請關注PHP中文網其他相關文章！