在解谜游戏中寻找模式

Question

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

我知道这取决于许多因素，例如您想要检测的模式类型或游戏规则...但我想知道在这种问题中最常用的算法是什么...

例如，像columns、bejeweled、甚至tetris这样的游戏。

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

这种游戏通常使用哪些结构？

- José Joel.

Answer 1

这通常取决于具体的领域。但也有两种情况需要进行这种搜索。一种情况是移动后（玩家对游戏区域进行的更改），另一种情况是整个游戏区域发生变化时。

例如，在俄罗斯方块中，放下一个方块后，无需扫描整个游戏区域。只需搜索与该方块接触的行。

而在《宝石迷阵》等连三消类游戏中，你每次交换相邻两个方块时，需要在每个发生变化的方块周围的每个方向上运行本地化搜索，以查看是否有任何方块被触发。如果有，游戏将把一些新的随机方块倒入游戏区域。现在，你可以在每个已更改的方块周围运行相同的本地化搜索，但这可能涉及很多 if 语句，并且实际上可能比从左上角到右下角扫描整个游戏区域更慢。这取决于你的实现方式，并需要进行性能分析。

就像 Adrian 所说，一个简单的二维数组就足够了。不过，通常你可能会在这个数组周围添加一圈像素边框，以简化寻找模式的过程。如果没有边框，你必须在边缘方块上使用 if 语句，例如“嗯，如果你在最上面一行，请勿向上搜索（并走出数组）”。有了边框，你可以安全地搜索所有内容：省去了 if 语句、节省了分支、管道问题和搜索时间。

对于 Jon：即使在现代计算机上，在高性能环境下制作搜索算法以玩游戏/解决问题这样的场景中，这些事情也真的很重要。如果是这样的话，你希望底层模拟尽可能快地运行，以便在最少的周期内深度搜索。

- Shaggy Frog

Answer 2

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

关于结构：一个简单的2D数组就足以表示游戏板。

- Adrian Grigore

Answer 3

考虑到现今平均计算机的速度，如果是实时游戏的话，在玩家游戏时它可能不会有太大的影响（编辑：仅适用于非常小的游戏板）。当然，这取决于游戏逻辑的复杂性，还要看代码在目标机器上运行的速度如何（例如，这是使用 JavaScript 网页游戏，还是使用 C++ 编写的 Windows 应用程序）。

如果是用来模拟游戏策略之类的东西，那么可以使用更高效的算法。

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

- Jon Seigel