H5游戏开发：消灭星星

by leeenx on 2018-01-17

详细介绍消灭星星游戏的实现（带源码）

「消灭星星」是一款很经典的「消除类游戏」，它的玩法很简单：消除相连通的同色砖块。

1. 游戏规则

「消灭星星」存在多个版本，不过它们的规则除了「关卡分值」有些出入外，其它的规则都是一样的。笔者介绍的版本的游戏规则整理如下：

1. 色砖分布

• 10 x 10 的表格
• 5种颜色 —— 红、绿、蓝，黄，紫
• 每类色砖个数在指定区间内随机
• 5类色砖在 10 x 10 表格中随机分布

2. 消除规则

两个或两个以上同色砖块相连通即是可被消除的砖块。

3. 分值规则

• 消除总分值 = n * n * 5
• 奖励总分值 = 2000 - n * n * 20

「n」表示砖块数量。上面是「总」分值的规则，还有「单」个砖块的分值规则：

• 消除砖块得分值 = 10 * i + 5
• 剩余砖块扣分值 = 40 * i + 20

「i」表示砖块的索引值（从 0 开始）。简单地说，单个砖块「得分值」和「扣分值」是一个等差数列。

4. 关卡分值

关卡分值 = 1000 + (level - 1) * 2000；「level」即当前关卡数。

5. 通关条件

• 可消除色块不存在
• 累计分值 >= 当前关卡分值

上面两个条件同时成立游戏才可以通关。

2. MVC 设计模式

笔者这次又是使用了 MVC 模式来写「消灭星星」。星星「砖块」的数据结构与各种状态由 Model 实现，游戏的核心在 Model 中完成；View 映射 Model 的变化并做出对应的行为，它的任务主要是展示动画；用户与游戏的交互由 Control 完成。

从逻辑规划上看，Model 很重而View 与 Control 很轻，不过，从代码量上看，View 很重而 Model 与 Control 相对很轻。

3. Model

10 x 10 的表格用长度为 100 的数组可完美映射游戏的星星「砖块」。

R - 红色，G - 绿色，B - 蓝色，Y - 黄色，P - 紫色。Model 的核心任务是以下四个：

• 生成砖墙
• 消除砖块 （生成砖块分值）
• 夯实砖墙
• 清除残砖 （生成奖励分值）

3.1 生成砖墙

砖墙分两步生成：

• 色砖数量分配
• 打散色砖

理论上，可以将 100 个格子可以均分到 5 类颜色，不过笔者玩过的「消灭星星」都不使用均分策略。通过分析几款「消灭星星」，其实可以发现一个规律 —— 「色砖之间的数量差在一个固定的区间内」。

如果把传统意义上的均分称作「完全均分」，那么「消灭星星」的分配是一种在均分线上下波动的「不完全均分」。

笔者把上面的「不完全均分」称作「波动均分」，算法的具体实现可以参见「波动均分算法」。

「打散色砖」其实就是将数组乱序的过程，笔者推荐使用「 费雪耶兹乱序算法」。

以下是伪代码的实现：

3.2 消除砖块

「消除砖块」的规则很简单 —— 相邻相连通相同色即可以消除。

前两个组合符合「相邻相连通相同色即可以消除」，所以它们可以被消除；第三个组合虽然「相邻相同色」但是不「相连通」所以它不能被消除。

「消除砖块」的同时有一个重要的任务：生成砖块对应的分值。在「游戏规则」中，笔者已经提供了对应的数学公式：「消除砖块得分值 = 10 * i + 5」。

「消除砖块」算法实现如下：

清除的算法使用「递归」逻辑上会清晰一些，不过「递归」在浏览器上容易「栈溢出」，所以笔者没有使用「递归」实现。

3.3 夯实砖墙

砖墙在消除了部分砖块后，会出现空洞，此时需要对墙体进行夯实：

向下夯实	向左夯实	向左下夯实（先下后左）

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

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

1. 定位空洞
2. 砖块移动（夯实）

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

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

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

1. 空洞上方的砖块向下移动
2. 空列右侧的砖块向左移动

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

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

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

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

• 空列
• 列的连续空洞
• 列的非连续空洞

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

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

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

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

3.4 消除残砖

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

4. View

View 主要的功能有两个：

• UI 管理
• 映射 Model 的变化（动画）

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

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

5. Control

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

• 绑定 Model & View
• 生成通关分值
• 判断通关条件
• 对外事件
• 用户交互

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

1Object.defineProperties(model.tile, {
2    originIndex: {
3        get() {...}, 
4        set(){
5            ...
6            view.update({originIndex})
7        }
8    },  
9    index: {
10        get() {...}, 
11        set() {
12            ...
13            view.update({index})
14        }
15    }, 
16    clr: {
17        get() {...}, 
18        set() {
19            ...
20            view.update({clr})
21        }
22    }, 
23    removed: {
24        get() {...}, 
25        set() {
26            ...
27            view.update({removed})
28        }
29    },  
30    score: {
31        get() {...}, 
32        set() {
33            ...
34            view.update({score})
35        }
36    }
37}) 

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

对外事件规划如下：

用户交互 APIs 规划如下：

6. 问题

在知乎有一个关于「消灭星星」的话题：popstar关卡是如何设计的？

这个话题在最后提出了一个问题 —— 「无法消除和最大得分不满足过关条件的矩阵」。

「无法消除的矩阵」其实就是最大得分为0的矩阵，本质上是「最大得分不满足过关条件的矩阵」。

最大得分不满足过关条件的矩阵
求「矩阵」的最大得分是一个 「背包问题」，求解的算法不难：对当前矩阵用「递归」的形式把所有的消灭分支都执行一次，并取最高分值。但是 javascript 的「递归」极易「栈溢出」导致算法无法执行。

其实在知乎的话题中提到一个解决方案：

网上查到有程序提出做个工具随机生成关卡，自动计算，把符合得分条件的关卡筛选出来

这个解决方案代价是昂贵的！笔者提供有源码并没有解决这个问题，而是用一个比较取巧的方法：进入游戏前检查是事为「无法消除矩阵」，如果是重新生成关卡矩阵。

注意：笔者使用的取巧方案并没有解决问题。

7. 结语

下面是本文介绍的「消灭星星」的线上 DEMO 的二维码：

游戏的源码托管在：https://github.com/leeenx/popstar

感谢耐心阅读完本文章的读者。本文仅代表笔者的个人观点，如有不妥之处请不吝赐教。
如果对「H5游戏开发」感兴趣，欢迎关注我们的专栏。

参考资料

• Knapsack problem
• NP-completeness
• popstar关卡是如何设计的？
• 费雪耶兹乱序算法
• 波动均分算法

游戏 H5 canvas game 消灭星星 popstar pixijs

H5游戏开发

感谢您的阅读，本文由 凹凸实验室 版权所有。如若转载，请注明出处：凹凸实验室（https://aotu.io/notes/2018/01/17/popstar/）

上次更新：2021-02-02 15:48:05

H5游戏开发：FC小蜜蜂

波动均分算法

var gitalkOpts={id:"bm90ZXMvMjAxOC8wMS8xNy9wb3BzdGFyLw==",owner:"o2team",repo:"o2team.github.io",title:"H5游戏开发：消灭星星",body:"https://aotu.io/notes/2018/01/17/popstar/index.html\\n\\n详细介绍消灭星星游戏的实现（带源码）",clientID:"3c4d153e6874260f9c7e",clientSecret:"dd44012504c6168bc05b9266e0554bb28c62ce15",admin:\["leeenx"\]}

本文转自 https://aotu.io/notes/2018/01/17/popstar/，如有侵权，请联系删除。