地图拼贴算法

地图

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

地图最终看起来像这样(在小地图视图中)。

enter image description here

我有一个相当简单的算法，从图像的每个像素提取颜色值，并转换成一个整数(0-5)取决于它的位置之间(0-255)对应的瓦片字典。然后将这个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

它作为从 [0][1]到 [1][1]的过渡工作，但不是从 [1][1]到 [2][1]的过渡工作，在那里硬边仍然存在。所以我想，在那种情况下，一个角瓦将不得不使用。我创建了两个3x3精灵表，我认为将持有所有可能的组合瓷砖，可能需要。然后我为游戏中的所有瓷砖复制了这个(白色区域是透明的)。最终，每种类型的瓷砖有16个瓷砖(不使用每个电子表格上的中心瓷砖)

SandSand2

理想的结果

因此，使用这些新的贴片和正确的算法，示例部分应该是这样的:

Correct

尽管我每次尝试都失败了，但是算法总是有一些缺陷，而且模式结果都很奇怪。我似乎不能把所有的案子都处理好，而且总的来说，这似乎是一种糟糕的处理方式。

解决方案？

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

26838 次浏览
小开

我有几点建议:

  • “中心”是什么并不重要，对吧？它可以是2，但如果其他的都是1，它会显示1？

  • 只有当顶部或侧面的近邻有差异时，角落是什么才重要。如果所有的近邻都是1，一个角是2，那么它将显示1。

  • 我可能会预先计算所有可能的邻居组合，创建一个8索引数组，前四个指示顶部/底部邻居的值，第二个指示对角线:

边[ N ][ E ][ S ][ W ][ NE ][ SE ][ SW ][ NW ] = 进入精灵的任何偏移量

所以在你的例子中，[2][2][1][1][2][2][1] = 4(第五个精灵)。

在这种情况下，[1][1][1][1]就是1，[2][2][2][2][2]就是2，剩下的就要算出来了。但是查找某个特定的瓦片将是微不足道的。

小开

好吧，第一个想法是，自动化一个完美的解决方案的问题需要一些相当丰富的插值数学。基于你提到的事实，预渲染瓦图像，我认为完整的插值解决方案是不保证在这里。

另一方面，正如你所说，手工完成地图将导致一个良好的结果..。 但我也假设，任何手动处理来修复故障也不是一个选项。

这里有一个简单的算法，不会给出一个完美的结果，但这是非常有益的，基于它所需的低努力。

与其尝试混合每一个边缘的瓦片，(这意味着你要么需要先知道混合相邻瓦片的结果-插值，或者你需要对整个地图进行多次细化，不能依赖于预先生成的瓦片)为什么不用交替棋盘格式混合瓦片呢？

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

在瓷砖的角落将会有一些小的不连续性，但是与您给出的示例相比，这些不连续性将会很小。

如果可以的话，我以后会用图片更新这篇文章。

小开

我当时正在做一个类似的东西，由于很多原因它还没有完成，但是基本上它需要一个0和1的矩阵，0是地面，1是一个迷宫生成器在 Flash 中的应用程序的墙。因为 AS3类似于 JavaScript，所以在 JS 中重写并不困难。

var tileDimension:int = 20;
var levelNum:Array = new Array();


levelNum[0] = [1, 1, 1, 1, 1, 1, 1, 1, 1];
levelNum[1] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[2] = [1, 0, 1, 1, 1, 0, 1, 0, 1];
levelNum[3] = [1, 0, 1, 0, 1, 0, 1, 0, 1];
levelNum[4] = [1, 0, 1, 0, 0, 0, 1, 0, 1];
levelNum[5] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[6] = [1, 0, 1, 1, 1, 1, 0, 0, 1];
levelNum[7] = [1, 0, 0, 0, 0, 0, 0, 0, 1];
levelNum[8] = [1, 1, 1, 1, 1, 1, 1, 1, 1];


for (var rows:int = 0; rows < levelNum.length; rows++)
{
for (var cols:int = 0; cols < levelNum[rows].length; cols++)
{
// set up neighbours
var toprow:int = rows - 1;
var bottomrow:int = rows + 1;


var westN:int = cols - 1;
var eastN:int = cols + 1;


var rightMax =  levelNum[rows].length;
var bottomMax = levelNum.length;


var northwestTile =     (toprow != -1 && westN != -1) ? levelNum[toprow][westN] : 1;
var northTile =         (toprow != -1) ? levelNum[toprow][cols] : 1;
var northeastTile =     (toprow != -1 && eastN < rightMax) ? levelNum[toprow][eastN] : 1;


var westTile =          (cols != 0) ? levelNum[rows][westN] : 1;
var thistile =          levelNum[rows][cols];
var eastTile =          (eastN == rightMax) ? 1 : levelNum[rows][eastN];


var southwestTile =     (bottomrow != bottomMax && westN != -1) ? levelNum[bottomrow][westN] : 1;
var southTile =         (bottomrow != bottomMax) ? levelNum[bottomrow][cols] : 1;
var southeastTile =     (bottomrow != bottomMax && eastN < rightMax) ? levelNum[bottomrow][eastN] : 1;


if (thistile == 1)
{
var w7:Wall7 = new Wall7();
addChild(w7);
pushTile(w7, cols, rows, 0);


// wall 2 corners


if      (northTile === 0 && northeastTile === 0 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
{
var w21:Wall2 = new Wall2();
addChild(w21);
pushTile(w21, cols, rows, 270);
}


else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 0)
{
var w22:Wall2 = new Wall2();
addChild(w22);
pushTile(w22, cols, rows, 0);
}


else if (northTile === 1 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 1 && northwestTile === 1)
{
var w23:Wall2 = new Wall2();
addChild(w23);
pushTile(w23, cols, rows, 90);
}


else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
{
var w24:Wall2 = new Wall2();
addChild(w24);
pushTile(w24, cols, rows, 180);
}


//  wall 6 corners


else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 0 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 1)
{
var w61:Wall6 = new Wall6();
addChild(w61);
pushTile(w61, cols, rows, 0);
}


else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 0 && westTile === 1 && northwestTile === 1)
{
var w62:Wall6 = new Wall6();
addChild(w62);
pushTile(w62, cols, rows, 90);
}


else if (northTile === 1 && northeastTile === 1 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 0)
{
var w63:Wall6 = new Wall6();
addChild(w63);
pushTile(w63, cols, rows, 180);
}


else if (northTile === 1 && northeastTile === 0 && eastTile === 1 && southeastTile === 1 && southTile === 1 && southwestTile === 1 && westTile === 1 && northwestTile === 1)
{
var w64:Wall6 = new Wall6();
addChild(w64);
pushTile(w64, cols, rows, 270);
}


//  single wall tile


else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
{
var w5:Wall5 = new Wall5();
addChild(w5);
pushTile(w5, cols, rows, 0);
}


//  wall 3 walls


else if (northTile === 0 && eastTile === 1 && southTile === 0 && westTile === 1)
{
var w3:Wall3 = new Wall3();
addChild(w3);
pushTile(w3, cols, rows, 0);
}


else if (northTile === 1 && eastTile === 0 && southTile === 1 && westTile === 0)
{
var w31:Wall3 = new Wall3();
addChild(w31);
pushTile(w31, cols, rows, 90);
}


//  wall 4 walls


else if (northTile === 0 && eastTile === 0 && southTile === 1 && westTile === 0)
{
var w41:Wall4 = new Wall4();
addChild(w41);
pushTile(w41, cols, rows, 0);
}


else if (northTile === 1 && eastTile === 0 && southTile === 0 && westTile === 0)
{
var w42:Wall4 = new Wall4();
addChild(w42);
pushTile(w42, cols, rows, 180);
}


else if (northTile === 0 && northeastTile === 0 && eastTile === 1 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 0 && northwestTile === 0)
{
var w43:Wall4 = new Wall4();
addChild(w43);
pushTile(w43, cols, rows, 270);
}


else if (northTile === 0 && northeastTile === 0 && eastTile === 0 && southeastTile === 0 && southTile === 0 && southwestTile === 0 && westTile === 1 && northwestTile === 0)
{
var w44:Wall4 = new Wall4();
addChild(w44);
pushTile(w44, cols, rows, 90);
}


//  regular wall blocks


else if (northTile === 1 && eastTile === 0 && southTile === 1 && westTile === 1)
{
var w11:Wall1 = new Wall1();
addChild(w11);
pushTile(w11, cols, rows, 90);
}


else if (northTile === 1 && eastTile === 1 && southTile === 1 && westTile === 0)
{
var w12:Wall1 = new Wall1();
addChild(w12);
pushTile(w12, cols, rows, 270);
}


else if (northTile === 0 && eastTile === 1 && southTile === 1 && westTile === 1)
{
var w13:Wall1 = new Wall1();
addChild(w13);
pushTile(w13, cols, rows, 0);
}


else if (northTile === 1 && eastTile === 1 && southTile === 0 && westTile === 1)
{
var w14:Wall1 = new Wall1();
addChild(w14);
pushTile(w14, cols, rows, 180);
}


}
// debug === // trace('Top Left: ' + northwestTile + ' Top Middle: ' + northTile + ' Top Right: ' + northeastTile + ' Middle Left: ' + westTile + ' This: ' + levelNum[rows][cols] + ' Middle Right: ' + eastTile + ' Bottom Left: ' + southwestTile + ' Bottom Middle: ' + southTile + ' Bottom Right: ' + southeastTile);
}
}


function pushTile(til:Object, tx:uint, ty:uint, degrees:uint):void
{
til.x = tx * tileDimension;
til.y = ty * tileDimension;
if (degrees != 0) tileRotate(til, degrees);
}


function tileRotate(tile:Object, degrees:uint):void
{
// http://www.flash-db.com/Board/index.php?topic=18625.0
var midPoint:int = tileDimension/2;
var point:Point=new Point(tile.x+midPoint, tile.y+midPoint);
var m:Matrix=tile.transform.matrix;
m.tx -= point.x;
m.ty -= point.y;
m.rotate (degrees*(Math.PI/180));
m.tx += point.x;
m.ty += point.y;
tile.transform.matrix=m;
}

基本上，这会检查从左到右，从上到下的每一个贴片，并假设边缘贴片总是1。我还擅自将这些图像导出为一个文件作为一个键:

Wall tiles

这是不完整的，可能是一个粗糙的方法来实现这一点，但我认为它可能会有一些好处。

编辑: 代码结果的屏幕截图。

Generated Result

小开

下面的正方形代表一块金属板。在右上角有一个“热通风口”。我们可以看到，当这一点的温度保持不变时，金属板在每一点都会收敛到一个恒定的温度，接近顶部的地方自然会变得更热:

heatplate

找出每个点的温度的问题可以作为一个“边值问题”来解决。然而，计算每个点的热量的最简单的方法是将平板模拟为网格。我们知道网格上的点在恒定温度下。我们将所有未知点的温度设置为室温(就好像通风口刚刚打开一样)。然后我们让热量通过平板传播，直到我们达到收敛。这是通过迭代完成的: 我们遍历每个(i，j)点。我们设定点(i，j) = (point (i + 1，j) + point (i-1，j) + point (i，j + 1) + point (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
小开
最佳答案

该算法的基本思想是通过一个预处理步骤找到所有的边缘，然后根据边缘的形状选择正确的平滑瓦。

第一步是找到所有的边缘。在下面的例子中，标有 X 的 镶边瓷砖都是绿色瓷砖，棕褐色瓷砖是其八个相邻瓷砖中的一个或多个。对于不同类型的地形，这种情况可以转化为一个瓦片是一个边缘瓦片，如果它有邻居较低的地形数量。

Edge tiles.

一旦检测到所有的边缘贴片，接下来要做的就是为每个边缘贴片选择正确的平滑贴片。这是我对你们光滑瓷砖的描述。

Smoothing tiles.

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

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

Six cases.

这些情况用来确定相应的平滑瓦，我们可以编号平滑瓦相应。

Smoothed tiles with numbers.

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

Choosing 5a or 5b.

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

Final enumeration.

在选择了相应的边框之后，边框看起来就像这样。

Final result.

最后，我可以说，只要边界是有规则的，这就可以。更准确地说，没有正好两个边缘瓷砖作为它们的邻居将必须分开处理。这种情况会发生在地图边缘的边缘瓷砖，这将有一个单一的边缘邻居和非常狭窄的地形片，其中相邻的边缘瓷砖的数量可能是三个甚至四个。


提交答案