algorithm - 流式免费游戏随机关卡创建用什么？

Question

我需要一些建议。我正在开发一款类似于 Flow Free 的游戏，其中游戏板由网格和彩色点组成，用户必须将相同颜色的点连接在一起而不重叠其他线，并用完板上的所有可用空间。

我的问题是关于关卡创建的。我希望让关卡随机生成(并且至少应该能够自行解决，以便它可以给玩家提示)并且我对使用什么算法感到困惑。有什么建议吗？

注:图片展示了Flow Free的目标，与我正在开发的目标相同。

感谢您的帮助。 :)

Answer 1

考虑使用一对更简单、更易于管理的算法来解决您的问题:一种算法可以可靠地创建简单的、预先解决的看板，另一种算法可以重新安排流程以使简单的看板变得更复杂。

如果您在 nx 上使用 n 流，那么第一部分构建一个简单的预求解板是微不足道的(如果您希望如此) n 网格:

• 对于每个流...
  • 将点头放在第一个空栏的顶部。
  • 将尾点放在该列的底部。

或者，您可以提供自己手工制作的入门板以传递给第二部分。这个阶段的唯一目标是构建一个有效的电路板，即使它只是微不足道的或预先确定的，所以保持简单是值得的。

第二部分，重新​​排列流，涉及遍历每个流，看看哪个流可以与其相邻流一起增长和收缩:

• 对于一些迭代...
  • 选择一个随机流f。
  • 如果 f 处于最小长度(例如 3 个正方形长)，则跳至下一次迭代，因为我们现在无法缩小 f。
  • 如果 f 的头点紧挨着另一个流 g 的点(如果有多个 g 可供选择，选择随机一个)...
    • 将 f 的头部点沿其流向移动一格(即，将其向尾部移动一格)。 f 现在短了一个方格，并且有一个空方格。 (现在这个谜题还没有解开。)
    • 将 g 中的相邻点移动到 f 腾出的空方格中。现在有一个空方 block ，g 的点从那里移动。
    • 用来自 g 的流量填充空白处。现在 g 比本次迭代开始时长一个方格。 (谜题也重新解决了。)
  • 对 f 的尾点重复上一步。

目前的方法是有限的(点总是相邻的)但很容易扩展:

• 添加一个步骤来循环遍历流 f 的主体，寻找与其他流交换空间的更棘手的方法...
• 添加防止点移动到旧位置的步骤...
• 添加您想到的任何其他想法。

这里的整体解决方案可能不如您想要的理想解决方案，但现在您有两个简单的算法，您可以进一步充实它们以发挥一个大型、包罗万象的算法的作用。最后，我认为这种方法易于管理，不神秘，易于调整，而且，如果不出意外的话，这是一个很好的起点。

---

更新:我根据上述步骤编写了概念验证代码。从下面的第一个 5x5 网格开始，该过程产生了随后的 5 个不同的板。有些很有趣，有些则不然，但它们始终适用于一种已知的解决方案。

起点

5 个随机结果(对于未对齐的屏幕截图感到抱歉)

还有一个随机的 8x8 尺寸。起点是与上述相同的简单列方法。