'Snake' - Développement d'un mini-jeu H5-Tutoriel H5-php.cn

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' - Développement d'un mini-jeu H5

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

Copier après la connexion

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

Copier après la connexion

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

Copier après la connexion

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 ?

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

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

Copier après la connexion

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

Copier après la connexion

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

Copier après la connexion

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

Copier après la connexion

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;

Copier après la connexion

如果考虑到投食的前提 —— 不与蛇身重叠，你会发现上面的随机代码并不能保证投食位置不与蛇身重叠。由于这个算法的安全性带有赌博性质，且把它称作「赌博算法」。为了保证投食的安全性，我把算法扩展了一下：

// 伪代码
function feed() {
    let index = Math.random(zone.length) >> 0;
    // 当前位置是否被占用
    return zone[index] === S ? feed() : index;
}
food = feed();

Copier après la connexion

上面的代码虽然在理论上可以保证投食的绝对安全，不过我把这个算法称作「不要命的赌徒算法」，因为上面的算法有致命的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();

Copier après la connexion

这个算法的平均复杂度为 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 是使用渲染引擎还原设计稿的过程。本文的目的是介绍「贪吃蛇」的实现思路，如何使用一个渲染引擎不是本文讨论的范畴，我想介绍的是：「如何提高渲染的效率」。