H5開發(fā)：實(shí)現(xiàn)消滅星星游戲的詳細(xì)內(nèi)容

「消滅星星」是一款很經(jīng)典的「消除類游戲」，它的玩法很簡(jiǎn)單：消除相連通的同色磚塊。

1. 游戲規(guī)則

「消滅星星」存在多個(gè)版本，不過它們的規(guī)則除了「關(guān)卡分值」有些出入外，其它的規(guī)則都是一樣的。筆者介紹的版本的游戲規(guī)則整理如下：

1. 色磚分布

10 x 10 的表格

5種顏色 —— 紅、綠、藍(lán)，黃，紫

每類色磚個(gè)數(shù)在指定區(qū)間內(nèi)隨機(jī)

5類色磚在 10 x 10 表格中隨機(jī)分布

2. 消除規(guī)則

兩個(gè)或兩個(gè)以上同色磚塊相連通即是可被消除的磚塊。

3. 分值規(guī)則

消除總分值 = n * n * 5

獎(jiǎng)勵(lì)總分值 = 2000 – n * n * 20

「n」表示磚塊數(shù)量。上面是「總」分值的規(guī)則，還有「單」個(gè)磚塊的分值規(guī)則：

消除磚塊得分值 = 10 * i + 5

剩余磚塊扣分值 = 40 * i + 20

「i」表示磚塊的索引值（從 0 開始）。簡(jiǎn)單地說，單個(gè)磚塊「得分值」和「扣分值」是一個(gè)等差數(shù)列。

4. 關(guān)卡分值

關(guān)卡分值 = 1000 + (level – 1) * 2000；「level」即當(dāng)前關(guān)卡數(shù)。

5. 通關(guān)條件

可消除色塊不存在

累計(jì)分值 >= 當(dāng)前關(guān)卡分值

上面兩個(gè)條件同時(shí)成立游戲才可以通關(guān)。

2. MVC 設(shè)計(jì)模式

筆者這次又是使用了 MVC 模式來寫「消滅星星」。星星「磚塊」的數(shù)據(jù)結(jié)構(gòu)與各種狀態(tài)由 Model 實(shí)現(xiàn)，游戲的核心在 Model 中完成；View 映射 Model 的變化并做出對(duì)應(yīng)的行為，它的任務(wù)主要是展示動(dòng)畫；用戶與游戲的交互由 Control 完成。

從邏輯規(guī)劃上看，Model 很重而View 與 Control 很輕，不過，從代碼量上看，View 很重而 Model 與 Control 相對(duì)很輕。

3. Model

10 x 10 的表格用長(zhǎng)度為 100 的數(shù)組可完美映射游戲的星星「磚塊」。

[
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 – 紅色，G – 綠色，B – 藍(lán)色，Y – 黃色，P – 紫色。Model 的核心任務(wù)是以下四個(gè)：

生成磚墻

消除磚塊 （生成磚塊分值）

夯實(shí)磚墻

清除殘磚 （生成獎(jiǎng)勵(lì)分值）

3.1 生成磚墻

磚墻分兩步生成：

色磚數(shù)量分配

打散色磚

理論上，可以將 100 個(gè)格子可以均分到 5 類顏色，不過筆者玩過的「消滅星星」都不使用均分策略。通過分析幾款「消滅星星」，其實(shí)可以發(fā)現(xiàn)一個(gè)規(guī)律 —— 「色磚之間的數(shù)量差在一個(gè)固定的區(qū)間內(nèi)」。

如果把傳統(tǒng)意義上的均分稱作「完全均分」，那么「消滅星星」的分配是一種在均分線上下波動(dòng)的「不完全均分」。

筆者把上面的「不完全均分」稱作「波動(dòng)均分」，算法的具體實(shí)現(xiàn)可以參見「波動(dòng)均分算法」。

「打散色磚」其實(shí)就是將數(shù)組亂序的過程，筆者推薦使用「 費(fèi)雪耶茲亂序算法」。

以下是偽代碼的實(shí)現(xiàn)：

// 波動(dòng)均分色磚
waveaverage(5, 4, 4).forEach(
// tiles 即色墻數(shù)組
(count, clr) => tiles.concat(generateTiles(count, clr));
);
// 打散色磚
shuffle(tiles);

3.2 消除磚塊

「消除磚塊」的規(guī)則很簡(jiǎn)單 —— 相鄰相連通相同色即可以消除。

前兩個(gè)組合符合「相鄰相連通相同色即可以消除」，所以它們可以被消除；第三個(gè)組合雖然「相鄰相同色」但是不「相連通」所以它不能被消除。

「消除磚塊」的同時(shí)有一個(gè)重要的任務(wù)：生成磚塊對(duì)應(yīng)的分值。在「游戲規(guī)則」中，筆者已經(jīng)提供了對(duì)應(yīng)的數(shù)學(xué)公式：「消除磚塊得分值 = 10 * i + 5」。

「消除磚塊」算法實(shí)現(xiàn)如下：

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); // 標(biāo)記當(dāng)前分值
deleteTile(tile); // 刪除磚塊
});
// 清除完成，跳出循環(huán)
if(nextSameTiles.length === 0) break;
else {
sameTiles = nextSameTiles;
}
}
}
}

清除的算法使用「遞歸」邏輯上會(huì)清晰一些，不過「遞歸」在瀏覽器上容易「棧溢出」，所以筆者沒有使用「遞歸」實(shí)現(xiàn)。

3.3 夯實(shí)磚墻

磚墻在消除了部分磚塊后，會(huì)出現(xiàn)空洞，此時(shí)需要對(duì)墻體進(jìn)行夯實(shí)：

向下夯實(shí) 向左夯實(shí)

向左下夯實(shí)（先下后左）

一種快速的實(shí)現(xiàn)方案是，每次「消除磚塊」后直接遍歷磚墻數(shù)組（10×10數(shù)組）再把空洞夯實(shí)，偽代碼表示如下：

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

But… 為了夯實(shí)一個(gè)空洞對(duì)一張大數(shù)組進(jìn)行全量遍歷并不是一種高效的算法。在筆者看來影響「墻體夯實(shí)」效率的因素有：

定位空洞

磚塊移動(dòng)（夯實(shí)）

掃描墻體數(shù)組的主要目的是「定位空洞」，但能否不掃描墻體數(shù)組直接「定位空洞」？

墻體的「空洞」是由于「消除磚塊」造成的，換種說法 —— 被消除的磚塊留下來的坑位就是墻體的空洞。在「消除磚塊」的同時(shí)標(biāo)記空洞的位置，這樣就無須全量掃描墻體數(shù)組，偽代碼如下：

function deleteTile(tile) {
// 標(biāo)記空洞
markHollow(tile.index);
// 刪除磚塊邏輯
...
}

在上面的夯實(shí)動(dòng)圖，其實(shí)可以看到它的夯實(shí)過程如下：

空洞上方的磚塊向下移動(dòng)

空列右側(cè)的磚塊向左移動(dòng)

墻體在「夯實(shí)」過程中，它的邊界是實(shí)時(shí)在變化，如果「夯實(shí)」不按真實(shí)邊界進(jìn)行掃描，會(huì)產(chǎn)生多余的空白掃

如何記錄墻體的邊界？
把墻體拆分成一個(gè)個(gè)單獨(dú)的列，那么列最頂部的空白格片段就是墻體的「空白」，而其余非頂部的空白格片段即墻體的「空洞」。

筆者使用一組「列集合」來描述墻體的邊界并記錄墻體的空洞，它的模型如下：

/*
@ count - 列磚塊數(shù)
@ start - 頂部行索引
@ end - 底部行索引
@ pitCount - 坑數(shù)
@ topPit - 最頂部的坑
@ bottomPit - 最底部的坑
*/
let wall = [
{count, start, end, pitCount, topPit, bottomPit},
{count, start, end, pitCount, topPit, bottomPit},
...
];

這個(gè)模型可以描述墻體的三個(gè)細(xì)節(jié)：

空列

列的連續(xù)空洞

列的非連續(xù)空洞

// 空列
if(count === 0) {
...
}
// 連續(xù)空洞
else if(bottomPit - topPit + 1 === pitCount) {
...
}
// 非連續(xù)空洞
else {
...
}

磚塊在消除后，映射到單個(gè)列上的空洞會(huì)有兩種分布形態(tài) —— 連續(xù)與非連續(xù)。

「連續(xù)空洞」與「非連續(xù)空洞」的夯實(shí)過程如下：

其實(shí)「空列」放大于墻體上，也會(huì)有「空洞」類似的分布形態(tài) —— 連續(xù)與非連續(xù)

它的夯實(shí)過程與空洞類似，這里就不贅述了。

3.4 消除殘磚

上一小節(jié)提到了「描述墻體的邊界并記錄墻體的空洞」的「列集合」，筆者是直接使用這個(gè)「列集合」來消除殘磚的，偽代碼如下：

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++; // 標(biāo)記獎(jiǎng)勵(lì)分?jǐn)?shù)
tile.removed = true;
}
}
}

4. View

View 主要的功能有兩個(gè)：

UI 管理

映射 Model 的變化（動(dòng)畫）

UI 管理主要是指「界面繪制」與「資源加載管理」，這兩項(xiàng)功能比較常見本文就直接略過了。View 的重頭戲是「映射 Model 的變化」并完成對(duì)應(yīng)的動(dòng)畫。動(dòng)畫是復(fù)雜的，而映射的原理是簡(jiǎn)單的，如下偽代碼：

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);
}
// 當(dāng)前索引變化 ----- 表示位置也有變化
if(tile.index !== index) {
this.updateTileIndex(tile, index);
}
// 設(shè)置分?jǐn)?shù)
if(tile.score !== score) {
tile.score = score;
}
if(tile.removed !== removed) {
// 移除或添加當(dāng)前節(jié)點(diǎn)
true === removed ? this.bomb(tile) : this.area.addChild(tile.sprite);
tile.removed = removed;
}
}

Model 的磚塊每次數(shù)據(jù)的更改都會(huì)通知到 View 的磚塊，View 會(huì)根據(jù)對(duì)應(yīng)的變化做對(duì)應(yīng)的動(dòng)作（動(dòng)畫）。

5. Control

Control 要處理的事務(wù)比較多，如下：

綁定 Model & View

生成通關(guān)分值

判斷通關(guān)條件

對(duì)外事件

用戶交互

初始化時(shí)，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})
 }
 }
})

「通關(guān)分值」與「判斷通關(guān)條件」這對(duì)邏輯在本文的「游戲規(guī)則」中有相關(guān)介紹，這里不再贅述。

對(duì)外事件規(guī)劃如下：

用戶交互 APIs 規(guī)劃如下：

6. 問題

在知乎有一個(gè)關(guān)于「消滅星星」的話題：popstar關(guān)卡是如何設(shè)計(jì)的？

這個(gè)話題在最后提出了一個(gè)問題 —— 「無法消除和最大得分不滿足過關(guān)條件的矩陣」。

「無法消除的矩陣」其實(shí)就是最大得分為0的矩陣，本質(zhì)上是「最大得分不滿足過關(guān)條件的矩陣」。

最大得分不滿足過關(guān)條件的矩陣
求「矩陣」的最大得分是一個(gè) 「背包問題」，求解的算法不難：對(duì)當(dāng)前矩陣用「遞歸」的形式把所有的消滅分支都執(zhí)行一次，并取最高分值。但是 javascript 的「遞歸」極易「棧溢出」導(dǎo)致算法無法執(zhí)行。

其實(shí)在知乎的話題中提到一個(gè)解決方案：

網(wǎng)上查到有程序提出做個(gè)工具隨機(jī)生成關(guān)卡，自動(dòng)計(jì)算，把符合得分條件的關(guān)卡篩選出來

這個(gè)解決方案代價(jià)是昂貴的！筆者提供有源碼并沒有解決這個(gè)問題，而是用一個(gè)比較取巧的方法：進(jìn)入游戲前檢查是事為「無法消除矩陣」，如果是重新生成關(guān)卡矩陣。

聲明：本網(wǎng)頁內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com