「Snake」--H5 ミニゲーム開発-H5 チュートリアル-php.cn

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

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

MVCデザインパターン

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

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

モデル

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

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

スネークには 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つがあります:

動く

食べる

衝突する

動く

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

「Snake」--H5 ミニゲーム開発
スネークリンクリストは、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 是使用渲染引擎还原设计稿的过程。本文的目的是介绍「贪吃蛇」的实现思路，如何使用一个渲染引擎不是本文讨论的范畴，我想介绍的是：「如何提高渲染的效率」。