Jos*_*el. 5 puzzle algorithm artificial-intelligence
我想知道,这是最常用的算法,用于寻找符合细胞网格的益智游戏中的模式.
我知道这取决于很多因素,比如你想要检测的模式类型,或游戏规则......但我想知道哪种算法在这类问题中最常用...
例如,像柱子,珠宝,甚至俄罗斯方块的游戏.
我还想知道是否通过"强力"检测模式(比如,扫描所有网格试图找到相同颜色的三个相邻单元格)是非常差的,在非常小的网格中使用特定算法,例如4 X 4(而且,我知道这取决于游戏和规则......)
在这种游戏中常用哪种结构？
它始终依赖于域.但是还有两种情况你会进行这类搜索.一个移动(玩家对游戏区域的改变)是另一种情况,另一种情况是整个棋盘改变后的情况.
在俄罗斯方块中,在丢弃一块之后你不需要扫描整个板.你只需要搜索片段正在触摸的行.
在像Bejeweled这样的第3场比赛中,你一次交换两个相邻的棋子,你首先要在每个方格周围的每个方向上进行本地化搜索,以便查看是否有任何棋子被触发.然后,如果他们有,游戏将把一些新的,随机的碎片扔到板上.现在,您可以在每个已更改的方块周围运行相同的本地化搜索,但这可能涉及大量if语句,并且实际上可能比从左上角到右下角扫描整个板更慢.这取决于您的实现,并需要分析.
正如阿德里安所说,一个简单的二维阵列就足够了.但是,通常,您可以在此数组周围添加像素的"边框",以简化模式搜索方面.没有边框,你必须if在边缘方块上有声明,"好吧,如果你在顶行,不要向上搜索(并离开阵列)".通过它周围的边框,您可以安全地搜索所有内容:保存自己的if语句,节省自己的分支,节省自己的管道问题,更快地搜索.
致Jon:如果您正在制作搜索算法来玩/解决游戏,那么这些事情在高性能设置中确实很重要,即使在现代机器上也是如此.如果您愿意,您希望您的基础模拟尽可能快地运行,以便在最少的周期内尽可能深地搜索.