在益智游戏中寻找模式

Question

我想知道，在由网格单元组成的益智游戏中寻找模式时最常用的算法是什么？

我知道这取决于许多因素，比如你想要检测的模式类型，或者我想知道的game...but规则，在这类问题中最常用的算法是什么……

例如，像柱子，宝石，甚至俄罗斯方块这样的游戏。

我还想知道，在非常小的网格中使用特定的算法来检测模式(例如，扫描所有网格试图找到三个相同颜色的不稳定单元)是否比在非常小的网格中使用特定算法(例如4X4)要糟糕得多(而且，我知道这取决于游戏和规则的类型...)

这类游戏中常用的结构是什么？

Answer 1

它总是依赖于域。但在两种情况下，你也会进行这样的搜索。一种情况是在移动之后(玩家对游戏区域进行了更改)，另一种情况是如果/当整个棋盘发生变化时。

在俄罗斯方块中，你不需要在掉下一块棋子后扫描整个棋盘。你只需要搜索这块碎片接触到的行。

在比赛3游戏中，你一次交换两个相邻的棋子，你首先在每个改变的方块周围的每个方向上运行一个本地化搜索，看看是否有任何棋子被触发。然后，如果他们有，游戏将倾倒一些新的，随机的棋子到棋盘上。现在，您可以在更改的每个方块周围运行相同的本地化搜索，但这可能涉及许多if语句，实际上可能会比从左上角到右下角扫描整个棋盘要慢。这取决于您的实现，并且需要分析。

正如禤浩焯所说，一个简单的2D数组就足够了。不过，您通常可以在此数组周围添加像素的“边界”，以简化模式搜索方面。如果没有边框，您必须在边框中使用if语句，声明“如果您在顶行，不要向上搜索(并离开数组)”。有了它周围的边界，您就可以安全地搜索所有内容:保存自己的if语句，保存自己的分支，保存自己的管道问题，更快地搜索。

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

Answer 2

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

关于结构:一个简单的2D数组应该足以表示电路板。

Answer 3

考虑到如今计算机的平均速度，如果用户玩游戏时是实时的，这可能没什么关系(编辑:仅适用于非常小的游戏板)。当然，这将取决于游戏逻辑的复杂性，但也取决于代码在目标机器上运行的速度(例如，这是一个JavaScript网页游戏，还是用C++编写的Windows应用程序)。

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

更有效的策略可以包括跟踪游戏棋盘的增量更改，而不是每次都重新扫描整个棋盘。