一个字节,一次查表:FrankMatch3LocalScan 三消图形局部扫描算法

多数三消代码先找出连线,再判断它是什么形状。FrankMatch3LocalScan 把两步合成一步:只在刚移动的棋子周围采样 8 个格子,结合移动方向打包成一个字节,再从预先算好的表里直接查出图形。代码已开源,并附一个最小化的 Unity 示例。

FrankMatch3LocalScan 是 Frank 为三消游戏项目 《War of Matches》(项目暂定名)写的一个算法。它的任务很小,但每时每刻都在执行:每当一个棋子落位,立即回答"有没有形成图形、是哪一种"。在这个游戏里,图形本身和"是否消除"同样重要:三连、L 形、T 形、2×2 方块,各自触发不同的效果。

代码现以 MIT 许可开源:github.com/imadyTech/FrankMatch3LocalScan。仓库里新增了一个最小化的 Unity 示例,任何人都可以直接运行,并在此基础上二次开发。你也可以 直接在浏览器里试玩:一个可以操作的小棋盘,实时显示每一次扫描。

仓库 README 的第一句话交代了它的年代:这是 Frank 最后一个完全手写的项目,写于 AI 编程助手进入我们日常工作之前。这篇文章则是事后在 AI 协助下写成的,用来解释这个思路,并与现有做法作个比较。

三消游戏通常怎么找匹配

在介绍我们的做法之前,我们先查阅了公开资料中的三消代码。常见做法大致有四类。

  • 扫描整个棋盘。 逐行、逐列统计同色连续段,长度达到 3 就记为一个匹配。哈佛 CS50 游戏开发课的 Board:calculateMatches()、Catlike Coding 的 Unity 三消教程中的 FindMatches() 都是这样做的。交换是否有效,靠跑一遍全盘扫描来判断,找不到就把交换撤回;连锁消除时,每次补充棋子后再全盘扫描一次。
  • 从交换的棋子向外延伸。 Kodeco(原 Ray Wenderlich)的 Unity 教程从被交换的棋子出发,先左右、再上下发射射线,任一方向凑满三个就消除。这是局部检测,但两个方向各查各的,所以 L 形或 T 形会被当成两条线消除,而不是被识别为一个图形。它的连锁环节又回到了逐格检查整个棋盘。
  • 洪水填充(Flood fill)。 Game Developer 上一篇讲 Unity 三消的文章,递归收集相连的同色棋子,数量达到 3 就消除。任何形状都能处理,但它不会告诉你找到的是什么形状。
  • 事后识别形状。 当游戏确实需要 T、L、十字等形状时,论坛里的常见建议是:先收集匹配到的格子,再把它们的坐标归一化后,和各个朝向的形状模板逐一比对。

另外,棋类引擎中有一种著名的提速技巧:位棋盘(bitboard),把同一颜色的所有格子存成一个位掩码,用移位和按位与找出连续段。它很快,但仍然是全盘运算,形状也仍要事后识别。

这些做法有一个共同点:发现匹配和识别形状是两个独立的步骤,而且其中至少有一步通常要遍历整个棋盘。

思路:三步

FrankMatch3LocalScan 建立在两个观察之上。

  1. 新的匹配一定包含刚移动过的棋子。 如果移动前棋盘上没有匹配,那么新出现的匹配必然经过落点。其他地方根本不用看。
  2. 移动方向告诉你哪里不用看。 棋子的来源格现在放着与它交换的那个棋子,颜色必然不同,不可能属于这个匹配。来源格后面的格子也就一并被切断了。

第一步:叠加所有图形,找出真正有用的格子

把游戏识别的每一种图形,在棋子"向左移动"时可能出现的每一种位置,都画进落点周围同一个 5×4 的窗口里。游戏一共定义了 14 种情形:处于四种位置的三连、四连和五连、L 形、T 形、2×2 方块,以及几种本游戏特有的图形。

把它们叠在一起,只有 8 个格子会被用到。这 8 个格子就是采样点。

第4位第1位第7位第2位第5位落点来源第0位第6位第3位
棋子向左移动到落点。灰底为 8 个采样点,每个对应一位:与落点棋子同色记 1,否则记 0。棋子的来源格永远不参与采样。

第二步:按方向把 8 个格子哈希成一个字节

逐个比较采样点与落点棋子的颜色:相同则该位置 1;不同,或超出棋盘边界,则为 0。8 次比较,得到一个字节。

另外三个方向使用同一布局旋转而来,所以第 5 位永远表示"正前方的格子",第 4 位永远表示"侧向两格",依此类推。方向是哈希函数的输入,查找表不必为四个方向各存一份。

// 棋子向左移动到 (x, y)。其他方向是这一布局的旋转。
byte hash = 0;
if (Same(x,     y - 1)) hash |= 1 << 7;
if (Same(x,     y + 1)) hash |= 1 << 6;
if (Same(x - 1, y    )) hash |= 1 << 5;
if (Same(x,     y - 2)) hash |= 1 << 4;
if (Same(x,     y + 2)) hash |= 1 << 3;
if (Same(x - 2, y    )) hash |= 1 << 2;
if (Same(x - 1, y - 1)) hash |= 1 << 1;
if (Same(x - 1, y + 1)) hash |= 1;

第三步:查表

一个字节只有 256 种取值,所以所有可能的邻域都可以提前列出来。在现有的表里,256 个值中有 172 个对应某种图形,其余对应"无匹配"。每种图形还以未旋转的布局存储了它包含的格子,算法按移动方向把它们旋转回去,得到棋盘上的实际坐标。

图形 必须为 1 的位 示例哈希
H3,正前方的三连 5、2 00100100 = 36
V3C,横跨落点的三连 7、6 11000000 = 192
S2A,2×2 方块 7、5、1 10100010 = 162
L5A,L 形 7、5、4、2 10110100 = 180
T5,T 形 7、6、5、2 11100100 = 228
V5,横跨落点的五连 7、6、4、3 11011000 = 216
T7,最大的图形 7、6、5、4、3、2 11111100 = 252

当一个字节同时包含多个图形时,表返回最大的那个。比如哈希值 252 同时包含 H3、V5 和 T5,表返回能覆盖它们全部的 T7。

连锁消除用的是同一个扫描

匹配被消除后,棋子下落,新棋子生成。每个落位的棋子以"向下"的方向扫描一次。即便在连锁消除时,也从不进行全盘遍历。每次扫描的代价是 8 次比较加一次查表,与棋盘大小无关。

创新之处

我们没有找到以这种方式工作的公开三消实现。这并不能证明不存在,如果你知道,我们很乐意了解。就我们所见,下面这几点的组合是新的。

  • 检测与分类合为一步。 这个字节不只是说"有匹配",而是直接说明是哪种形状。其他做法都是先找出连续段或连通块,再另行分类。
  • 移动方向是算法的一部分。 利用方向,搜索范围缩小了,来源格被排除了,同一张表也通过旋转服务四个方向。
  • 每次移动的工作量是常数。 8 次读取、1 次查表,再加上几个坐标的旋转。棋盘多大都一样,连锁消除也只涉及真正移动过的棋子。
  • 规则就是数据。 这张表只是"字节到形状"的映射。要改变游戏识别哪些形状或它们的优先级,改表即可,不用动扫描代码。

单独来看,各个组成部分并不新鲜。把一个格子的邻居打包成位掩码再查表,在别的领域是常见技巧:2D 游戏的自动铺砖(auto-tiling)就是这样挑选墙壁和地形贴图的,康威生命游戏等元胞自动机也常用邻域查找表来运行。FrankMatch3LocalScan 增加的是三消特有的部分:通过叠加游戏图形来选取采样点,并让哈希值取决于棋子来的方向。

在制作示例时,我们还核对了这张手写的表。对 256 个值中的每一个,它返回的恰好是"所有位都已置 1 的图形中最大的那个"。这意味着这张表不必手写,可以由图形掩码列表自动生成,增加新形状也就安全得多。

局限

  • 窗口是固定的。 扫描在每个方向上最多看到距落点两格。超出这个范围的连续段不会包含在返回的格子里;需要 8 个采样点以外格子的形状无法识别,除非增加第 9 位,表会因此翻倍到 512 项。
  • 每次扫描只返回一个图形。 每次落位只返回经过该格的最大图形。如果游戏希望一次移动产生的两个独立图形分别计分,就需要合并两个被交换棋子各自的扫描结果,示例就是这样做的。
  • 部分图形是《War of Matches》特有的。 "棋子落在一个竖向三连旁边"和 2×2 方块是这个游戏的规则,其他游戏应修改查找表。
  • 它假定来源格颜色不同。 对于交换两个不同颜色的棋子,这一点总是成立。对于下落的棋子,上方的棋子同样移动过,也会被单独扫描,所以竖向连线仍会由最上面的棋子发现。
  • 原始代码不是线程安全的。 它在哈希计算时把棋盘尺寸存放在静态字段里。

性能:暂未测量

我们没有发布基准测试数据。公平的比较需要其他实现在相同棋盘、相同规则(包括形状识别)下运行,而我们没有找到可以在同等条件下并排运行的开源代码。拿我们自己临时重写的版本作对比,测出来的多半只是我们写得好不好。

从理论上看,优势是明确的:全盘扫描在每一轮连锁中都要付出与棋盘面积成正比的代价,而局部扫描只需要对每个移动过的棋子做 8 次比较。在实际中这是否重要,取决于棋盘大小、目标设备,以及游戏每帧还要做多少其他事。如果你做了测量,欢迎告诉我们结果。

试一试,再往前走一步

最快的体验方式是 在线演示。它是示例的 Blazor WebAssembly 版本,使用同一套代码,完全在浏览器中运行。

仓库包含三部分:

  • Algorithms/ 是游戏中的原始代码:四个方向的哈希函数、256 项查找表,以及各图形的坐标。
  • UnitySample/ 是一个最小化的 Unity 6 项目。打开它,在空场景中按 Play,点击两个相邻的棋子即可交换。侧边面板实时显示每一次扫描:落点、方向、二进制形式的字节,以及它对应的图形。最近一次扫描的 8 个采样点会标在棋盘上。棋盘逻辑是纯 C#,不依赖 Unity;EditMode 测试会检查查找表,以及四个方向上的哈希布局。
  • BlazorSample/ 就是在线演示。它原样编译 Algorithms/ 中的文件,与 Unity 示例共用棋盘逻辑,不需要任何服务器:本地用 dotnet run 运行,或发布到任意静态托管。

一些我们觉得值得尝试的方向:

  • 由图形列表自动生成查找表,而不是手写;
  • 用一个 256 元素的普通数组代替字典;
  • 把同样的思路用于提示和死局检测:假设有棋子移动到某格,计算该格的哈希;
  • 为图形更大的游戏尝试 9 位或 10 位的布局。

代码以 MIT 许可发布。欢迎 fork、修改,并用在你自己的游戏里。

参考资料

想聊聊类似的项目?

30 分钟通话。不收费,除非你主动提,否则不会再联系你。

预约通话