关于“前排非空”（non-empty front）

[AlephAlpha]

除了早期从 WLS 抄来的那些改进之外，rlifsrc 引入的改进中最简单又有效的是这两个：前排非空（non-empty front），和对角宽度。其中前排非空的选项已在 4.0 版删除：这个功能还在，只是改成根据对称性、位移、搜索顺序等条件自动开启。

不过和对角宽度比起来，前排非空不是这么直观直观。我也一直害怕有 bug，还是要写点文档总结一下，顺便也为实现 #51 中提到的更多对称性作准备。

前排非空

前排非空的想法很简单：比如说，假如我们要搜 17x5 大小向上飞的 c/3 飞船，搜索顺序是从左到右一列一列地搜，找到了这么一个玩意儿：

注意它在一个周期中的三代，最左边一列都是空的。如果我们把它 ⬅️ 向左移动一列，结果还是满足所有的条件：

于是，我们可以干脆增加一个第一列非空的条件，这样可以有效地缩减搜索空间。

这种情况下我们把第一列叫做前排（front）。如果搜索顺序是一行一行地搜，则把第一行叫做前排；如果搜索顺序是对角方向，则把第一行和第一列都算作前排。

不过，我们还需要定义什么是空——由于 B0 规则的存在，我们不能简单地把死细胞定义为空。这里我们采取的定义是：对于每一代，如果一个细胞的状态和搜索范围之外的细胞一致，则称其为空。也就是说：

• 对于无 B0 的规则，“空”的定义很简单：死细胞即为空。
• 对于有 B0 没有 S8 的 Life-like （含 non-totalistic）的规则，第奇数代死细胞为空，第偶数代活细胞为空。这里把每个周期的最前面一代称为第一代，而非第零代。
• 对于有 B0 没有 S8 的 Generations 规则，若共有 n 种状态，则对于第 i 代，i 模 n 余 1 时死细胞为空，余 2 时活细胞为空，余 3 时刚开始死亡的第一代为空，依此类推。上一条可看作这一条的特例。
• rlifesrc 不支持既有 B0 又有 S8 的规则，此类规则需手动转化为无 B0 的规则再搜。

当我们说一个细胞集合（比如说前排）为空时，指的是集合中每一个细胞都为空。同样到了，说这个集合非空指的是至少有一个细胞非空。

搜索的时候，我们可以用一个变量来记录前排中未知或已知非空的细胞的数量；每次搜到一个在前排的细胞，都根据其状态的变换来更新这个变量；如果变量变成了0，则说明当前的 partial result 不满足前排非空的条件，没必要在它上面浪费时间，可以直接回头。

然后问题来了：什么时候可以要求前排非空？

或者换句话说，怎样的搜索条件有平移不变性，即任何满足此条件的图样在向指定方向平移之后还满足同样的条件？

条件的平移不变性

我们按网页版的 Setting，从上到下一条一条分析：

• 规则：这个当然无关。
• 宽度：
  • ⬆️ 向上平移一格不影响宽度。
  • ⬅️ 向左平移一格会改变图样的左边界，但平移的前提是最左一列为空，因此此条件也不影响结果。
  • ↖️ 向左上（对角方向）平移时的前提是第一行第一列皆空，因此也没有影响。
• 高度：与宽度同理。
• 周期：也无关。
• dx：只是平移的话没有问题。
• dy：也没问题。
• 对角宽度：
  • ⬆️ 向上平移一格时可能会把图样移出对角宽度的范围。这是第一个不满足平移不变性的条件。
  • ⬅️ 同上。
  • ↖️ 向左上平移的话不会有影响。
  • 因此，在设了对角宽度的时候，除非搜索方向是对角方向，否则都不能要求前排非空。
• 变换：
  • Id：恒等变换，完全不变，完全无关。
  • 旋转：平移会导致旋转中心移动，因此不满足平移不变性。
  • 翻转：要翻转轴和平移的方向平行才行，其它情况下不满足平移不变性。
• 对称：
  • C1：没问题。
  • C2/C4：和前面旋转变换的情况一样，不满足平移不变性。
  • D2：要对称轴和平移的方向平行才行，其它情况下不满足平移不变性。
  • D4/D8：不可能两条对称轴都和平移的方向平行，因此不满足平移不变性。
• 最大活细胞数：当然无关。
• 搜索顺序：这不是图样要满足的条件的一部分，但决定了前排的定义。
• 未知细胞的状态选取：这也不是图样要满足的条件的一部分。
• 已知的细胞：已知细胞的坐标是固定的，不满足平移不变性。

后面几个选项也都无关，不一一讨论了。

也就是说，我们需要考虑的只有对角宽度、变换、对称、已知的细胞这几个选项。

半个前排

但有时我们不需要考虑整个前排：比如说，假如我们要搜 45x10 大小向左飞的 c/4 飞船，搜索顺序还是从左到右一列一列地搜，找到了这么一个玩意儿：

注意它一个周期的四个回合中，第一列的上半部分都是空的。如果我们把它上下翻转一下，结果还是满足所有的条件：

因此，我们可以要求一个第一列的上半部分非空，进一步缩减搜索空间。

（写到这里忽然发现这个条件还可以进一步加强：把第一列所有回合的细胞状态写成一个二进制数，然后要求这个二进制数不能小于把它所有数位左右翻转的结果；或者把第一列的上半部分和下半部分写到两个二进制数中，然后比较这两个数就行了。不过 Rust 中整数大小是有限的，用 64 位的整数表示的话就不支持前排超过 64 个细胞的情形；Generations 的规则要把二进制改成 n 进制，能支持的前排细胞数更少，实现上也更复杂一些。）

类似地，如果搜索顺序是一行一行地搜，则只考虑第一行的左半边；如果搜索顺序是对角方向，只考虑第一列。

为了能加上这个条件，我们要要求搜索条件在翻转变换下不变。

如果以图样中心处为原点的话，这里涉及到的三种翻转如下：

• 左右翻转：(x,y) => (-x,y)
• 上下翻转：(x,y) => (x,-y)
• 以对角线为轴翻转：(x,y) => (y,x)

（等等，写到这里我发现我的实现有个严重的 Bug：非各向同性的规则是不能随便翻转的！这有点难办……等改好这个 Bug 再继续写吧。）

（以上 Bug 已修复……希望不要引入新 Bug……）

和之前一样，所有设置从上到下一条一条分析：

• 规则：如果是各向同性的规则就不要紧，但各向异性的规则就要讨论规则的对称性，不然会出前面说的这个 Bug……
• 宽度、高度：
  • ⬆️⬅️ 左右翻转和上下翻转都不影响宽度、高度。
  • ↖️ 能以对角线为轴翻转的前提是宽度等于高度。
• dx、dy
  • ⬆️ 左右翻转会使 dx 变成 -dx，因此 dx 必须为 0；dy 不影响。
  • ⬅️ 上下翻转会使 dy 变成 -dy，因此 dy 必须为 0；dx 不影响。
  • ↖️ 以对角线为轴翻转会让 dx 和 dy 互换，因此 dx 必须等于 dy。
• 对角宽度：
  • ⬆️⬅️ 只有无对角宽度时才能左右翻转和上下翻转。
  • ↖️ 以对角线为轴翻转的话不会有影响。
• 变换：此变换必须和相应的翻转可交换。
  • Id：恒等变换，完全不变，完全无关。
  • 旋转 90°/270°：和所有翻转都不可交换，也就是说先旋转后翻转和先翻转后旋转结果不同。
  • 旋转 180°：这个和所有翻转都交换。
  • 翻转：任一个翻转都和自己可交换。此外左右翻转和上下翻转可交换，以对角线为轴和以反对角线为轴的两个翻转也可交换。别的都不行。
• 对称：这次需要此对称性要求不变的所有变换都和该翻转可交换
  • C1：没问题。
  • C2：和前面旋转 180° 的情形一样，都可以。
  • C4：和前面旋转 90° 的情况一样，都不行。
  • D2：需要 D2 的对称轴和翻转轴平行或垂直才行。
  • D4：需要 D4 的对称轴和翻转轴平行或垂直才行。两个对称轴，一个平行一个垂直。
  • D8：不行。
• 最大活细胞数：当然无关。
• 搜索顺序：这不是图样要满足的条件的一部分，但决定了沿哪条轴翻转。
• 未知细胞的状态选取：这也不是图样要满足的条件的一部分。
• 已知的细胞：已知细胞的坐标是固定的，不满足翻转不变性，除非它就在翻转轴上。

看起来变换、对称和已知细胞的条件比前排非空要宽松。不过我们是在要求前排非空的前提下才能考虑半个前排，所以实际新增的条件只有规则（差点又忘了）、宽度、高度、dx、dy 这些。

前排的第一代

前面说的前排指的是前排的每一代。要求前排非空等价于要求至少有一代的前排非空。于是，对于振荡子（也就是 dx、dy 为 0 的情形），只要规则没有 B0，我们可以干脆前排非空的那一代定为第一代，于是可以要求前排的第一代非空，进一步缩减搜索空间。

但对飞船来说，问题没这么简单。事实上，对于周期为 p 的振荡子，第 p+1 代和第一代是一样的，因此第二代到第 p+1 代也满足原本的条件。但对飞船来说，第 p+1 代相比第一代还会有一个平移，可能会平移出原本的高度和宽度所规定的范围。

不过，搜索飞船的一种常见情况是：每个周期仅平移一格，而且平移的方向正好是向着前排。

比如说，假如我们要搜 21x13 大小向左飞的 c/4 飞船，对称性是 D2-，搜索顺序还是从左到右一列一列地搜，找到了这么一个玩意儿（这次把每一代都画出来了，从左到右）：

这飞船前排的第一代是空的。于是，它的第五代只是把第一代向前平移一格，并不会移出规定的范围。也就是说，它的第二到第五代也满足原本的条件：

因此，这种情况下也可以要求前排的第一代非空。

也就是说，如果要要求前排的第一代非空，在前排非空的条件的基础上，我们还需要：

• ⬆️ 一行一行搜时，要 dx = 0, 0 <= dy <= 1，而且规则不能有 B0。
• ⬅️ 一列一列搜时，要 dy = 0, 0 <= dx <= 1，而且规则不能有 B0。
• ↖️ 对角方向搜时，要 dx = dy, 0 <= dx <= 1，而且规则不能有 B0。

（写到这里忽然发现，没必要完全禁掉 B0 的规则，其实可以改成要求前排的前两代非空；对于 Generations 的规则，若有 n 种状态，则可以改为前排的前 n 代非空。这里需要的改动很小，已改。）

没那么前的前排

上一节的讨论只适合飞船每个周期向前平移一格的情形。如果平移不止一格呢？

此时，我们不能再要求前排的第一代非空。事实上，此时前排的第一代必须是空的，因为这些细胞的前一代的整个邻域都已经在搜索范围之外。

不过，我们可以把“前排”往后挪一挪。

比如说，假如我们要搜 12x15 大小向左飞的 2c/5 飞船，对称性是 D2-，搜索顺序还是从左到右一列一列地搜，找到了这么一个玩意儿（这次把每一代都画出来了，从左到右）：

它第一代前两列都是空的。第六代只是把第一代向前移动两格，不会移出规定的范围。于是，和之前一样，我们可以考虑它的第二到第六代：

于是，我们可以干脆把前排的定义从第一列移到第二列，继续要求新的“前排”的第一代非空。

一般地，如果飞船每个周期向前平移 d 格（平移的方向必须向着前排），我们就可以把前排的定义修改为第 d-1 行/列/行加列。

但我们还要说明新的要求比原本要求的前排（所有代）非空要强，不然直接用原本的要求不就行了吗？

这也不难。一个细胞非空的必要条件是它前一代的邻域中至少有一个细胞非空。若飞船周期为 p，新的前排是第 d-1 列，那么新前排的前一代对应于第 p 代往前刚离开搜索范围的那一列，其邻域的三列只有一列在搜索范围之内，也就是第 p 代的第一列。因此，只要要求新的前排第一代非空，旧的前排就一定也非空。

于是，我们可以把上一节的条件改进为：

• ⬆️ 一行一行搜时，要 dx = 0, dy >= 0，而且规则不能有 B0，此时。
• ⬅️ 一列一列搜时，要 dy = 0, dx >= 0，而且规则不能有 B0。
• ↖️ 对角方向搜时，要 dx = dy, dx >= 0，而且规则不能有 B0。

此时“前排”的定义为：

• ⬆️ 若 dy = 0，则前排还是第一行，否则改为第 dy-1 行。
• ⬅️ 若 dx = 0，则前排还是第一列，否则改为第 dx-1 列。
• ↖️ 若 dx = 0，则前排还是第一行加第一列，否则改为第 dy-1 行加第 dx-1 列。

目前 rlifesrc 采用的前排非空的条件就是这么多。

自定义对称性

前面说了这么多，一方面是为了总结和查 bug，另一方面是为实现 #51 中提到的自定义对称性做准备。

其实说“自定义对称性”有点不准确，因为这也包含了一些不属于对称性的条件。

我们想要支持哪些条件呢？先试着列举一下。

• 给定一个细胞，指定其状态。这个其实已经通过“已知的细胞”实现了。
• 给定一个细胞，要求其状态和另一个指定的细胞一致/不一致。
• 给定一个区域，要求区域内的所有细胞都处于某个指定的状态。
• 给定一个区域，要求其状态和该区域通过某种变换得到的另一个区域一致/不一致。

区域怎么定义，允许哪些变换，都是需要讨论的。

自定义对称性最好还能写成一种方便读取的格式，比如说 JSON。

（未完待续）

[AlephAlpha]

啊啊啊，又忘了考虑 B0 的规则……

先在前面加一句注意，以后再补充。已补充。

[AlephAlpha]

本想这个春节假期实现自定义对称性的，不过都偷懒去了……

接下来这段时间我会比较忙，没时间更新 rlifesrc （除了 dependabot 推送的更新）。不过关于自定义对称性有什么好的建议都可以提。@HuntingBot @yujh-yujh （好像@不到）