用于生成 Unblock Me 游戏随机棋盘的算法

Question

有一个名为Unblock Me的iPhone游戏非常受欢迎。其目标是消除红色方块前面的所有障碍物，使其通向出口：

要生成一个随机的游戏板，有什么明智的方法吗？我正在考虑以下做法：

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

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

- TheOne

---

您可以在游戏之外生成随机棋盘，并将其作为游戏中的关卡存储。无需在游戏内生成它们，这样可以保持关卡的一致性。 - nhahtdh

@nhahtdh，没错，但我想为用户创建一个真正独特的体验，每个关卡都完全不同。 - TheOne

@Ramin：只有在技术可行的情况下才应该这样做。如果您还想保证一定难度水平，那么此问题的搜索空间可能无法做到这一点。 - Simeon Visser

你所做的将会使得不同用户之间，甚至是不同尝试之间的难度级别有所不同。 - nhahtdh

Answer 1

我玩过那个游戏，这里有一些想法：

• 仅仅进行N次随机移动并不一定会使关卡更难。你可能会陷入一个可以在n步内解决的状态，其中n明显小于N。
• 关卡可能是在台式机上生成的，然后直接包含在移动游戏中。这样可以进行更详尽的搜索（很可能是基于树结构和回溯），以确保关卡至少需要一定数量的移动才能解决。当然，难度越大，所需的移动次数就应该越多。
• 你可以将更多的知识融入算法中：如果你想让红色方块通过，长度为三的竖向方块必须位于底部位置。这限制了关卡的解决方式。这可以使关卡更加困难，特别是当其中有多个竖向方块时。

- Simeon Visser