😹 🦄 👈 基于约束的图块放置算法 👨🏿‍🤝‍👨🏽 🉑 😗

这篇文章介绍了“ 生成世界” （ Generate Worlds）中使用的算法，该工具允许用户通过构建少量的体素图块来创建和探索程序世界。我将对该算法进行简要说明，并且在以下文章中，我将讨论与其他方法相比在速度和灵活性方面的优势。要了解有关基于约束的程序生成是什么及其有趣之处的更多信息，建议阅读前一篇文章。

如果要测试使用此系统创建程序世界的优势，可以购买“生成世界”。如果价格对您来说太高了，请继续阅读：这篇文章将为您提供有关如何独立实现Generate Worlds算法的信息。

瓷砖套装

在“生成世界”中，每个世界都是由一组图块（图块）组成的。本质上，图块只是小型体素模型。让我们从一个例子开始。下图由9个图块组成。如您所见，每个图块均包含显示为彩色立方体的体素。

如果按照逻辑方式排列这些体素模型，则可以创建一个漂亮的田园场景，如下面的动画所示。所谓“逻辑”，是指如果瓷砖沿接缝边缘的颜色匹配，则它们可以放在一起。

生成世界算法的任务是快速，自动地完成此类装配。在开始算法之前，让我们看一下问题的陈述。

我们相互连接瓷砖

看一下包含4个图块的图块集：

这些图块类似于上面显示的三维图块。

生成世界算法使用一个简单的规则创建有效的图块组合 ： 如果两个图块彼此接触，则沿触摸边缘的所有颜色必须匹配 。该规则正式确定了一位在职设计师使用体素瓷砖创建3D世界的方法。

在上面介绍的4个图块的允许组合中，沿边界的亮单元应仅接触亮单元，而暗单元应仅接触暗单元。例如：

正确和不正确连接的示例。

右边的示例是不可接受的，因为沿着图块触摸的边缘，浅色方块触摸深色方块。为该图块生成的两个有效组合如下所示：

在一般情况下，创建有效的图块组合并不是一件容易的事。例如，考虑以下简单的“贪婪”策略：我们从一个空网格开始。在每次迭代中，我们将图块放置在某个点，并考虑到已放置的图块，选择可接受的图块。下图显示了这种策略的问题。

如果我们在放置瓷砖的时候没有预见到放置将如何影响未来的选择，那么“贪婪”算法将很快陷入停顿；在上图中，红色方块中不能放置有效的图块。这是主要问题：以前发布的图块可以将当前选项的数量减少到零。我们需要某种方法来防止放置瓷砖，这可能导致我们陷入僵局。在“生成世界”中实现的算法首先考虑所有可能放置在所有网格点上的图块。如果我们在网格中放置一个图块，那么很明显，将来的某些选项将变得不可访问。在算法消除了这些选项之后，我们可以重新检查剩余的选项，并消除现在与相邻点处较少数量的剩余可能的图块不兼容的其他图块。

考虑以下示例。该算法从3x3网格开始，在其中心有一个图块。该图块的位置意味着在相邻网格点处不允许有9个可能的图块，因此他将其丢弃，不再考虑它们。删除这些图块后，他可以删除与所有被认为是可以放置在相邻网格点上的图块不兼容的图块。图中的红色正方形标记了删除图块的点，因为它们与所有仍在考虑中的邻居不兼容。如果算法继续此过程，直到可以删除的图块，它将返回到电路左下角所示的状态。如您所见，许多图块被排除在考虑范围之外。如果放置磁贴的策略仅包括从剩余的这些组中选择磁贴，那么陷入死胡同的可能性将比上述“贪婪”方法低得多。

这种方法的问题在于，每次放置磁贴时，都需要进行昂贵的迭代过程。但是请注意，每次我放置一个带有倒T的图块时，在上一示例中删除的那19张图块都可以在此放置范围内从考虑中删除。我将图块称为集合，它们在托管图块周围仍然是有效选项，即该图块的有效邻居 。

借助信息缓存，可快速放置瓷砖

生成世界算法的最重要原理是，每次放置此图块时，都可以重用有关可能的图块邻居的信息。 例如，在网格的八个周围正方形的倒T的情况下，我们可以通过查看此图块可接受的邻域的缓存版本，在放置该图块后立即从考虑中删除19个图块。

例如，在下面的示例中，该算法使用4个图块的缓存允许邻域用图块填充5x5网格。放置第一个图块之后，他从考虑中删除了上面示例中不可能的19个图块。放置每个图块之后，将不在考虑范围内的所有选项都删除。