在游戏 Unblock Me 中生成随机棋盘的算法

Question

iPhone 上有一款很受欢迎的游戏，叫做 Unblock Me。目标是移除红色方 block 前面的所有障碍物，以畅通导出:

为该游戏生成随机棋盘的明智方法是什么？我正在考虑这些方面的事情:

1. 将红色方 block 放在导出处。
2. 在红色方 block 周围随机放置 M 个方 block 。
3. 进行 N 次随机移动，直到红色方 block 被阻挡。
4. 每个级别增加 M 或 N。

请注意，移动设备的 CPU 功率和 RAM 有限，因此效率很重要。

Answer 1

我经常玩这个游戏，所以这里有一些想法:

• 简单地进行 N 次随机移动并不一定会使关卡变得更难。您可能最终处于可以在 n 步中解决的状态，其中 n 明显小于 N。
• 关卡可以在台式机上生成，然后简单地包含在手机游戏中。这允许进行更详尽的搜索(很可能是基于树和回溯)以确保该级别至少需要一定数量的移动才能解决。关卡应该越难，当然需要的 Action 就越多。
• 您可以在算法中添加更多知识:如果您想让红色棋子通过，则长度为 3 的垂直棋子必须位于底部位置。这限制了解决关卡的方式。这会使关卡更加困难，尤其是当其中有多个垂直部分时。