用H5教你如何做游戏——消灭星星(2)

如果把传统意义上的均分称作「完全均分」，那么「消灭星星」的分配是一种在均分线上下波动的「不完全均分」。
image
笔者把上面的「不完全均分」称作「波动均分」，算法的具体实现可以参见「波动均分算法」。「打散色砖」其实就是将数组乱序的过程，笔者推荐使用「 费雪耶兹乱序算法」。
以下是伪代码的实现：
image
2 .消除砖块
「消除砖块」的规则很简单 —— 相邻相连通相同色即可以消除。
image
前两个组合符合「相邻相连通相同色即可以消除」，所以它们可以被消除；第三个组合虽然「相邻相同色」但是不「相连通」所以它不能被消除。
「消除砖块」的同时有一个重要的任务：生成砖块对应的分值。在「游戏规则」中，笔者已经提供了对应的数学公式：「消除砖块得分值 = 10 * i 5」。
image
「消除砖块」算法实现如下：
image
清除的算法使用「递归」逻辑上会清晰一些，不过「递归」在浏览器上容易「栈溢出」，所以笔者没有使用「递归」实现。
3. 夯实砖墙
砖墙在消除了部分砖块后，会出现空洞，此时需要对墙体进行夯实：
|
image
|
image
|
image
|
| --- | --- | --- |
| 向下夯实 | 向左夯实 | 向左下夯实（先下后左） |
一种快速的实现方案是，每次「消除砖块」后直接遍历砖墙数组（10x10数组）再把空洞夯实，伪代码表示如下：
image
But… 为了夯实一个空洞对一张大数组进行全量遍历并不是一种高效的算法。在笔者看来影响「墙体夯实」效率的因素有：
定位空洞
砖块移动（夯实）
image
扫描墙体数组的主要目的是「定位空洞」，但能否不扫描墙体数组直接「定位空洞」？
墙体的「空洞」是由于「消除砖块」造成的，换种说法 —— 被消除的砖块留下来的坑位就是墙体的空洞。在「消除砖块」的同时标记空洞的位置，这样就无须全量扫描墙体数组，伪代码如下：
image
在上面的夯实动图，其实可以看到它的夯实过程如下：
空洞上方的砖块向下移动
空列右侧的砖块向左移动
墙体在「夯实」过程中，它的边界是实时在变化，如果「夯实」不按真实边界进行扫描，会产生多余的空白扫描：
如何记录墙体的边界？
把墙体拆分成一个个单独的列，那么列最顶部的空白格片段就是墙体的「空白」，而其余非顶部的空白格片段即墙体的「空洞」。
image
笔者使用一组「列集合」来描述墙体的边界并记录墙体的空洞，它的模型如下：
image
这个模型可以描述墙体的三个细节：