"Snake" - Développement d'un mini-jeu H5

Aujourd'hui, je vais partager avec vous un petit jeu réalisé avec H5 pour que tout le monde puisse en discuter et étudier. C'est un jeu très classique, Snake. Il existe deux manières classiques de jouer à Snake : l'une consiste à marquer des points pour terminer les niveaux et l'autre consiste à manger jusqu'à la fin.

Le gameplay spécifique de la première méthode est que le serpent terminera le niveau après avoir mangé une certaine quantité de nourriture, et la vitesse s'accélérera après avoir passé le niveau ; la deuxième méthode de jeu est qu'il mange jusqu'à ce que il n'y a plus de nourriture. Ce que nous allons mettre en œuvre aujourd'hui, c'est la deuxième façon de jouer.

MVCDesign Pattern

Basé sur le Snake classique, j'utilise également un modèle de conception classique lors de son implémentation : MVC (c'est-à-dire : Modèle – Vue – Contrôle). Les différents états et structures de données du jeu sont gérés par Model ; View est utilisé pour afficher les modifications dans Model ; l'interaction entre l'utilisateur et le jeu est complétée par Control (Control fournit diverses interfaces API de jeu).

Le modèle est le cœur du jeu et le contenu principal de cet article ; View impliquera certains problèmes de performances ; Le contrôle est responsable de la logique métier. L'avantage de cette conception est que le modèle est complètement indépendant, que la vue est la machine à états du modèle et que le modèle et la vue sont pilotés par le contrôle.

Modèle

Regardez une image classique d'un serpent gourmand.

Snake compte quatre participants clés :

serpent

nourriture

Murs (limites)

Scène (zone)

La scène est une matrice m * n (tableau bidimensionnel), et la limite d'index de la matrice est Sur les murs de la scène, les membres sur la matrice sont utilisés pour marquer les emplacements de la nourriture et des serpents.

La scène vide est la suivante :

[
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0],
]

La nourriture (F) et le serpent (S) apparaissent sur la scène :

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

Depuis le fonctionnement en deux dimensions Les tableaux ne sont pas aussi bons que Tableau unidimensionnel est pratique, j'utilise donc un tableau unidimensionnel, comme suit :

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

Le serpent et la nourriture sur la matrice de scène ne sont que les mappage de la scène aux deux, et ils ont des données indépendantes l'une pour l'autre. Structure :

Snake est une liste d'index de coordonnées

La nourriture est une valeur d'index pointant vers les coordonnées de la scène.

Activités des serpents

Il existe trois activités des serpents, comme suit :

Bouger (bouger)

Manger (manger)

collision

bouger

Que se passe-t-il à l'intérieur du serpent lorsqu'il bouge ?

La liste chaînée du serpent fait deux choses en un seul mouvement : insérer un nouveau nœud en tête de table et supprimer un ancien nœud en fin de table. . Utilisez un tableau pour représenter la liste chaînée de serpents, puis le mouvement du serpent est le pseudo-code suivant :

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

Le tableau est-il adapté comme liste chaînée de serpents ?

C'est la première question à laquelle j'ai pensé. Après tout, le décalage et le pop du tableau peuvent représenter de manière transparente le mouvement du serpent. Cependant, commodité ne signifie pas de bonnes performances. La complexité temporelle du unshift pour insérer des éléments dans le tableau est O(n), et la complexité temporelle du pop pour supprimer l'élément de queue du tableau est O(1).

Le mouvement d'un serpent est une action à haute fréquence. Si la complexité algorithmique d'une action est O(n) et que la longueur du serpent est relativement grande, alors les performances du jeu seront problématiques. Le serpent gourmand que je veux réaliser est théoriquement un long serpent, donc ma réponse dans cet article est la suivante : les tableaux ne conviennent pas comme listes chaînées de serpents.

La liste chaînée des serpents doit être une véritable structure de liste chaînée.

La complexité temporelle de la suppression ou de l'insertion d'un nœud dans une liste chaînée est O(1). L'utilisation d'une liste chaînée comme structure de données d'une liste chaînée de serpent peut améliorer les performances du jeu. javascript Il n'y a pas de structure de liste chaînée prête à l'emploi. J'ai écrit une classe de liste chaînée appelée Chain qui fournit unshfit & pop. Le pseudo-code suivant crée une liste chaînée de serpents :

let snake = new Chain();

En raison de problèmes d'espace, nous ne présenterons pas ici comment Chain est implémenté. Les étudiants intéressés peuvent accéder à : https://github.com/leeenx/. es6-utils#chain

Manger et collision

La différence entre « manger » et « collision » est que manger touche « nourriture » et la collision frappe « mur ». Je pense que « manger » et « entrer en collision » sont deux branches des trois résultats possibles du « mouvement » d'un serpent. Les trois résultats possibles du mouvement d'un serpent sont : "avancer", "manger" et "collision".

Regardez le pseudo-code pour le mouvement du serpent :

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

Le suivant dans le code représente la valeur d'index de la grille dans laquelle la tête du serpent est sur le point d'entrer Seulement lorsque cette grille est sur le point d'entrer. 0 le serpent peut-il "avancer", quand cette grille est S, cela signifie "collision" avec soi-même, et lorsque cette grille est F, cela signifie manger.

On dirait qu'il y a moins de bosses dans le mur ?

Pendant le processus de conception, je n'ai pas conçu le mur dans la matrice de la scène, j'ai plutôt représenté le fait de frapper le mur en indexant hors des limites. En termes simples, lorsque next === -1, cela signifie sortir des limites et heurter le mur.

Le pseudo-code suivant représente l'ensemble du processus d'activité du serpent :

// 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;
}

Alimentation aléatoire

L'alimentation aléatoire signifie la sélection aléatoire d'une valeur d'indice du stade pour cartographier l'emplacement des aliments. Cela semble très simple et peut s'écrire directement comme ceci :

// 伪代码
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做贪吃蛇小游戏的全部步奏，有兴趣的朋友可以深度研究一下。

推荐阅读：

Les balises HTML5 les plus complètes

analyse du stockage hors ligne HTML5 et du stockage des cookies

Plusieurs façons de créer des effets dynamiques en HTML 5

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!