algorithm - 连接线-算法

Question

我正在使用 C#，但将来我可能需要在其他语言上使用它。

很多游戏都有这样的谜题。有一组电线(有两种类型的电线:直的和弯的。)，有一个地方是信号进来的地方，还有一个地方是信号必须离开的地方。但是电线的布置不允许这种情况发生。您必须转动一些电线才能为信号创建路径。

是的，我正试图再次找到美洲大陆，以免在未来多次尝试找到它。

在未来的某个地方，我也会尝试同样的事情，但这次使用将信号分成 2 或 3 个信号的电线。

问题是我想不出一个我能想象到的算法如何把它变成代码。想了半天，想不出什么好办法。

那么，你能帮帮我吗？我将能够将算法理解为“程序必须做什么”，但我基本上需要帮助才能将算法理解为“如何编写代码”。

谢谢!

Answer 1

看看一些maze generation algorithms -- 它们做的事情与您正在寻找的相同，因此您需要创建网格。从我链接的那些中选择一个简单的“细胞雕刻机”；随机旋转所有的线片，等等!

对您问题的评论指出，将算法转化为代码需要一点一点地分解它——这就是我们要做的:

您将从潜在电线位置的网格开始(可能是 2D，但 3D 游戏会很棒)。

要生成一个可解决的关卡，您可以做几件事——生成一个关卡，看看它是否可以解决(不好)，或者生成一个已解决的关卡，然后“解开”它(更好)。正如我在上面提到的，生成一个已解决的关卡涉及与迷宫生成非常相似的算法——一个已解决的关卡将有许多可穿越的“路径”，就像迷宫一样。解开关卡只会遍历所有线段，并稍微旋转它们。

但是迷宫生成呢？我链接到的资源包含一些非常适合您使用的算法——一个简单的随机 DFS 应该足以满足您的需求。

您会注意到，我涵盖了涉及分支线的一般情况——实际上，排除分支意味着您必须进行更多编码，以智能地“修剪”分支——也就是说，当您的一条真实路径到达时回溯卡住，比如在角落里，因为随机移动可能是制作有趣关卡所必需的。

您还应该注意，如果我理解正确的话，此类游戏的解决方案需要使用所有给定的电线(我知道一些这样的游戏)。否则，考虑到上述生成策略，游戏可能会更简单。