地图拼贴algorithm

地图

我正在用Javascript制作一个基于图块的RPG游戏，使用perlin noise heightmaps，然后根据噪音的高度分配一个图块types。

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

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

然后，引擎根据数组中的值确定拼贴，并将其绘制到canvas上。 所以，我最终会看到有趣的世界，这些世界具有逼真的外表特征：山脉，海洋等

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

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

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

algorithm

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

这是引擎可能需要渲染的一个示例场景，当前的tile是用X标记的。

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

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

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

 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]的过渡，其中硬边缘仍然存在。 所以我想，在这种情况下，一个angular落瓦片将不得不被使用。 我创build了两个3×3的精灵图表，我认为这些图表将会包含所有可能需要的图块组合。 然后我复制了这个游戏中所有的瓷砖（白色区域是透明的）。 这最终是每个types的瓷砖16个瓷砖（每个spritesheet中心瓷砖不使用）。

理想的结果

所以，使用这些新的贴图和正确的algorithm，示例部分将如下所示：

尽pipe我所做的每一次尝试都失败了，但是algorithm总是存在一些缺陷，模式变得很奇怪。 我似乎无法得到所有的案件，整体来看，这似乎是一个糟糕的做法。

一个办法？

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

Answer 1

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

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

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

请注意，实际上没有那么多不同types的图块。 我们需要从3×3方格之一的八个外部方块，但是只有四个angular落的方格，因为在第一个方格中已经find了直线方块。 这意味着总共有12个不同的情况我们必须区分。

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

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

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

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

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

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

Answer 2

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

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

如果你把这个问题应用到你的问题上，它就是非常相似，只是平均的颜色，而不是温度。 你可能需要大约5次迭代。 我build议使用400×400的网格。 这就是400x400x5 =less于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

好吧，首先想到的是，自动完成问题的解决scheme需要一些相当丰富的插值math。 基于您提到预渲染的平铺图像的事实，我假设完整的插值解决scheme在这里是不保证的。

另一方面，如你所说，手工完成地图将会产生一个好的结果……但是我也认为任何手动过程来修复故障也不是一个select。

这是一个简单的algorithm，不能给出一个完美的结果，但这是非常有益的，因为它需要很less的努力。

而不是试图混合每一个边缘的瓦片（这意味着你需要先知道混合相邻瓦片的结果 – 插值，或者你需要改进整个地图几次，不能依靠预先生成的瓦片）为什么不把瓷砖混合成交替的棋盘格呢？

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

也就是只混合上面matrix中出现的瓦片？

假设唯一允许的价值步骤是一次性的，你只有几个瓷砖devise…

 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个模式。 如果利用旋转和reflection对称，则会更less。

'A'将是一个简单的[1]风格的瓷砖。 'D'将是一个对angular线。

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

如果可以，我会稍后用图片更新这个post。

Answer 4

我正在玩类似的东西，这是因为一些原因没有完成; 但基本上它将采用0和1,0的matrix，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.我还冒着将图像作为文件导出以用作关键的自由：

这是不完整的，可能是一个很好的方法来实现这一点，但我认为这可能是有益的。

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

Answer 5

我会build议几件事情：

• 不要紧，什么“中心”瓷砖，对不对？ 它可能是2，但是如果所有其他的都是1，它会显示1？

• 只有当紧邻的邻居在顶部或侧面有所不同时，它才重要。 如果所有的邻居都是1，angular落是2，那么它会显示1。

• 我可能会预先计算所有可能的邻居组合，创build一个8个索引数组，其中前4个指示顶部/底部邻居的值，第二个指示对angular线：

边缘[N] [E] [S] [W] [NE] [SE] [SW] [NW] =无论偏移到精灵

所以在你的情况下，[2] [2] [1] [1] [2] [2] [1] [1] = 4（第5个精灵）。

在这种情况下，[1] [1] [1] [1]将是1，[2] [2] [2] [2]将是2，其余的将被计算出来。 但是查找特定的瓦片将是微不足道的。