H5遊戲開發：貪吃蛇

廣東IT優就業

貪吃蛇的經典玩法有兩種：

1. 積分闖關

2. 一吃到底

第一種是小編小時候在掌上遊戲機最先體驗到的（不小心暴露了年齡），具體玩法是蛇吃完一定數量的食物后就通關，通關后速度會加快；第二種是諾基亞在1997年在其自家手機上安裝的遊戲，它的玩法是吃到沒食物為止。筆者要實現的就是第二種玩法。

MVC設計模式

基於貪吃蛇的經典，筆者在實現它時也使用一種經典的設計模型：MVC（即：Model - View - Control）。遊戲的各種狀態與數據結構由 Model 來管理；View 用於顯示 Model 的變化；用戶與遊戲的交互由 Control 完成（Control 提供各種遊戲API介面）。

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

Model

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

廣東IT優就業

web前端/H5/javascript學習群：250777811

歡迎關注此公眾號→【web前端EDU】跟大佬一起學前端！歡迎大家留言討論一起轉發

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

1. 蛇（snake）

2. 食物（food）

3. 牆（bounds）

4. 舞台（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）

移動

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

廣東IT優就業

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

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();

吃食 & 碰撞

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

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

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

代碼中的

next

表示蛇頭即將進入的格子的索引值，只有當這個格子是

0

時蛇才能「前進」，當這個格子是

S

表示「碰撞」自己，當這個格子是

F

表示吃食。

好像少了撞牆？ 筆者在設計過程中，並沒有把牆設計在舞台的矩陣中，而是通過索引出界的方式來表示撞牆。簡單地說就是

next === -1

時表示出界和撞牆。

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

廣東IT優就業

// 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%

看來「賭博演算法」還是可以利用一下的。於是筆者重新設計了一個演算法：

// 偽代碼function bet() { let rnd = Math.random() * zone.length >> 0; return zone[rnd] === 0 ? rnd : -1;}function feed() { ...}food = bet();if(food === -1) food = feed();

新演算法的平均複雜度可以有效地降低到 O(n/4)，人生有時候需要點運氣 : )。

View

在 View 可以根據喜好選擇一款遊戲渲染引擎，筆者在 View 層選擇了

PIXI

作為遊戲遊戲渲染引擎。

View 的任務主要有兩個：

1. 繪製遊戲的界面；

2. 渲染 Model 里的各種數據結構

也就是說 View 是使用渲染引擎還原設計稿的過程。本文的目的是介紹「貪吃蛇」的實現思路，如何使用一個渲染引擎不是本文討論的範疇，筆者想介紹的是：「如何提高渲染的效率」。

在 View 中顯示 Model 的蛇可以簡單地如以下偽代碼：

// 清空 View 上的蛇view.snake.clean();model.snake.forEach( (node) => { // 創建 View 上的蛇節點let viewNode = createViewNode(node); // 併合一條新蛇 view.snake.push(viewNode); });

上面代碼的時間複雜度是 O(n)。上面介紹過蛇的移動是一個高頻的活動，我們要盡量避免高頻率地運行 O(n) 的代碼。來分析蛇的三種活動：「移動」，「吃食」，「碰撞」。

首先，Model 發生了「碰撞」，View 應該是直接暫停渲染 Model 里的狀態，遊戲處在死亡狀態，接下來的事由 Control 處理。

Model 中的蛇（鏈表）在一次「移動」過程中做了兩件事：向表頭插入一個新節點，同時剔除表尾一個舊節點；蛇（鏈表）在一次「吃食」過程中只做一件事：向表頭插入一個新節點。

如果在 View 中對 Model 的蛇鏈表做差異化檢查，View 只增量更新差異部分的話，演算法的時間複雜度即可降低至 O(1) ~ O(2) 。以下是優化后的偽代碼：

let snakeA = model.snake, snakeB = view.snake;// 增量更新尾部while(snakeB.length <= snakeA.length) { headA = snakeA.next(); // 頭節點匹配if(headA.data === headB.data) break; // 不匹配else { // 向snakeB插入頭節點if(snakeA.HEAD === headA.index) { snakeB.unshift(headA.data); } // 向snakeB插入第二個節點else snakeB.insertAfter(0, headA.data); }}// 增量更新頭部 let tailA = snakeA.last(), tailB;while(snakeB.length !== 0) { tailB = snakeB.last(); // 尾節點匹配if(tailA.data === tailB.data) break; // 不匹配else snakeB.pop();}

Control

Control 主要做 3 件事：

1. 遊戲與用戶的互動

2. 驅動 Model

3. 同步 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

對象下。

snake.event.on("countdown", (time) => console.log("剩餘時間：", time));

「驅動 Model 」只做一件事 ------ 將 Model 的蛇的方向更新為用戶指定的方向。 「同步 View 與 Model 」也比較簡單，檢查 Model 是否有更新，如果有更新通知 View 更新遊戲界面。

廣東IT優就業

更多IT精彩推薦：

人人都要學的IT小技巧：http://xue.ujiuye.com/zt/renrenxue/