地图切片算法

javascript html algorithm canvas

2022-08-30 02:41:17

地图

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

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

enter image description here

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

然后，引擎从数组中的值中确定切片，并将它们绘制到画布上。所以，我最终得到了有趣的世界，这些世界具有逼真的特征：山脉，海洋等。

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

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

enter image description here

正是在这种观点中，我希望过渡发生。

算法

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

An example of a tile profile

这是引擎可能必须呈现的内容的示例方案，当前磁贴是用 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]
     ...
}

这给出了这样的结果：

Result

它的工作原理是从到，但不是从到的过渡，其中保留一个硬边。所以我想在这种情况下，必须使用角图块。我创建了两个 3x3 精灵表，我认为这两个表可以容纳所有可能需要的图块组合。然后，我为游戏中的所有图块复制了这一点（白色区域是透明的）。这最终是每种类型的磁贴有 16 个磁贴（不使用每个 spritesheet 上的中心磁贴。[0][1][1][1][1][1][2][1]

Sand Sand2

理想的结果

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

Correct

但是，我所做的每一次尝试都失败了，算法中总是存在一些缺陷，并且模式最终变得奇怪。我似乎无法正确处理所有案例，总的来说，这似乎是一种糟糕的方法。

解决方案？

因此，如果有人可以提供另一种解决方案，说明我如何创建这种效果，或者编写分析算法的方向，那么我将不胜感激！

答案 1

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

第一步是找到所有边缘。在下面的示例中，标有 X 的边缘磁贴都是绿色磁贴，其中棕褐色磁贴作为其八个相邻磁贴中的一个或多个。对于不同类型的地形，如果图块具有较低地形数的相邻点，则此条件可以转换为边缘图块。

Edge tiles.

检测到所有边缘拼贴后，接下来要做的就是为每个边拼贴选择正确的平滑拼贴。这是我对您的平滑瓷砖的表示。

Smoothing tiles.

请注意，实际上没有那么多不同类型的磁贴。我们需要来自 3x3 正方形之一的八个外部图块，但只需要来自另一个正方形的四个角方块，因为直边方块已经在第一个正方形中找到。这意味着我们必须区分总共有12种不同的情况。

现在，查看一个边缘图块，我们可以通过查看其最近的四个相邻图块来确定边界向哪个方向转动。用X标记边缘磁贴，就像上面一样，我们有以下六种不同的情况。

Six cases.

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

Smoothed tiles with numbers.

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

Choosing 5a or 5b.

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

Final enumeration.

选择相应的边缘磁贴后，边框将如下所示。

Final result.

作为最后的说明，我可能会说，只要边界有点规律，这就会起作用。更准确地说，没有两个边缘图块作为其邻居的边缘图块必须单独处理。对于地图边缘的边缘图块（将具有单个边缘邻居）和非常狭窄的地形（相邻边缘图块的数量可能为三个甚至四个），将发生这种情况。

答案 2

下面的正方形表示金属板。右上角有一个“热通风口”。我们可以看到，当该点的温度保持不变时，金属板在每个点处收敛到恒定的温度，在顶部附近自然变热：

heatplate

在每个点找到温度的问题可以作为“边界值问题”来解决。然而，计算出每个点的热量的最简单方法是将板建模为网格。我们知道恒温下电网上的点。我们将所有未知点的温度设置为室温（就好像通风口刚刚打开一样）。然后，我们让热量通过板传播，直到我们达到收敛。这是通过迭代完成的：我们迭代每个（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