javascript - 解谜算法将一块棋子移入出口点

我正在寻找一些关于什么是我可以使用 Javascript 解决附加图像上的难题的好算法的建议，最好是如果算法被记录并且可以包含 JS 示例。

白色棋子可以一次移动一个，4 个方向，进入灰色点（如果它们适合）当较大的白色棋子到达红色出口点时，游戏结束。

这只是为了好玩。

我正在用 Javascript 制作这个，我将使用 p5.js 来显示它。我不是在寻找实际的代码解决方案，这是一个有趣的个人练习。

我过去尝试过，但没有成功，我记得它花了很多时间计算出口路径，但几分钟后就找不到了。

显示的拼图是一个非常基本的版本，可以理解这个想法，但是每次棋盘都会变得越来越复杂，例如，在更大的棋盘上会有很多不同尺寸的白色棋子。

我知道我可以尝试广度优先搜索算法，但是我不知道如果板变大它是否仍然适合，例如 5x7 而不是 3x3，我不知道如何估计它有多少排列可以带计算机找到最短的退出路径。

有了 BFS，我明白，从董事会的给定状态，我需要探索所有可能的后果，每一个都是不同的分支，这可能导致数百万个组合，其中每个组合都将探索如果给定的情况会发生什么搬到这里而不是那里。

感谢您的时间和耐心:)

标签： javascriptbreadth-first-searchgame-developmentpath-finding

根据http://groups.csail.mit.edu/mac/users/bob/sliding-blocks.pdf滑动谜题通常可以在 NP 完全问题的世界中占据一席之地，这些问题通常是粗糙且计算成本高的（如果可以解决的话） . 这就解释了为什么你甚至很难尝试计算路径。

通常没有针对此类问题的通用方法，因为每个问题都需要特定的定制解决方案。

在您的具体情况下，尽管我建议尝试一种简单的寻路方法，首先您尝试将棋子尽可能靠近，然后，一个动作出来，您尝试将棋子从潜在路径“推开”。

我希望这可以为您指明正确的方向:-)