在益智游戏中寻找模式
我想知道哪些是最常用的算法，用于在益智游戏中寻找符合细胞网格的模式。
我知道这取决于很多因素，例如您想要检测的模式类型，或者游戏规则...但我想知道在此类问题中哪些是最常用的算法...
例如，诸如专栏、宝石迷阵、甚至俄罗斯方块之类的游戏。
我还想知道通过“强力”检测模式（例如，扫描所有网格试图找到相同颜色的三个相邻单元）是否比在非常小的网格（例如 4 X 4）中使用特定算法更糟糕（再说一次，我知道这取决于游戏的类型和规则......）
此类游戏中常用哪些结构？
I was wondering, which are the most commonly used algorithms applied to finding patterns in puzzle games conformed by grids of cells.
I know that depends of many factors, like the kind of patterns You want to detect, or the rules of the game...but I wanted to know which are the most commonly used algorithms in that kind of problems...
For example, games like columns, bejeweled, even tetris.
I also want to know if detecting patterns by "brute force" ( like , scanning all the grid trying to find three adyacent cells of the same color ) is significantly worst that using particular algorithms in very small grids, like 4 X 4 for example ( and again, I know that depends of the kind of game and rules ...)
Which structures are commonly used in this kind of games ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
它始终依赖于域。但也有两种情况需要您进行此类搜索。一种情况是在移动之后（玩家对游戏区域进行更改），另一种情况是如果/当整个棋盘发生变化时。
在俄罗斯方块中，您不需要在棋子掉落后扫描整个棋盘。您只需搜索该作品所接触的行即可。
在像《宝石迷阵》这样的三消游戏中，您一次要交换两个相邻的棋子，您首先要在每个发生变化的方格周围的每个方向上运行本地化搜索，以查看是否触发了任何棋子。然后，如果有的话，游戏会将一些新的随机棋子倾倒到棋盘上。现在，您可以在每个已更改的方块周围运行相同的本地化搜索，但这可能涉及大量
if语句，并且实际上可能比从左上到右下扫描整个板要慢。这取决于您的实施并且需要分析。正如阿德里安所说，一个简单的二维数组就足够了。不过，通常您可以在该数组周围添加像素“边框”，以简化搜索模式方面。如果没有边框，您必须在边缘方块上使用
if语句，表示“好吧，如果您在顶行，则不要向上搜索（并离开数组）” 。有了边框，您就可以安全地搜索所有内容：节省自己的if语句、节省自己的分支、节省自己的管道问题、更快地搜索。乔恩：如果您正在制定搜索算法来玩/解决游戏，那么即使在现代机器上，这些事情在高性能设置中确实很重要。如果是的话，您希望底层模拟尽可能快地运行，以便在最少的周期内进行尽可能深入的搜索。
It's always domain-dependent. But there's also two situations where you'd do these kinds of searches. Ones situation is after a move (a change to the game field made by the player), and the other would be if/when the whole board has changed.
In Tetris, you wouldn't need to scan the whole board after a piece is dropped. You'd just have to search the rows the piece is touching.
In a match-3 games like Bejeweled, where you're swapping two adjacent pieces at a time, you'd first run a localized search in each direction around each square that changed, to see if any pieces have triggered. Then, if they have, the game will dump some new, random pieces onto the board. Now, you could run the same localized search around each square that's changed, but that might involve a lot of
ifstatements and might actually be slower to just scanning the whole board from top left to bottom right. It depends on your implementation and would require profiling.As Adrian says, a simple 2D array suffices. Often, though, you may add a "border" of pixels around this array, to simplify the searching-for-patterns aspect. Without a border, you'd have to have
ifstatements along the edge squares that says "well, if you're in the top row, don't search up (and walk off the array)". With a border around it, you can safely just search through everything: saving yourselfifstatements, saving yourself branching, saving yourself pipeline issues, searching faster.To Jon: these kinds of things really do matter in high-performance settings, even on modern machines, if you're making a search algorithm to play/solve the game. If you are, you want your underlying simulation to run as quickly as possible in order to search as deep as possible in the fewest cycles.
关于算法：这当然取决于游戏。例如，对于俄罗斯方块，您只需扫描具有相同颜色的每一行。在这种情况下，我什至想不出什么不等于暴力方法的方法。但对于大多数休闲游戏来说，暴力破解应该完全没问题。与图形和声音处理相比，模式识别应该可以忽略不计。
关于结构：一个简单的二维数组应该足以表示棋盘。
Regarding algorithms: It certainly depends on the game. For example for tetris, you'd only have to scan each row if it has the same color. I can't even think of something that would not equal the brute force approach in this case. But for most casual games brute force should be perfectly fine. Pattern recognition should be negligible in comparison to graphics and sound processing.
Regarding structures: A simple 2D-Array should suffice for representing the board.
考虑到当今计算机的平均速度，如果用户玩游戏时是实时的，那可能并不重要（编辑：仅适用于非常小的游戏板）。当然，这取决于游戏逻辑的复杂性，还取决于代码在目标机器上运行的速度（即，这是一个 JavaScript 网页游戏，还是一个用 C++ 编写的 Windows 应用程序）。
如果这是为了模拟游戏策略之类的事情，那么请使用更有效的算法。
更有效的策略可能包括跟踪游戏板的增量变化，而不是每次都重新扫描整个板。
Given the average computer speed these days, if it's real-time as the user is playing the game, it probably won't matter (EDIT: for very small game boards only). Certainly, it would depend on the complexity of the game logic, but also how fast the code is going to run on the target machine (i.e., is this a JavaScript web page game, or a Windows app written in C++).
If this is for something like simulating gameplay strategies, then use an algorithm that's more efficient.
A more efficient strategy could involve keeping track of incremental changes to the game board, instead of re-scanning the whole board every time.