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

Question

有一款名为 Unblock Me 的 iPhone 流行游戏。目标是清除红色方块前面的所有障碍物，以便有一条通向出口的清晰路径：

为该游戏生成随机棋盘的明智方法是什么？我在想一些事情：

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

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

Answer 1

我玩了很多游戏，所以这里有一些想法：

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