有趣的地图几何与数学

# Ultima Ratio Regum 0.11 更新 #57：有趣的地图几何与数学 来源：https://www.markrjohnsongames.com/2026/04/11/ultima-ratio-regum-0-11-update-57-interesting-map-geometry-and-mathematics/ Ultima Ratio Regum 0.11 更新 #57：有趣的地图几何与数学 (https://www.markrjohnsongames.com/2026/04/11/ultima-ratio-regum-0-11-update-57-interesting-map-geometry-and-mathematics/) 大家好！这次的更新内容有点不一样。我平时不太详细讨论代码的具体实现，更倾向于聚焦设计问题，但这周我决定破个例。在自上次更新 (https://www.markrjohnsongames.com/2026/03/30/ultima-ratio-regum-0-11-update-56-huge-map-clue-advancement-and-integration-complete/) 以来，处理世界地图线索的一些边缘情况和 bug 时，我遇到了一个有点意思的挑战——如何解决一个虽罕见但棘手的问题。具体来说，这个问题涉及地图线索上的损坏区域有机扩散时，可能让线索的一部分孤零零地漂浮在损坏区域的“海洋”中，周围没有任何其他元素相连。如果不太清楚这是什么意思，请看下图： 从“沉浸感”的角度来看，这显然是个问题，原因不言而喻——玩家角色怎么可能知道那块重要部分应该位于何处？而且，图中那个至关重要的“X”恰好成为孤立的幸存部分纯属巧合；在其他例子中，我也见过地图的任意元素被孤立，甚至多个图块一起形成更大的“孤岛”。这个问题亟待解决，但处理起来却出乎意料地棘手。原因有好几个：首先，我需要一种方法，在生成损坏时增加尽可能少的时间开销。最直接的方案是某种泛洪填充算法，即不断测试所有未损坏的地图部分是否仍然连通，一旦发现不连通，就移除/撤销最后添加的损坏块。这很直观，但有问题。正如该技术的 Wikipedia 页面 (https://en.wikipedia.org/wiki/Flood_fill) 详细指出的，优化这个算法在计算上相当困难，因为有很多方式会导致耗时惊人。这之所以是个问题，是因为生成更高级别的地图（我将其归类为“困难”或“极难”难度），本身就已经比“简单”或“普通”难度的地图要难得多——游戏必须丢弃一些尝试，因为它们不符合我设定的参数。这意味着我极其不希望再给生成系统增加一个计算密集的环节，尤其不管这个计算 *是什么*，它都必须在每次添加一个损坏块后运行一次（严格来说，并不是每次都需要——前七个损坏块添加后不必运行，因为需要八个才能形成一个完整回路，但你明白我的意思）。 第二个挑战是，损坏的填充方式相当有机——游戏会在网格上选择若干个起始点（高难度多一点，低难度少一点），然后让它们向各个方向扩散（高难度扩散多，低难度扩散少），迭代一定次数（同样，高难度次数多，低难度次数少）。这种方法能创造出非常丰富、看起来自然的损坏效果，我非常不愿意改变它，尤其是我已经花了大量时间优化这段代码，确保它在美学和游戏性两方面都能产出我期望的结果——但我看不出如何用一种非泛洪填充的明显方式，利用现有的代码来检查是否会产生“孤岛”。如果一个损坏块碰触到另一个损坏块，这本身不是问题，也不会自动产生漂浮孤岛。最好的替代方案似乎是：每次向某个图块添加损坏时，查看它上下左右的相邻图块，然后再从 *这些* 图块查看它们上下左右的图块，如果已经有三四个损坏块，就不添加你刚加的损坏。这肯定比泛洪填充快，但计算量依然不小——对于大量损坏，你可能要运行这个检查 50 次左右，每次检查 16 个图块，一共 800 次检查，每次都需要查询两个不同的网格（*地图* 网格和 *损坏* 网格）——而且即便如此，它也并没有完全解决问题，因为它无法阻止 2 图块或 3 图块的孤岛出现！现在，代码已经有一些机制来确保整个 *地图* 不会被分成两半，即只允许地图边缘的一个图块被损坏（这本身并不总是发生，但在小地图上比大地图上更常见，因为边缘占地图总尺寸的比例更大），这很有帮助，但那段代码无法阻止这些内部孤岛。所以，鉴于以上所有情况，我必须找到另一个解决方案——而这篇博文要讲的就是寻找和优化那个解决方案的逻辑/思维过程 :)。 于是，我开始考虑其他替代方案，突然想到一个计算上极其简单的想法——只需要在游戏考虑添加某个损坏块时，快速检查一下某个东西。这个想法是：在地图网格下方隐藏一个玩家永远看不到的网格，其中有一组特定的图块 *不能* 被损坏，并且这些图块在几何上被排列成某种方式，使得孤岛永远不可能形成。我意识到，如果地图上的某个图块永远不会变成损坏块，那么它周围的所有图块，在某种意义上，就“安全”了，不会被变成孤岛图块，因为它们保证会与一个永远不能变成损坏的图块相邻。有了这个认识后，我打开画图软件，制作了一个基本的 9×9 网格——我意识到最大的世界地图线索将是实现这个方案最难的部分，所以从那里开始——然后实验用最少多少个图块就能成功实现这个效果。我的初步实验，仅仅基于我刚才概述的逻辑，最终看起来像下面这样，我满意了大约 10 秒钟，心想只要红色图块始终是非损坏图块，我们就永远不会有孤岛，因为其他每个图块都与一个红色图块相邻……对吧？嗯，不，显然不对，我的大脑立刻指出，这根本无法阻止多图块孤岛的出现，即使它确实能成功阻止单图块孤岛。哎呀。 那么下一个方案就是，找到一个模型，使得整个网格上没有哪个图块不与红色图块（即在此模型中，我禁止其成为损坏块的图块）接触，*并且* 确保没有可能形成回路。我意识到，这实际上意味着，不能被损坏的图块（红色）都必须以某种方式连接到地图的边缘，否则游戏——在极其罕见的边缘情况下，但依然可能——有可能在它们周围生成一个更大的损坏回路，从而在中心产生一个更大的漂浮孤岛，而不是单个图块。不过，我当然不想过多干扰线索损坏的整体形状，并希望找到最大的空间可以保持没有“不能损坏”图块，同时确保每个图块都与其中之一接触。经过一番思考，我决定平行对角线可能是最好的方式，因为水平或垂直的平行线只能让其他图块形成 2×2 的块存在于它们之间，而在这里，我们可以拥有*几乎* 3×3 的损坏有效图块块，每个块只需被一个红色图块“挖掉”一个图块，以确保每个可能的图块都被一个不能损坏的图块“接地”，从而防止孤岛。我当时还认为，边缘图块通常也必须是红色图块，这样内部的图块就不能通过边缘损坏构成的回路变成孤岛（此刻我并没有忘记之前已经在生成器中实现的“只允许地图边缘一个图块被损坏”规则，但我还没意识到这个规则对这个系统的影响）。经过一番考虑，并试图最小化不能损坏图块的数量，我提出了以下方案，作为可能的隐藏网格，它确实能够完全防止线索孤岛的出现： 我对这个方案相当满意，但对其局限性感到失望——线索上那么多潜在的可损坏空间都被排除在外了！当然，这个方案可以有一些变体，比如沿 x 轴或 y 轴翻转来得到另一种可能性，而且对角线也可以放置在不同的位置来达到同样的目标……即便如此，地图线索中相当大的一部分区域——在这个模型下——是不能被损坏的。尽管如此，这似乎是我能想到的最佳方案了，所以我花了一些时间探索其他几何布局，以最大化可能出现的“不能损坏”图块布局的范围，这样即使在上面的版本中某些区域不能损坏，在其他版本中这些图块 *可以* 被损坏——由于这些是隐藏的、玩家永远看不到的东西，玩家应该永远不会注意到或意识到其中某个网格在暗中塑造了高难度世界地图线索上损坏的最终分布形式。实际上，这真是一次非常有趣的智力和几何练习，因为我总是在试图确保“不能损坏”图块的数量尽可能少，同时确保每个图块都与其中之一相连，并且它们都到达地图网格的边缘，*并且* 它们以各种有趣的方式做到这一点，以确保线索上仍然可以生成尽可能多的损坏变形，而不会受到这些防止孤岛出现的隐藏网格的过多限制。经过一番努力，我最终想出了类似下面这样的方案，并开始从内心了解这个特定几何问题的一些“规则”： （实际上其中两个有错误——看看你能不能找出这两个网格中实际可能产生孤岛的地方？） 这些方案确实有效，但到这个时候，我真的开始担心它们 *注定* 会限制可能出现的损坏形状。如果你回顾一下上周的更新 (https://www.markrjohnsongames.com/2026/03/30/ultima-ratio-regum-0-11-update-56-huge-map-clue-advancement-and-integration-complete/)，一些“困难”和“极难”难度的地图上有大片区域被损坏移除，形状各异，而无论我怎么尝试，这些隐藏网格 *注定* 会限制这一点。我意识到，实际上很多“不能损坏”图块在大多数损坏生成中根本用不上，但它们仍然会阻止损坏生成（至少大部分时间是这样），使得最终结果不如我期望的那么有趣。这有点两难，但后来我有了一个想法，也有了一个领悟。想法是这样的：如果我们将“不能损坏”图块分成组，让损坏生成器计算每组中有多少图块已被损坏，而且只有当一组中 *所有* 图块都被损坏（从而可能形成回路）时，游戏才说“不行！”并阻止添加损坏。但在细化这个想法时，我意识到这不行，因为在达到主要尺寸之前，仍然可能形成较小的损坏回路。所以我转而考虑一种系统，其中某些图块只有在其他图块被损坏/未被损坏时才能被损坏——这个想法在下面左图中大致勾勒出来。与此同时，我领悟到：每个地图上的整个外部循环图块，*以及* 第二层外部循环图块，无论如何都不会变成孤岛！在任何情况下，这都需要多个外部循环图块被损坏，而已经有一条规则禁止了这一点，所以这大大简化了问题。综合这两点，我试图找到一个模型——下面右图——其中我们可以有少量的成组图块，每组只有一个能被损坏，而只有少数几个绝对 *不能* 损坏的图块……但这变得相当复杂，计算开销也比我想象的要大，需要大量的条件判断才能让这样的系统工作。 然而，既然已经意识到最外两层循环已经免疫于这个问题，那么只有内部区域令人头疼，我们只需将这些内部区域连接到最外两层循环。这再次变成了一个有趣的几何和数学小问题——如何以最有效的方式做到这一点，使得所有“不能损坏”图块都以某种方式连接到第二外层循环或另一个“不能损坏”图块，而其他所有图块（最外两层除外）都正交或对角地与一个“不能损坏”图块相连，*并且* 我们拥有尽可能少的“不能损坏”图块，以确保为世界地图线索生成视觉损坏时获得最大的可能性空间？下面是我早期的两个实验，左边只需要九个图块就能满足 9×9 世界地图线索网格中所有位置的条件，右边则需要十个图块来满足相同条件。在摆弄这些方案时，我没有找到只需要八个图块的方案，但也许确实存在？如果你能找到满足这些规则的方案（假设从我的描述中你能理解这些规则……），请告诉我，我很想看看。总之，这两个方案让我非常满意，因为它们仍然允许地图损坏视觉效果有极大的多样性，同时确保不可能产生单图块孤岛。正是在这一点上，我开始觉得自己真的取得了进展——早期的一些版本有那么多“不能损坏”图块，我 *确实* 担心会对最终结果产生非常不利的影响，但现在，我对事情最终会是什么样子感到相当有信心。 *不过*，这些方案中的对角线部分让我觉得最好能去掉它们。有些地图线索确实会以地图的一部分仅仅通过“对角线”悬挂在其余部分上的方式生成，这看起来 *还行*，但视觉上不如其他生成方式漂亮（即地图各部分之间通过正交连接）。因此，我回到画图软件中的网格，试图找到一些“不能损坏”图块布局，它们的连接完全或主要是正交的，以再次确保我们得到更好看的生成效果。这有点棘手，因为正交线在平面上覆盖的“距离”不如对角线——这就是为什么许多策略游戏采用六边形网格，以防止对角线移动在客观上比正交移动更强——但为了得到更美观的视觉效果，这是值得的。我继续尝试了几种不同的布局，最终找到了一个方案，它使用一组正交连接且延伸到达到第二层外环的“不能损坏”图块，同时仍能确保每个内部图块都接近其中一个红色图块。这个新方案最终看起来像下面这样，它只使用了七个“不能损坏”图块（相对于 9×9 网格），并且完全通过正交连接，这意味着损坏的生成看起来会更自然，而不会出现那种仅靠对角线相连的奇怪“悬挂”效果。 这个最终方案让我非常满意。它计算上轻量（每次添加损坏块时只需一次快速检查），几乎不影响生成时间，并且通过简单地禁止某些图块被损坏，确保了永远不会产生任何孤岛。由于这些隐藏网格是随机的且玩家不可见，因此玩家永远无法察觉到它们的存在，但是它们悄悄地确保了地图损坏生成始终是视觉上连贯且可信的。在实现并测试这个系统后，我所有的担忧都烟消云散了——生成的损坏看起来仍然像以前一样有机和多样，但再也不会出现孤立的图块或小群组浮现在损坏的“海洋”中。这是一个很棒的解决方案，也是一个很好的例子，说明有时在幕后添加一个简单的约束比试图直接解决复杂问题更有效。希望这篇关于修复一个边缘情况中的思维过程的解释对你有用。一如既往，如果你有任何问题或想法，请在评论中告诉我！