貪吃蛇的經典玩法有兩種： 第一種是筆者小時候在掌上游戲機最先體驗到的（不小心暴露了年齡），具體玩法是蛇吃完一定數量的食物後就通關，通關後速度會加快；第二種是諾基亞在1997年在其自家手機上安裝的游戲，它的玩法是吃到沒食物為止。筆者要實現的就是第二種玩法。 MVC設計模式 基於貪吃蛇的經典，筆者在實現 ...
貪吃蛇的經典玩法有兩種：
- 積分闖關
- 一吃到底
第一種是筆者小時候在掌上游戲機最先體驗到的（不小心暴露了年齡），具體玩法是蛇吃完一定數量的食物後就通關，通關後速度會加快；第二種是諾基亞在1997年在其自家手機上安裝的游戲，它的玩法是吃到沒食物為止。筆者要實現的就是第二種玩法。
MVC設計模式
基於貪吃蛇的經典，筆者在實現它時也使用一種經典的設計模型：MVC（即：Model - View - Control）。游戲的各種狀態與數據結構由 Model 來管理；View 用於顯示 Model 的變化；用戶與游戲的交互由 Control 完成（Control 提供各種游戲API介面）。
Model 是游戲的核心也是本文的主要內容；View 會涉及到部分性能問題；Control 負責業務邏輯。 這樣設計的好處是： Model完全獨立，View 是 Model 的狀態機，Model 與 View 都由 Control 來驅動。
Model
看一張貪吃蛇的經典圖片。
web前端/H5/javascript學習群：250777811
歡迎關註此公眾號→【web前端EDU】跟大佬一起學前端！歡迎大家留言討論一起轉發
貪吃蛇有四個關鍵的參與對象：
- 蛇（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();
吃食 & 碰撞
「吃食」與「碰撞」區別在於吃食撞上了「食物」，碰撞撞上了「牆」。筆者認為「吃食」與「碰撞」屬於蛇一次「移動」的三個可能結果的兩個分支。蛇移動的三個可能結果是：「前進」、「吃食」和「碰撞」。
回頭看一下蛇移動的偽代碼：
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%
看來「賭博演算法」還是可以利用一下的。於是筆者重新設計了一個演算法：
// 偽代碼 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 的任務主要有兩個：
- 繪製游戲的界面；
- 渲染 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 件事：
- 游戲與用戶的互動
- 驅動 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 對象下。
snake.event.on("countdown", (time) => console.log("剩餘時間：", time));
「驅動 Model 」只做一件事 ------ 將 Model 的蛇的方向更新為用戶指定的方向。 「同步 View 與 Model 」也比較簡單，檢查 Model 是否有更新，如果有更新通知 View 更新游戲界面。
結語
想要貪吃蛇項目源碼的加→
web前端/H5/javascript學習群：250777811
歡迎關註此公眾號→【web前端EDU】跟大佬一起學前端！歡迎大家留言討論一起轉發
