具有正则表达式的Match 3算法

虽然它肯定是市场上最著名的因果游戏类型之一，但我之前从未做过3类游戏。 当我决定选择这种类型时，我偶然发现了这种类型： 检测匹配项和潜在匹配项。

这些不是难题，可以通过遍历每个单元格并检查相邻单元格来解决。 但是， 那从来不是我的风格 ，我想尝试一些不同的东西。

• Nomad游戏引擎：第3部分-大图
• 统一计算着色器：表现不佳
• Google For India的重要公告
• 仅iPad，gamedev –＃13 –如何仅使用iPad构建的游戏赚钱
• 虚拟团队

在我看来，问题是模式匹配类型的，因此我想到了正则表达式 。 一旦设置了表达式，匹配操作应该非常简单且非常快速。

首先，我必须将我的宝石网格显示为字符串 。 由于我选择对网格使用一维数组 ，因此仅需要map+join或reduce操作。 我发现lodash map+join更清晰和非常简单。

 _.map(grid, 'type').join('') 

在这里，我假设 type 是一个表示gem type 的变量，并且只使用一个字符（数字或字符）。 如果每种类型使用多个字符，则每种类型的字符数应相等。

这是最简单的情况。 对于每种T型宝石，我们构建了一个表达式以匹配 具有至少3个字符的 任何连续 T 系列 ：

 /(TTT)/g 

有两个问题：

首先 ，在某些情况下， T中的一个 在另一行上。 例如：

  |  |  T |  T ||  T |  |  | 

在这种情况下，字符串表示法是…TTT…但这不是我们想要的。 我们只应进行距行尾至少2个单元格位置的比赛：

 number_of_columns - match_position % number_of_columns > 2 

其次 ，由于RegEx会消耗所有匹配的字符，因此对于TTTTT 仅会捕获 前三个字符，而不会捕获 其他 三个字符。 有两种解决方案：

• 为每个特定情况/(TTTTT|TTTT|TTT)/g制作一个RegEx。 考虑到其他情况也需要相同的过程，这比有用的问题要麻烦得多 。
• 使用 RegEx.exec 捕获 。

 令模式= /（TTT）/ g， 
 结果= []， 
 比赛; 
  while（（match = pattern.exec（gridString））！= null）{ 
  results.push（匹配） 
  } 

这有点复杂，因为字符不会在同一行，因此它们在字符串中的位置分散了 。

请注意，同一列和两个连续行上的两个字符之间的距离是number_of_columns - 1索引（请参见下图） 。

  |  |  T |   | 
  |   |  T |  | 

每对字符的表达式为

 /T.{number_of_columns - 1}T/g 

因此， 列匹配的表达式为 ：

 /(T.{number_of_columns - 1}T.{number_of_columns - 1}T)/g 

虽然这种情况不会遇到连续检测匹配项的第一个问题，但确实会遇到第二个问题 ，因此应以相同的方式处理。

表达式（如图中的顺序）是：

 /(TT.)/ 
 /(TT)/ 
 /(.TT)/ 

但是，该模式还必须考虑可以交换以进行匹配的单元格，它们位于non-T单元格的上方或下方，如下图所示：

从下排T细胞到匹配细胞的距离等于其与non-T细胞的距离，减去non-T T细胞后non-T细胞数，即：

 列数-1-T_after_non_T_cell数 

我们的表达式是：

 /(TT..{number_of_columns - 1}T)/ 
 /(TT{number_of_columns - 2}T)/ 
 /(.TT.{number_of_columns - 3}T)/ 

这也是遭受连续检测匹配项的第一个问题 ，应该以相同的方式处理 。

我们也可以为上排T单元格的情况构建表达式，但是， 结果将返回该上排单元格的索引，而不是匹配项的第一个索引。 这很不好，因为这会使处理第一个问题变得更加困难。

相反，我们可以翻转网格 （通过反转字符串），然后使用相同的表达式 。 为了找到真实的匹配索引，必须将接收到的索引转换回原始字符串中的索引，并减去2 ，因为网格被翻转了，这也使每个匹配中的像元顺序颠倒了。

为了实现目的，我们可以合并表达式，因为我们只需要知道当前网格是否具有潜在的匹配。

这里我不讨论提示功能。 实施该功能的最佳方法是使用RegEx的后向功能，JavaScript目前尚不支持该功能。 不过，诸如XRegExp之类的库提供了此功能。

如果您到目前为止已经读过，则不需要太多解释，上图所示情况的表达式为：

 /(T.{number_of_columns - 1}T.{number_of_columns}T)/ 
 /(T.{number_of_columns}T.{number_of_columns - 2}T)/ 
 /(.T.{number_of_columns - 2}T.{number_of_columns - 1}T)/ 

这会在匹配右侧找到带有可交换单元格的潜在匹配。 与上一部分类似，对于可交换T在左列的情况，我们只需要翻转网格 ，使用相同的表达式 ，然后将索引转换回原始字符串，并减去2 * number_of_columns 。

这也遇到了第一个问题 ，即检测行上的匹配项，因此应以相同的方式处理，尽管在这种情况下，到行尾的最小距离为1（可交换单元格的右边留有一列）。

 number_of_columns - match_position % number_of_columns > 1