「Snake」--H5 ミニゲーム開発

今日は、みんなで議論したり勉強したりできるように、H5 で作られた小さなゲームを紹介します。それは非常に古典的なゲーム、スネークです。スネークをプレイする古典的な方法は 2 つあります。1 つはポイントを獲得してレベルをクリアする方法、もう 1 つは最後まで食べる方法です。

最初の方法の具体的なゲームプレイは、ヘビが一定量の餌を食べるとレベルをクリアし、レベルを通過すると速度が上がります。2 番目の方法は、餌がなくなるまで食べるというものです。今日実装するのは 2 番目の遊び方です。

MVCデザイン パターン

古典的な Snake に基づいて、実装する際には古典的なデザイン モデルである MVC (つまり、モデル – ビュー – コントロール) も使用します。ゲームのさまざまな状態とデータ構造はモデルによって管理され、ビューはモデルの変更を表示するために使用されます。ユーザーとゲームの間の対話はコントロールによって実行されます (コントロールはさまざまなゲーム API インターフェイスを提供します)。

モデルはゲームの中核であり、この記事の主な内容にはパフォーマンスの問題が含まれます。コントロールはビジネス ロジックを担当します。 この設計の利点は、モデルが完全に独立しており、ビューがモデルのステート マシンであり、モデルとビューの両方がコントロールによって駆動されることです。

モデル

貪欲なヘビの古典的な写真を見てください。

スネークには 4 つの主要な参加者がいます:

スネーク

食べ物

壁

ゾーン

ステージは 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],
]

2次元配列の操作は1次元配列ほど便利ではないため、次のように 1 次元配列を使用します。

[
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,
]

ステージ マトリックス上のスネークと食べ物は、ステージを 2 つにマッピングしたものにすぎません。これらは独立したデータ構造を持っています。

スネークは座標インデックスのリンクされたリストです。 food はステージ座標を指すインデックス値です。

ヘビの活動

ヘビの活動には以下の3つがあります:

動く

食べる

衝突する

動く

動くとヘビの中で何が起こる？

スネーク リンク リストは、1 回の移動中に 2 つのことを実行します。テーブルの先頭に新しいノードを挿入し、テーブルの末尾にある古いノードを削除します。配列を使用してスネーク リンク リストを表現すると、スネークの動きは次の疑似コードになります:

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

その配列はスネーク リンク リストとして適切ですか?

これは私が最初に考えた質問です。結局のところ、配列のシフト解除とポップはヘビの動きをシームレスに表現できます。ただし、利便性が優れたパフォーマンスを意味するわけではありません。配列に要素を挿入する unshift の時間計算量は O(n)、配列の末尾の要素を削除する Pop の時間計算量は O(1) です。

ヘビの動きは高頻度のアクションであり、1 つのアクションのアルゴリズムの複雑さが O(n) で、ヘビの長さが比較的長い場合、ゲームのパフォーマンスに問題が発生します。私が実現したい貪欲なスネークは理論的には長いスネークであるため、この記事での私の答えは、配列はスネークのリンクされたリストとしては適切ではない、というものです。

スネークリンクリストは実際のリンクリスト構造でなければなりません。

リンク リスト内のノードの削除または挿入の時間計算量は O(1) です。スネーク リンク リストのデータ構造としてリンク リストを使用すると、ゲームのパフォーマンスを向上させることができます。

javascript

既製のリンク リスト構造はありません。Chain は unshfit と Pop を提供するリンク リスト クラスを作成しました。次の疑似コードは、スネークリンクリストを作成します:

let snake = new Chain();

スペースの問題のため、ここではチェーンの実装方法は紹介しません。興味のある方は https://github.com/leeenx/es6-utils#chain

を参照してください。

食べることと衝突すること

「食べること」と「衝突すること」の違いは、食べることは「食べ物」に当たり、衝突することは「壁」に当たることです。 「食べる」と「ぶつかる」は、ヘビの「動き」で考えられる3つの結果のうちの2つの分岐であると私は考えています。ヘビの動きで考えられる結果は、「前進」、「食べる」、「衝突」の 3 つです。

ヘビの動きの疑似コードを見てください:

function move(next) {
    snake.pop() & snake.unshift(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 で動的な効果を作成するいくつかの方法

以上が「Snake」--H5 ミニゲーム開発の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。