地图拼贴算法

地图

我正在使用Javascript制作基于图块的RPG游戏，使用perlin噪声高度图，然后根据噪音高度分配图块类型。

地图最终看起来像这样（在小地图视图中）。

我有一个相当简单的算法，它从图像上的每个像素中提取颜色值，并根据其与瓷砖字典中的图块对应的（0-255）之间的位置将其转换为整数（0-5）。 然后将这个200x200数组传递给客户端。

然后引擎根据数组中的值确定图块并将其绘制到画布上。 所以，我最终会看到有趣的世界，它们具有逼真的外观特征：山脉，海洋等。

现在我想要做的下一件事是应用某种混合算法，如果邻居不是相同类型的话，会导致图块无缝融合到邻居中。 上面的示例地图是玩家在小地图中看到的内容。 在屏幕上，他们看到由白色矩形标记的部分的渲染版本; 其中瓷砖是与他们的图像，而不是单一颜色的像素呈现。

这是用户在地图上看到的内容的示例，但它与上面显示的视口不同。

正是在这种观点下，我希望发生转变。

算法

我想出了一个简单的算法，它将遍历视口内的地图，并在每个拼贴块的顶部渲染另一个图像，并提供其旁边的不同类型的拼贴块。 （不改变地图！只是渲染一些额外的图像。）算法的想法是分析当前瓦片的邻居：

这是引擎可能必须呈现的示例场景，其中当前瓦片是用X标记的瓦片。

一个3x3数组被创建并且它周围的值被读入。所以对于这个例子来说数组看起来像。

[
    [1,2,2]
    [1,2,2]
    [1,1,2]
];

然后，我的想法是为可能的瓷砖配置制定一系列案例。 在一个非常简单的层面上：

if(profile[0][1] != profile[1][1]){
     //draw a tile which is half sand and half transparent
     //Over the current tile -> profile[1][1]
     ...
}

这给出了这个结果：

它从[0][1]到[1][1] ，但不是从[1][1]到[2][1]过渡，其中硬边缘仍然存在。 所以我认为在这种情况下必须使用角落的瓦片。 我创建了两个3x3精灵图表，我认为它们将包含所有可能需要的图块组合。 然后我复制了游戏中存在的所有图块（白色区域是透明的）。 最终每个类型的瓷砖有16个瓷砖（每个spritesheet上的中心瓷砖未被使用）。

理想的结果

因此，使用这些新的贴图和正确的算法，示例部分将如下所示：

尽管我所做的每一次尝试都失败了，但算法中总是存在一些缺陷，并且模式变得很奇怪。 我似乎无法将所有案例都对，并且总体而言似乎是一个糟糕的做法。

一个办法？

所以，如果任何人都可以提供一个替代解决方案，以便我如何创建这种效果，或者写出分析算法的方向，那么我将非常感激！

---

该算法的基本思想是使用预处理步骤来查找所有边，然后根据边的形状选择正确的平滑块。

第一步是找到所有的边缘。 在下面的例子中，用X标记的边缘瓦片都是绿色的瓦片，棕褐色瓦片作为它们八个相邻瓦片中的一个或多个。 对于不同类型的地形，如果条件具有较低地形数的邻居，则该条件可以转化为瓦片作为边缘瓦片。

一旦检测到所有边缘瓦片，接下来要做的是为每个边缘瓦片选择正确的平滑瓦片。 这是我的平滑瓷砖的代表。

请注意，实际上没有那么多不同类型的切片。 我们需要来自3x3方格之一的八个外部方格，但只有四个角落方格，因为在第一个方格中已经找到了直线方格。 这意味着总共有12个不同的情况我们必须区分。

现在，通过查看一个边缘瓦片，我们可以通过查看其四个最近的邻居瓦片来确定边界转向的方式。 如上所述用X标记边缘瓦片，我们有以下六种不同的情况。

这些情况用于确定相应的平滑瓦片，我们可以相应地对平滑瓦片进行编号。

每种情况仍然有a或b的选择。 这取决于草的哪一面。 确定这种情况的一种方法是跟踪边界的方向，但最简单的方法是在边缘旁边选择一块瓷砖，并查看其颜色。 下图显示了两种情况5a）和5b），可以通过例如检查右上方瓷砖的颜色来区分这两种情况。

原始示例的最终枚举将如下所示。

并选择相应的边缘瓷砖后，边框看起来像这样。

作为最后的说明，我可以说，只要边界有点规则，这就会起作用。 更确切地说，不具有两个边缘瓦片作为其邻居的边缘瓦片将不得不分开处理。 这将发生在地图边缘上的边缘地砖上，该边缘地砖将具有单个边缘邻居，并且对于非常狭窄的地形区域，其中相邻边缘地砖的数量可以是三个甚至四个。

---

下面的正方形代表一块金属板。 右上角有一个“散热孔”。 我们可以看到，随着这一点的温度保持不变，金属板在每个点收敛到恒定的温度，在顶部附近自然更热：

在每个点找到温度的问题可以解决为“边界值问题”。 然而，在每个点处计算热量的最简单方法是将板模拟为网格。 我们知道恒温下电网上的点。 我们将所有未知点的温度设置为室温（就像通风口刚打开时那样）。 然后我们让热量通过盘子传播，直到达到收敛。 这是通过迭代完成的：我们遍历每个（i，j）点。 我们设定点（i，j）=（点（i + 1，j）+点（i-1，j）+点（i，j + 1）+点（i，j-1））/ 4 [除非点（i，j）具有恒温的排气口]

如果您将此应用于您的问题，它非常相似，只是平均颜色而不是温度。 你可能需要大约5次迭代。 我建议使用400x400网格。 这就是400x400x5 =少于100万次迭代，这将是快速的。 如果你只使用5次迭代，你可能不需要担心任何点保持恒定的颜色，因为它们不会偏离原来的太多（实际上只有颜色的距离5内的点才会受到颜色的影响）。 伪代码：

iterations = 5
for iteration in range(iterations):
    for i in range(400):
        for j in range(400):
            try:
                grid[i][j] = average(grid[i+1][j], grid[i-1][j],
                                     grid[i][j+1], grid[i][j+1])
            except IndexError:
                pass

---

好的，首先想到的是，自动化问题的完美解决方案需要一些相当丰富的插值数学。 基于您提到预先渲染的平铺图像这一事实，我认为完整的插值解决方案不在此处。

另一方面，如你所说，手工完成地图会带来好的结果......但我也假设任何手动过程来修复毛刺也不是一种选择。

这是一个简单的算法，并不能给出完美的结果，但基于所花费的精力，这是非常有益的。

与其尝试混合每个边缘拼贴块（这意味着您需要首先知道混合相邻拼贴块的结果 - 插值，或者您需要多次优化整个地图，并且不能依赖预先生成的拼贴块）为什么不把瓷砖混合成交替棋盘格式？

[1] [*] [2]
[*] [1] [*]
[1] [*] [2]

也就是说只混合上面矩阵中出现的瓦片？

假设唯一允许的价值步骤是一次一个的，那么您只有几块地砖可以设计......

A    [1]      B    [2]      C    [1]      D    [2]      E    [1]           
 [1] [*] [1]   [1] [*] [1]   [1] [*] [2]   [1] [*] [2]   [1] [*] [1]   etc.
     [1]           [1]           [1]           [1]           [2]           

总共有16种模式。 如果利用旋转和反射对称，则会更少。

'A'将是一个普通的[1]风格的瓷砖。 'D'将是一个对角线。

瓷砖角落会有小的不连续处，但与您给出的例子相比，这些会很小。

如果我能，我会稍后用图片更新这篇文章。

链接地址: http://www.djcxy.com/p/6837.html

上一篇: Map Tiling Algorithm

下一篇: What are the mathematical/computational principles behind this game?