algorithm - 在益智游戏中寻找模式

Question

我想知道，哪些是最常用的算法，用于在由单元格组成的益智游戏中寻找模式。

我知道这取决于很多因素，比如你想要检测的模式类型，或者游戏规则......但我想知道在这类问题中哪些是最常用的算法......

例如，专栏、 gem 迷阵、甚至俄罗斯方 block 等游戏。

我还想知道通过“蛮力”检测模式(例如，扫描所有网格试图找到三个相同颜色的相邻细胞)是否比在非常小的网格(例如 4 X 4)中使用特定算法要差得多例如(再一次，我知道这取决于游戏的类型和规则......)

这类游戏常用的结构有哪些？

Answer 1

它始终依赖于域。但也有两种情况需要您进行此类搜索。一种情况是移动后(玩家对游戏区域的改变)，另一种情况是当整个棋盘发生变化时。

在俄罗斯方 block 中，您不需要在放下一个棋子后扫描整个棋盘。您只需搜索作品所涉及的行即可。

在像 gem 迷阵这样的三消游戏中，您一次要交换两个相邻的棋子，您首先会在每个发生变化的方 block 周围的每个方向上运行局部搜索，以查看是否有任何棋子被触发。然后，如果有的话，游戏会把一些新的、随机的棋子扔到棋盘上。现在，您可以围绕每个已更改的方 block 运行相同的本地化搜索，但这可能涉及大量 if 语句，并且实际上可能比仅从左上角到右下角扫描整个棋盘更慢。这取决于您的实现，并且需要分析。

正如 Adrian 所说，一个简单的二维数组就足够了。不过，您通常可以在该数组周围添加一个像素“边界”，以简化搜索模式方面的工作。如果没有边框，您必须在边缘方 block 上使用 if 语句来表示“好吧，如果您在第一行，请不要向上搜索(并离开数组)” .有了边框，您就可以安全地搜索所有内容:节省您自己的 if 语句、节省您自己的分支、节省您自己的管道问题、更快地搜索。

致乔恩:如果您正在制定搜索算法来玩/解决游戏，那么这些事情在高性能设置中确实很重要，即使在现代机器上也是如此。如果是，您希望底层模拟尽快运行，以便在最少的周期内尽可能深入地搜索。