地图拼贴算法

Question

地图

我正在使用Javascript制作基于图块的RPG,使用perlin噪声高度图,然后根据噪声的高度指定一个图块类型.

地图最终看起来像这样(在迷你地图视图中).

我有一个相当简单的算法,它从图像上的每个像素中提取颜色值,并根据其在(0-255)之间的位置将其转换为整数(0-5),该位置对应于图块字典中的图块.然后将此200x200阵列传递给客户端.

然后,引擎根据数组中的值确定切片并将其绘制到画布.所以,我最终得到了具有现实主义特征的有趣世界:山脉,海洋等.

现在我要做的下一件事就是应用某种混合算法,如果邻居不是同一类型的话,会使得瓷砖无缝地融合到它们的邻居中.上面的示例地图是玩家在小地图中看到的内容.屏幕上他们看到标有白色矩形的部分的渲染版本; 使用图像而不是单色像素渲染切片的位置.

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

在这种观点中,我希望过渡发生.

算法

我想出了一个简单的算法,它将遍历视口中的地图,并在每个图块的顶部渲染另一个图像,前提是它位于不同类型的图块旁边.(不改变地图!只是渲染一些额外的图像.)算法的想法是分析当前tile的邻居:

这是引擎可能必须呈现的示例场景,其中当前图块是标记为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上的中心瓷砖.)

理想的结果

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

尽管如此,我所做的每一次尝试都失败了,算法总会有一些缺陷,模式最终会变得奇怪.我似乎无法让所有案例都正确,总体而言,这似乎是一种糟糕的做法.

一个办法？

那么,如果有人能提供一个替代解决方案,我将如何创建这种效果,或者编写分析算法的方向,那么我将非常感激!

Answer 1

该算法的基本思想是使用预处理步骤来找到所有边缘,然后根据边缘的形状选择正确的平滑贴片.

第一步是找到所有边缘.在下面的示例中,标有X 的边缘区块都是绿色区块,其中棕褐色区块是其八个相邻区块中的一个或多个.对于不同类型的地形,如果该地块具有较低地形数的邻居,则该条件可以转化为作为边缘地块的地块.

一旦检测到所有边缘图块,接下来要做的是为每个边缘图块选择正确的平滑图块.这是我对平滑瓷砖的表示.

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

现在,通过查看一个边缘区块,我们可以通过查看其四个最接近的相邻区块来确定边界转向的方向.如上所述用X标记边缘图块我们有以下六种不同的情况.

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

每种情况仍然可以选择a或b.这取决于草在哪一侧.确定这一点的一种方法可能是跟踪边界的方向,但最简单的方法是在边缘旁边挑一块瓷砖,看看它有什么颜色.下面的图像显示了两种情况5a)和5b),它们可以通过例如检查右上方瓷砖的颜色来区分.

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

选择相应的边缘瓷砖后,边框看起来像这样.

作为最后一点,我可能会说,只要边界有些规律,这就可行.更确切地说,不必具有与其邻居完全相同的两个边缘瓦片的边缘瓦片将必须单独处理.对于将具有单个边缘邻居的地图边缘上的边缘瓦片以及对于相邻边缘瓦片的数量可以是三个或甚至四个的非常窄的地形块,将发生这种情况.

Answer 2

以下方块表示金属板.右上角有一个"散热孔".我们可以看到,当这个点的温度保持不变时,金属板在每个点收敛到恒定温度,在顶部附近自然更热:

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

Answer 3

好吧,首先想到的是,自动化问题的完美解决方案需要一些相当内容丰富的插值数学.基于您提到预渲染的平铺图像这一事实,我认为这里不保证完整的插值解决方案.

另一方面,正如你所说的那样,手工完成地图将会产生良好的效果......但我也认为任何修复故障的手动过程也不是一种选择.

这是一个简单的算法,没有给出完美的结果,但这是非常有益的,因为它需要的努力.

而不是尝试混合每个边缘区块(这意味着您需要首先知道混合相邻区块的结果 - 插值,或者您需要多次优化整个地图并且不能依赖于预先生成的区块)为什么不以交替的棋盘格图案混合瓷砖？

[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'将是一个对角线.

在瓷砖的角落处会有小的不连续性,但与您给出的示例相比,这些不连续性会很小.

如果我可以稍后用图像更新此帖子.