H5 development: details of realizing the game of destroying stars

This article introduces to you the details of the H5 implementation of the star elimination game. It has a good reference value. I hope it can help friends in need.

"Destroy the Stars" is a very classic "elimination game". Its gameplay is very simple: eliminate connected bricks of the same color.

1. Game rules

There are multiple versions of "Destroy the Stars", but except for the "level points", their rules are somewhat different. The rules are the same. The game rules of the version introduced by the author are organized as follows:

1. Color brick distribution

10 x 10 table

5 colors - red, green, blue, yellow , purple

The number of each type of color bricks is randomly distributed within the specified interval

5 types of color bricks are randomly distributed in the 10 x 10 table

2. Elimination rules

Two or more bricks of the same color are connected and can be eliminated.

3. Points Rules

Total elimination points = n * n * 5

Total reward points = 2000 – n * n * 20

"n" represents the number of bricks. The above are the rules for the "total" score, as well as the score rules for "single" bricks:

Score for eliminating bricks = 10 * i 5

Deduction for remaining bricks Score = 40 * i 20

"i" represents the index value of the brick (starting from 0). Simply put, the "score value" and "deduction value" of a single brick are an arithmetic sequence.

4. Level score

Level score = 1000 (level – 1) * 2000; “level” is the current level number.

5. Clearance conditions

The color blocks that can be eliminated do not exist

Cumulative score>=Current level score

The above two conditions are true at the same time The game can be cleared.

2. MVC design pattern

The author used the MVC pattern again this time to write "Destroy the Stars". The data structure and various states of the star "bricks" are implemented by the Model, and the core of the game is completed in the Model; the View maps the changes in the Model and performs corresponding behaviors. Its main task is to display animations; the interaction between the user and the game is implemented by the Model. Control is complete.

From a logical planning perspective, Model is very heavy while View and Control are very light. However, from a code perspective, View is very heavy while Model and Control are relatively light.

3. Model

The 10 x 10 table uses an array with a length of 100 to perfectly map the game's star "bricks".

[
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P,
R, R, G, G, B, B, Y, Y, P, P
]

R – red, G – green, B – blue, Y – yellow, P – purple. The core tasks of the Model are the following four:

Generate brick walls

Eliminate bricks (generate brick scores)

Consolidate brick walls

Clear Residual bricks (generation bonus points)

3.1 Generate brick wall

The brick wall is generated in two steps:

Allocation of the number of color bricks

Disperse the color Brick

Theoretically, 100 grids can be equally divided into 5 categories of colors, but the "Destroy the Stars" that the author has played does not use the even distribution strategy. By analyzing several "Destroy Stars" models, we can actually find a rule - "the number difference between colored bricks is within a fixed range."

If equal division in the traditional sense is called "complete equal division", then the distribution of "Eliminate the Stars" is an "incomplete equal division" that fluctuates up and down the average line.

The author calls the above "incomplete equalization" "fluctuation equalization". For the specific implementation of the algorithm, please refer to "fluctuation equalization algorithm".

"Dispersing color bricks" is actually the process of shuffling the array. The author recommends using the "Fisher-Yates shuffling algorithm".

The following is the implementation of pseudo code:

// 波动均分色砖
waveaverage(5, 4, 4).forEach(
// tiles 即色墙数组
(count, clr) => tiles.concat(generateTiles(count, clr));
);
// 打散色砖
shuffle(tiles);

3.2 Eliminating bricks

The rule of "eliminating bricks" is very simple - adjacent ones with the same color can be eliminated .

The first two combinations are in line with "adjacent ones of the same color can be eliminated", so they can be eliminated; although the third combination is "adjacent to the same color" but not "connected" Pass" so it cannot be eliminated.

While "eliminating bricks", there is an important task: generating the scores corresponding to the bricks. In the "Game Rules", the author has provided the corresponding mathematical formula: "Score value for eliminating bricks = 10 * i 5".

The "elimination of bricks" algorithm is implemented as follows:

function clean(tile) {
let count = 1;
let sameTiles = searchSameTiles(tile);
if(sameTiles.length > 0) {
deleteTile(tile);
while(true) {
let nextSameTiles = [];
sameTiles.forEach(tile => {
nextSameTiles.push(...searchSameTiles(tile));
makeScore(++count * 10 + 5); // 标记当前分值
deleteTile(tile); // 删除砖块
});
// 清除完成，跳出循环
if(nextSameTiles.length === 0) break;
else {
sameTiles = nextSameTiles;
}
}
}
}

The logic of the clearing algorithm using "recursion" will be clearer, but "recursion" is prone to "stack overflow" on browsers, so The author did not use "recursive" implementation.

3.3 Consolidating the Brick Wall

After removing some bricks, holes will appear in the brick wall. At this time, the wall needs to be compacted:

向下夯实 向左夯实

向左下夯实（先下后左）

一种快速的实现方案是，每次「消除砖块」后直接遍历砖墙数组（10×10数组）再把空洞夯实，伪代码表示如下：

   
for(let row = 0; row < 10; ++row) {
for(let col = 0; col < 10; ++col) {
if(isEmpty(row, col)) {
// 水平方向（向左）夯实
if(isEmptyCol(col)) {
tampRow(col);
}
// 垂直方向（向下）夯实
else {
tampCol(col);
}
break;
}
}
}

But… 为了夯实一个空洞对一张大数组进行全量遍历并不是一种高效的算法。在笔者看来影响「墙体夯实」效率的因素有：

定位空洞

砖块移动（夯实）

扫描墙体数组的主要目的是「定位空洞」，但能否不扫描墙体数组直接「定位空洞」？

墙体的「空洞」是由于「消除砖块」造成的，换种说法 —— 被消除的砖块留下来的坑位就是墙体的空洞。在「消除砖块」的同时标记空洞的位置，这样就无须全量扫描墙体数组，伪代码如下：

function deleteTile(tile) {
// 标记空洞
markHollow(tile.index);
// 删除砖块逻辑
...
}

在上面的夯实动图，其实可以看到它的夯实过程如下：

空洞上方的砖块向下移动

空列右侧的砖块向左移动

墙体在「夯实」过程中，它的边界是实时在变化，如果「夯实」不按真实边界进行扫描，会产生多余的空白扫

如何记录墙体的边界？
把墙体拆分成一个个单独的列，那么列最顶部的空白格片段就是墙体的「空白」，而其余非顶部的空白格片段即墙体的「空洞」。

笔者使用一组「列集合」来描述墙体的边界并记录墙体的空洞，它的模型如下：

/*
@ count - 列砖块数
@ start - 顶部行索引
@ end - 底部行索引
@ pitCount - 坑数
@ topPit - 最顶部的坑
@ bottomPit - 最底部的坑
*/
let wall = [
{count, start, end, pitCount, topPit, bottomPit},
{count, start, end, pitCount, topPit, bottomPit},
...
];

这个模型可以描述墙体的三个细节：

空列

列的连续空洞

列的非连续空洞

// 空列
if(count === 0) {
...
}
// 连续空洞
else if(bottomPit - topPit + 1 === pitCount) {
...
}
// 非连续空洞
else {
...
}

砖块在消除后，映射到单个列上的空洞会有两种分布形态 —— 连续与非连续。

「连续空洞」与「非连续空洞」的夯实过程如下：

其实「空列」放大于墙体上，也会有「空洞」类似的分布形态 —— 连续与非连续

它的夯实过程与空洞类似，这里就不赘述了。

3.4 消除残砖

上一小节提到了「描述墙体的边界并记录墙体的空洞」的「列集合」，笔者是直接使用这个「列集合」来消除残砖的，伪代码如下：

function clearAll() {
let count = 0;
for(let col = 0, len = this.wall.length;  col < len; ++col) {
let colInfo = this.wall[col];
for(let row = colInfo.start; row <= colInfo.end; ++row) {
let tile = this.grid[row * this.col + col];
tile.score = -20 - 40 * count++; // 标记奖励分数
tile.removed = true;
}
}
}

4. View

View 主要的功能有两个：

UI 管理

映射 Model 的变化（动画）

UI 管理主要是指「界面绘制」与「资源加载管理」，这两项功能比较常见本文就直接略过了。View 的重头戏是「映射 Model 的变化」并完成对应的动画。动画是复杂的，而映射的原理是简单的，如下伪代码：

update({originIndex, index, clr, removed, score}) {
// 还没有 originIndex 或没有色值，直接不处理
if(originIndex === undefined || clr === undefined) return ;
let tile = this.tiles[originIndex];
// tile 存在，判断颜色是否一样
if(tile.clr !== clr) {
this.updateTileClr(tile, clr);
}
// 当前索引变化 ----- 表示位置也有变化
if(tile.index !== index) {
this.updateTileIndex(tile, index);
}
// 设置分数
if(tile.score !== score) {
tile.score = score;
}
if(tile.removed !== removed) {
// 移除或添加当前节点
true === removed ? this.bomb(tile) : this.area.addChild(tile.sprite);
tile.removed = removed;
}
}

Model 的砖块每次数据的更改都会通知到 View 的砖块，View 会根据对应的变化做对应的动作（动画）。

5. Control

Control 要处理的事务比较多，如下：

绑定 Model & View

生成通关分值

判断通关条件

对外事件

用户交互

初始化时，Control 把 Model 的砖块单向绑定到 View 的砖块了。如下：

Object.defineProperties(model.tile, {
    originIndex: {
        get() {...},
        set(){
            ...
            view.update({originIndex})
        }
    },  
    index: {
        get() {...},
        set() {
            ...
            view.update({index})
        }
    },
    clr: {
        get() {...},
        set() {
            ...
            view.update({clr})
        }
    },
    removed: {
        get() {...},
        set() {
            ...
            view.update({removed})
        }
    },  
    score: {
        get() {...},
        set() {
            ...
            view.update({score})
        }
    }
})

「通关分值」与「判断通关条件」这对逻辑在本文的「游戏规则」中有相关介绍，这里不再赘述。

对外事件规划如下：

##resume Resume gameover Game over ##User interaction APIs are planned as follows:

name	detail
pass	Clear customs
pause	Pause

nameinitnextenter pauseresumedestroy6. Question

type	deltail
method	Initialize the game
method	Enter the next level
method	Enter the specified level
method	Pause
method	recovery
method	Destroy the game

There is a question about " Topic of "Destroy the Stars": How are popstar levels designed?

This topic raised a question at the end - "A matrix that cannot be eliminated and the maximum score does not meet the conditions for passing the level."

"The matrix that cannot be eliminated" is actually a matrix with a maximum score of 0. It is essentially a "matrix with a maximum score that does not meet the conditions for passing the level."

The matrix with the maximum score that does not meet the pass conditions

Finding the maximum score of the "matrix" is a "knapsack problem". The algorithm to solve it is not difficult: use "recursion" for the current matrix to eliminate all Each branch is executed once and the highest score is taken. However, the "recursion" of JavaScript can easily lead to "stack overflow", causing the algorithm to fail to execute.

In fact, a solution was mentioned in the Zhihu topic:

I found a program on the Internet that proposed a tool to randomly generate levels, automatically calculate, and filter out the levels that meet the scoring conditions

This solution is expensive! The source code provided by the author does not solve this problem, but uses a more tricky method: before entering the game, check whether it is "unable to eliminate the matrix", and if it is to regenerate the level matrix.

Related recommendations:

HTML5 Canvas API to create a simple guessing game

Use canvas to implement a maze game

The above is the detailed content of H5 development: details of realizing the game of destroying stars. For more information, please follow other related articles on the PHP Chinese website!