首頁  >  文章  >  web前端  >  《貪吃蛇》--H5小遊戲開發

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

php中世界最好的语言
php中世界最好的语言原創
2017-11-18 17:27:122048瀏覽

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

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

MVC設計模式

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

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

Model

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

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

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

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

移動

當蛇在移動時,內部發生了什麼變化?

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

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

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 中的蛇(链表)在一次「移动」过程中做了两件事:向表头插入一个新节点,同时剔除表尾一个旧节点;蛇(链表)在一次「吃食」过程中只做一件事:向表头插入一个新节点。

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

如果在 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中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn