召唤与合成2中的多消落点问题的解谜与分析

Abstract

召唤于合成2是召合网络的一款三消手游（至少对于本文及作者来说可以是）。由于其盘面较大，初始情况下的消除物种类较少，出现多消，即消除数量大于三的可能性很高。而在未指定落点的情况下，消除的落点又往往令玩家摸不着头脑。因此在本文中作者提出了一种可能的，在无特殊效果的情况下，符合实验结果的一种解释多消落点的模型。

Problem

(资料图)

在召唤与合成2中的消除过程

在彻底将问题抽象化之前，首先需要解释的是在游戏中的消除流程。在游戏中，不考虑词条，正负面效果，英雄主动和被动技能的话，可以把消除流程概括如下：

1. 玩家移动盘面

2. 判断消除范围

3. 合成需要消除的部分

4. 下落并重新填充因合成而产生的空位

5. 若仍有消除，回到2；否则回到1

其中，当第一次进行2时，消除的落点必定是玩家进行交换的格子，本文就不做解释、验证和证明了。而在游戏中，盘体现为2维的方形棋盘，其中填充满了数种可消除的棋子，或者是不可消除的负面格子，亦或者是不可消除、不反应、不填充的null格用于修整盘的形状。

接下来本文将简略解释2和3两步，具体的实现在后文会有提及。第二步的消除范围可以概括为：

若同一方向上存在3个或以上的相同可消除物，则这一方向上的相同可消除物都在此消除范围内。此处的范围指的是在方格盘中的八个方向。

若两个消除范围共享至少一个格子，则这两个消除范围会被合并为同一个。

同一盘面上可以同时存在多个不相交的消除范围。

第三步就是消除与合成。在通常情况下，合成产物是被消除物同种且等阶+1的可消除物。在游戏中体现为形态上升一级，额外形态为且被消除物的额外形态之和，同时盘面分数（即形态中）增加被消除物的基础分*（多消数量-2）。盘面分数问题并非本文重点，以后有机会再行叙述。消除后，合成产物出现的格子就称之为消除的落点，而除了落点之外的位置就变成空气，待到后面被下落填充。

抽象化的多消落点问题

在阐述抽象化的问题之前，本文首先做出两点假设。第一是多消落点是非随机的，第二是多消落点是非枚举的。做出这两点假设是基于两点观测，其一是消除落点是可复现的，其二是消除范围的形状对于枚举或查表来说过于复杂了。这两点在实验中有所体现，但不会在本文进行验证。

抽象化的消除落点问题可以这样表述。在n*n的二维方格表中T，存在由若干方格组成的图形集合g，假设由所有满足条件的图形g组成的集合G，存在一种映射f: G->T，使得G中的每个图形都在T中对应唯一的落点，求映射f。

其中，集合G中的元素g需要满足如下条件：

对g中的任意一点g，在四个方向上必须存在连续的至少三个格子（包括g本身）在g中。

g的尺寸必须大于等于3。

接下来，必须严谨的定义方向。对于n*n的二维方格表来说，其中的任意格子x具有坐标(a,b)，而a, b都是范围[0, n)之中的整数。与一般的习惯不同，本文根据召唤与合成中的代码逻辑，将a定义为纵轴坐标，b定义为横轴坐标，且(0, 0)在左下角。那么四个方向按定义及游戏内的判定顺序分别是：

上下：形如(a + i, b)，i是整数且(a+i)在范围[0, n)之中的格子，在x的上下方向上

右左：形如(a, b + i)，i为整数且(b+i)在范围[0, n)之中的格子。

右上-左下：(a + i, b + i)

左上-右下：(a + i, b - i)

值得注意的是，在游戏中的判定顺序是按上面表述的顺序进行的，且同一方向中先判定i的正方向再判定i的负方向。另外，本文假设三消和多消的落点计算逻辑共通，因此多消落点与消除落点等价。

实验方法

作者提出了多种消除落点模型，在这一段仅阐述最终符合实验结果的一种。首先作者假设图形g实际上是一个有序集合，集合内的排序是在判定消除范围的过程中进入集合的顺序。而落点将会是集合中序号序号的中点，即集合尺寸的一半(从0开始数且向下取整)。

实验数据可以根据游戏内英雄试用的功能获得。由于该模式的盘面只有5*5，实验数据的覆盖面有限，但作者懒得管。

而决定进入集合的顺序的过程则稍显复杂。根据不久前的消除解谜活动可知，填充空气的顺序是从下到上，从左往右。而起点在左下角且优先从下往上。作者假设消除范围的判定遵循同样的逻辑。那么因此在图形g的所有元素(a, b)中，拥有最小的b且a最小的格子永远是判定起点，其序号记为0。 接下来把起点位计入一个栈中。重复以下操作直到栈为空：从栈中取最后一位(stack pop)，按顺序检查四个方向是否有三个以上(两个以上加上本身)连续的格子在g中，若存在，则把1到正方向末端推入栈中(stack push)，再把-1到负方向末端推入栈中。此处检查和推入栈中的顺序与前文定义方向时相同。

这个过程写成伪代码如下

取图形左下角为0

把位置0加入栈中

若栈不为空则循环：

从栈中取出x

循环四个方向：

若此方向有三个以上连续的元素y_i在g中，则把正方向推入栈，再把负方向推入栈。若已标号，则不重复入栈。

子循环结束

循环结束

按推入栈的顺序标记g中元素的序号，返回序号为|g|/2的元素。

实验结果

这里也放出大部分作为实验的结果，黄色格子和红色格子代表消除范围，而红色格子是消除落点。虽然由于下落是沿纵轴的因此同一纵轴上的结果在游戏中等价，但是对于本问题而言并非如此。

这两张图没有列出直线消除的情况，原因是过于简单，按顺序表过去就是了。

而根据上述模型编号后，可以看到红色格子与序号中点重合。

经过编号后可以看出，三消落点在编号1，四五消落点是编号2，六七落点是3，以此类推。显而易见的实验得出的落点符合模型。

讨论

可能的代码实现

这里给出一种可能的伪代码（虽然是py)。这段伪代码包括了节中提到的判断消除范围和消除落点的计算。whz不对此py代码的可靠性和正确性做出保证，因为这是我随手写的，仅供参考。

逻辑的成因分析

其实简单观察就能发现，这个模型中的搜索过程既不是DFS也不是BFS。这是一种畸形的搜索过程。同时也不是一种高效的实现方法，因为在循环四个方向寻找相同消除物的过程中多次重复尝试探索了几个格子。将其搜索遍历的过程换成树形会更明显

由于DFS与BFS分别对应栈和队列，其过程会相对简洁和直观。作者推测实现该过程的程序员对于如何在循环中遍历四个方向有困难或是其他原因拒绝使用循环，因此用来BFS类似的过程来标记需要探索的格子，这样可以线性地写出四个方向的检测。同时可能为了节约内存，此程序员希望使用DFS所类似的栈结构尽快降低待探索格子的数量，因此做了一个结合。作者询问了朋友且搜索了相关算法，没有找到这样搜索算法的名字，大概这也是一种创新吧。

相同过程的其他实现

前文提到，作者最开始提出了不止一种模型，在这一节中就简单叙述一下。其中两种分别对应了深度优先搜索DFS和宽度优先搜索BFS，在此不再赘述。

另外一种算法是合并法，也是作者认为效率更高的模型。即，对盘中格子进行循环，若四个方向上至少有1个方向的正负一格和本格相同，则这是一个范围。若新的范围与之前存在的范围重合，则合并两个或多个。此时落点仍然可以是进入范围的顺序（当然这样与实验结果不符）。这个方法下格子被调用的次数固定，每个格子不超过4次（自身四个方向）+8次（由周边发起的探索）。同时具有实现简洁和运算简单的优势其实也没有好多少（没什么别的意思whz只是觉得召合优化太菜）。

运算模型其实还包括重心模型，方向优先模型之类的需要坐标运算的模型，很遗憾都被排除出去了。我就是很难理解为什么是这么个不论不类的算法。

结语

whz也是消除游戏的老玩家了，老版开心消消乐也有两千多关通关加一千多关满星，可惜这消消乐后来硬堆难度和无用的系统，削道具获取就退了。偶然看到召合就下下来玩玩，有各种词条的情况下变化也挺多，当然本文并没有进行讨论。因为有分数的存在后来也是萌生了想要暴力运算最优解的想法，为此消除落点问题就成了绕不过去的砍。由于没有找到教程就自己解了个迷，很有趣啊，愚蠢的程序员。

Reference

什么写这玩意还要写引用。图是我excel做的，实验是在游戏内完成的。那张树图是百度(Google)找的BFS顺序树改的。感谢Aliujiji的答疑，以及不弃教程里的的那张3*3范围内的五消图（虽然我没有放到文中而且另外做了一张）。