返回资讯中心
外部精选
软件工程
#开发者实时流

开发者总结解谜游戏中检测图环路的各种错误算法

来源标题:Possibly all the ways to get loop-finding in graphs wrong

一位解谜游戏开发者回顾多年开发经历,称自己可能已集齐了在图中查找环路的全部错误做法。这些游戏(如 Net、Slant、Bridges)需检测环路以判断答案是否正确,并找出构成环的边向玩家指出错误。他逐一弃用不理想的算法,现将这些失败案例整理成文作为反面教材。

Hacker News 最新josephcsible2026/11/20 · 今天30 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

在我的谜题合集里,有许多游戏要求你用边把点连接起来,构成一个图,而谜题规则规定你必须避免在图中形成任何环。例子包括 Net、Slant,以及 Bridges 的某些配置(尽管不是默认配置)。Loopy 和 Pearl 也关心图中是否存在环,不过这两个更微妙:你的目标是制造一个环,只有错误的环才必须被拒绝。

因此,这些谜题程序需要能够检查图中是否存在环,以便判断谜题解答是否正确。如果存在环,它们还必须找出构成该环的边,从而向玩家指出他们的解答为何未被接受。多年来,在我开发这些谜题的过程中,我尝试了数量惊人的算法来完成这项工作。每一种都因某种原因不尽如人意,我便把它丢弃,转向下一种。

到现在,我可能已经收集齐了所有把这件事做错的方法!所以我想把所有错误都写下来,作为一份案例研究,既展示你能用哪些方式错误地解决这个特定问题,也展示如果你没能在文献中找到现有解法,会浪费多少精力。当生成一个这样的谜题时,生成器会运行一个自动求解算法,以检查其解是否唯一。因此,求解算法需要检查自己是否意外地在图中造出了一个环。

或者更准确地说,如果求解器能判断自己是否即将造出一个环,那就更好:当它考虑向图中添加某条边时,它想知道这条边是否会形成一个环。如果是,它就决定根本不添加这条边,这比先添加、发现搞砸了、再不得不撤销要高效得多。

我的自动求解器通常通过使用不相交集合森林数据结构的实现来处理这件事,它也被称为“并查集”数据结构,或直接叫“不相交集合数据结构”¹。我谨认为,严格来说,“不相交集合森林”指的是解决增量等价关系追踪问题的一种特定技术,而其他不带“森林”的名字指的是问题本身,并不承诺采用某种特定解法——就像快速傅里叶变换是实现称为离散傅里叶变换的抽象数学算子的一种特定算法。在两种情况下,这种区分常被忽略,因为那个著名算法解决问题的方式太好,以至于没人真正想用别的。¹我的代码中通篇称之为“dsf”,这样短得多,我在这里也沿用这个叫法。

对于以前没接触过 dsf 的人,它是一种非常快的数据结构,用于追踪集合中元素之间的等价关系,只要等价关系是增量添加的:你一开始认为集合中每个元素都不同,当两个元素之前不等价时,你可以更新数据结构使它们等价,但绝不会有元素从原本等价变为不等价。因此,集合的元素被划分为等价类,一次更新可以合并两个类,但一个类永远不会分裂。你可以通过告诉 dsf 某对元素 a 和 b 现在被视为相同,来高效地添加一个新的等价关系;你也可以随时查询它,询问两个元素当前是否被视为等价。它会自动追踪传递性,例如,如果你已经告诉它 a = b 且 c = d,然后你告诉它 b = c,它会立即知道 a = d。它是我整个谜题合集绝对基石:没有这个工具模块,其中大部分都会瘫成一堆。

因此,当 Slant 的自动求解器——例如——试图解一个谜题时,它会在网格的顶点上建立一个 dsf。每次添加一条边,它就告诉 dsf 统一该边两端的两个顶点。于是 dsf 的等价类精确追踪图的连通分量:如果两个顶点之间存在路径可达,dsf 就会报告它们“等价”,如果不可达,就不会。

这意味着,在求解器向谜题解中添加一条边之前,它可以查询 dsf,看看两个端点是否被视为等价。如果 dsf 说是,那么这两个顶点之间已经有一条路径,而这条路径不可能涉及我们即将添加的边(因为我们还没添加它)。因此,如果我们确实添加了那条边,两个顶点之间就会存在两条完全独立的路径——也就是一个环。

自动求解器通常只在确定某条边正确时才把它加入图,这意味着它们永远不需要改变主意再把它移除。所以它们一路进行时,只需要维护一个 dsf,在求解过程开始时网格为空时初始化,然后随过程推进更新它。

但是,要在游玩过程中使用同一套系统,而玩家可能以任意方式添加或移除边,你就必须在每次想检查错误时从头开始,也就是玩家每走一步时。每次,你新建一个 dsf;遍历玩家的游戏状态,统一玩家已填充的每条边的端点;在每种情况下,事先检查端点是否已经等价,如果是,就判定玩家的解答无效,因为它有环。

这个算法是正确的,而且非常高效。对于自动求解来说,它完全没有问题,尤其是因为整个求解器运行期间你只需保留一个 dsf。所以 Puzzles 中的自动求解器仍然用这种方式做环检测。

但它不会生成我在

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →