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

Question

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

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

例如，专栏、宝石、俄罗斯方块等游戏。

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

这类游戏常用哪些结构？

Answer 1

它始终依赖于域。但也有两种情况需要您进行此类搜索。一种情况是在移动之后（玩家对游戏场地进行的更改），另一种情况是如果/当整个棋盘发生变化时。

在俄罗斯方块中，您无需在掉落一块后扫描整个棋盘。您只需要搜索该作品所接触的行。

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

正如 Adrian 所说，一个简单的二维数组就足够了。但是，通常，您可以在该数组周围添加像素“边框”，以简化搜索模式方面。如果没有边框，您必须if在边缘正方形上声明“好吧，如果您在第一行，请不要搜索（并离开数组）”。周围有边框，您可以安全地搜索所有内容：保存自己if的语句，保存自己的分支，保存自己的管道问题，更快地搜索。

对 Jon：这些事情在高性能设置中确实很重要，即使在现代机器上，如果你正在制作一个搜索算法来玩/解决游戏。如果你是，你希望你的底层模拟尽可能快地运行，以便在最少的周期内搜索尽可能深的深度。

Answer 2

关于算法：这当然取决于游戏。例如，对于俄罗斯方块，您只需要扫描具有相同颜色的每一行。在这种情况下，我什至想不出与蛮力方法不一样的东西。但是对于大多数休闲游戏来说，蛮力应该是完全没问题的。与图形和声音处理相比，模式识别应该可以忽略不计。

关于结构：一个简单的 2D 阵列应该足以代表板。

Answer 3

鉴于这些天的平均计算机速度，如果它在用户玩游戏时是实时的，那可能并不重要（编辑：仅适用于非常小的游戏板）。当然，这取决于游戏逻辑的复杂性，以及代码在目标机器上运行的速度（即，这是一个 JavaScript 网页游戏，还是一个用 C++ 编写的 Windows 应用程序）。

如果这是为了模拟游戏策略，那么使用更有效的算法。

更有效的策略可能涉及跟踪游戏板的增量更改，而不是每次都重新扫描整个板。