"Snake"--H5 mini game development

Today I will share with you a small game made with H5 for everyone to discuss and study. It is a very classic game, Snake. There are two classic ways to play Snake: one is to score points to clear levels, and the other is to eat to the end.

The specific gameplay of the first method is that the snake will clear the level after eating a certain amount of food, and the speed will speed up after passing the level; the second method of gameplay is that it eats until it runs out of food. What we are going to implement today is the second way of playing.

MVCDesign Pattern

Based on the classic Snake, I also use a classic design model when implementing it: MVC (ie: Model – View – Control). The various states and data structures of the game are managed by Model; View is used to display changes in Model; the interaction between the user and the game is completed by Control (Control provides various game API interfaces).

Model is the core of the game and the main content of this article; View will involve some performance issues; Control is responsible for business logic. The advantage of this design is that the Model is completely independent, the View is the state machine of the Model, and both the Model and View are driven by Control.

Model

Look at a classic picture of a greedy snake.

Snake has four key participants:

SNAKE

Food

Walls (bounds)

Stage (zone)

The stage is a m * n matrix (two-dimensional array), and the index boundary of the matrix is On the walls of the stage, members on the matrix are used to mark the locations of food and snakes.

The empty stage is as follows:

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

Food (F) and snake (S) appear on the stage:

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

Because the operation of two-dimensional arrays is not as good as one-dimensional arrays Convenience, so I use a one-dimensional array, as follows:

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

The snake and food on the stage matrix are just the mapping of the stage to the two, and they have independent data structures:

Snake is a list of coordinate indexes;

Food is an index value pointing to the stage coordinates.

Activities of snakes

There are three activities of snakes, as follows:

Move(move)

Eat ( eat)

Collision

Movement

What happens inside the snake when it moves?

The snake linked list does two things during one move: inserting a new node into the head of the table and deleting an old node at the end of the table. Use an array to represent the snake linked list, then the movement of the snake is the following pseudo code:

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

Is the array suitable as a snake linked list?

This is the first question I thought about. After all, the unshift & pop of the array can seamlessly represent the movement of the snake. However, convenience does not mean good performance. The time complexity of unshift to insert elements into the array is O(n), and the time complexity of pop to remove the tail element of the array is O(1).

The movement of a snake is a high-frequency action. If the algorithm complexity of an action is O(n) and the length of the snake is relatively large, then there will be problems with the game's performance. The greedy snake I want to realize is theoretically a long snake, so my reply in this article is - arrays are not suitable as snake linked lists.

The snake linked list must be a real linked list structure.

The time complexity of deleting or inserting a node in a linked list is O(1). Using a linked list as the data structure of a snake linked list can improve the performance of the game. javascript There is no ready-made linked list structure. I wrote a linked list class called Chain. Chain provides unshfit & pop. The following pseudo code is to create a snake linked list:

let snake = new Chain();

Due to space issues, we will not introduce how Chain is implemented here. Interested students can go to: https://github.com/leeenx/es6- utils#chain

Eating & Collision

The difference between "eating" and "collision" is that eating hits "food" and collision hits "wall". I think "eating" and "collision" are two branches of the three possible outcomes of a snake's "movement". The three possible outcomes of a snake's movement are: "advance", "eat" and "collision".

Look back at the pseudo code for snake movement:

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

The next in the code represents the index value of the grid the snake head is about to enter. Only when this grid is 0 can the snake "move forward". When this grid is S, it means "collision" with yourself. When this grid is F, it means eating.

It seems like there is less hitting the wall?

During the design process, I did not design the wall in the matrix of the stage. Instead, I represented hitting the wall by indexing out of bounds. Simply put, next === -1 means out of bounds and hitting the wall.

The following pseudocode represents the entire activity process of the snake:

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

Random feeding

Random feeding refers to randomly selecting an index value of the stage for mapping food Location. This seems very simple and can be written directly like this:

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

推荐阅读：

The most complete HTML5 tags

html5 offline storage and cookie storage analysis

Several ways to create dynamic effects in HTML 5

The above is the detailed content of "Snake"--H5 mini game development. For more information, please follow other related articles on the PHP Chinese website!