Javascript 地图平铺算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/8901987/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Map Tiling Algorithm
提问by Dan Prince
The Map
地图
I'm making a tile based RPG with Javascript, using perlin noise heightmaps, then assigning a tile type based on the height of the noise.
我正在使用 Javascript 制作基于 tile 的 RPG，使用 perlin 噪声高度图，然后根据噪声的高度分配一个 tile 类型。
The maps end up looking something like this (in the minimap view).
地图最终看起来像这样（在小地图视图中）。
I have a fairly simple algorithm which extracts the color value from each pixel on the image and converts it into a integer (0-5) depending on its postion between (0-255) which corresponds to a tile in tile dictionary. This 200x200 array is then passed to the client.
我有一个相当简单的算法，它从图像上的每个像素中提取颜色值，并根据它在 (0-255) 之间的位置将其转换为整数 (0-5)，这对应于平铺字典中的平铺。然后将此 200x200 数组传递给客户端。
The engine then determines the tiles from the values in the array and draws them to the canvas. So, I end up with interesting worlds that have realistic looking features: mountains, seas etc.
然后引擎根据数组中的值确定图块并将它们绘制到画布上。所以，我最终得到了具有逼真特征的有趣世界：山脉、海洋等。
Now the next thing I wanted to do was to apply some kind of blending algorithm that would cause tiles to seamlessly blend into their neighbours, ifthe neighbour is not of the same type. The example map above is what the player sees in their minimap. Onscreen they see a rendered version of the section marked by the white rectangle; where the tiles are rendered with their images rather than as single color pixels.
现在我想做的下一件事是应用某种混合算法，如果邻居的类型不同，它会导致瓦片无缝地混合到他们的邻居中。上面的示例地图是玩家在他们的小地图中看到的。在屏幕上，他们看到由白色矩形标记的部分的渲染版本；瓷砖是用它们的图像而不是单色像素呈现的。
This is an example of what the user would see in the map but it is not the same location as the viewport above shows!
这是用户将在地图中看到的示例，但它与上面显示的视口位置不同！
It is in this view that I want the transitioning to occur.
正是在这种观点下，我希望发生转变。
The Algorithm
算法
I came up with a simple algorithm that would traverse the map within the viewport and render another image over the top of each tile, providing it was next to a tile of different type. (Not changing the map! Just rendering some extra images.) The idea of the algorithm was to profile the current tile's neighbors:
我想出了一个简单的算法，它可以在视口内遍历地图并在每个图块的顶部渲染另一个图像，前提是它位于不同类型的图块旁边。（不改变地图！只是渲染一些额外的图像。）算法的想法是分析当前图块的邻居：
This is an example scenario of what the engine might have to render, with the current tile being the one marked with the X.
这是引擎可能必须渲染的示例场景，当前图块是标有 X 的图块。
A 3x3 array is created and the values around it are read in. So for this example the array would look like.
创建一个 3x3 数组并读入它周围的值。因此对于这个例子，数组看起来像。
[
[1,2,2]
[1,2,2]
[1,1,2]
];
My idea was then to work out a series of cases for the possible tile configurations. On a very simple level:
我的想法是为可能的瓷砖配置制定一系列案例。在一个非常简单的层面上：
if(profile[0][1] != profile[1][1]){
//draw a tile which is half sand and half transparent
//Over the current tile -> profile[1][1]
...
}
Which gives this result:
这给出了这个结果：
Which works as a transition from [0][1]to [1][1], but not from [1][1]to [2][1], where a hard edge remains. So I figured that in that instance a corner tile would have to be used. I created two 3x3 sprite sheets that I thought would hold all the possible combinations of tiles that could be needed. Then I replicated this for all of the tiles that there are in the game (The white areas are transparent). This ends up being 16 tiles for each type of tile (The center tiles on each spritesheet are not used.)
它作为从[0][1]到的过渡[1][1]，而不是从[1][1]到的过渡[2][1]，其中仍然存在硬边。所以我想在那种情况下必须使用角砖。我创建了两个 3x3 精灵表，我认为它们可以容纳可能需要的所有可能的瓷砖组合。然后我为游戏中的所有图块复制了这个（白色区域是透明的）。对于每种类型的图块，最终得到 16 个图块（不使用每个精灵表上的中心图块。）
The Ideal Outcome
理想的结果
So, with these new tiles and the correct algorithm, the example section would look like this:
因此，使用这些新图块和正确的算法，示例部分将如下所示：
Every attempt I have made has failed though, there is always some flaw in the algorithm and the patterns end up strange. I can't seem to get all the cases right and overall it seems like a poor way of doing it.
我所做的每一次尝试都失败了，算法中总是存在一些缺陷，并且模式最终变得奇怪。我似乎无法正确处理所有案例，总的来说，这似乎是一种糟糕的做法。
A Solution?
一个办法？
So, if anyone could provide an alternative solution as to how I could create this effect, or what direction to go for writing the profiling algorithm, then I would be very grateful!
因此，如果有人可以提供有关如何创建这种效果的替代解决方案，或者编写分析算法的方向，那么我将非常感激！
采纳答案by user1884905
The basic idea of this algorithm is to use a pre-processing step to find all edges and then select the correct smoothing tile according to the shape of the edge.
该算法的基本思想是使用预处理步骤找到所有边缘，然后根据边缘的形状选择正确的平滑瓦片。
The first step would be to find all edges. In the example below the edge tilesmarked with an X are all green tiles with a tan tile as one or more of their eight neighbouring tiles. With different types of terrain this condition could translate to a tile being an edge tile if it has neighbours of lower terrain-number.
第一步是找到所有边。在下面的示例中，标有 X的边缘瓷砖都是绿色瓷砖，其中一个或多个棕褐色瓷砖作为其八个相邻瓷砖中的一个或多个。对于不同类型的地形，如果它具有较低地形编号的邻居，则这种情况可能会转化为边缘瓷砖。
Once all edge tiles are detected the next thing to do is to select the right smoothing tile for each edge tile. Here is my representation of your smoothing tiles.
一旦检测到所有边缘图块，接下来要做的就是为每个边缘图块选择正确的平滑图块。这是我对您的平滑瓷砖的表示。
Note that there are actually not that many different types of tiles. We need the eight outer tiles from one of the 3x3 squares but only the four corner squares from the other since the straight-edge tiles are already found in the first square. This means that there in total are 12 different cases we must distinguish between.
请注意，实际上没有那么多不同类型的瓷砖。我们需要来自 3x3 方格中的一个方格的 8 个外部方格，但只需要来自另一个方格的四个角方格，因为在第一个方格中已经找到了直边方格。这意味着我们必须区分总共 12 种不同的情况。
Now, looking at one edge tile we can determine which way the boundary turns by looking at its four closest neighbour tiles. Marking an edge tile with X just as above we have the following six different cases.
现在，查看一个边缘瓦片，我们可以通过查看其四个最近的相邻瓦片来确定边界转向的方向。如上所述用 X 标记边缘瓦片，我们有以下六种不同的情况。
These cases are used to determine the corresponding smoothing tile and we can number the smoothing tiles accordingly.
这些情况用于确定相应的平滑图块，我们可以相应地对平滑图块进行编号。
There is still a choice of a or b for each case. This depends on which side the grass is on. One way to determine this could be to keep track of the orientation of the boundary but probably the simplest way to do it is to pick one tile next to the edge and see what colour it has. The image below shows the two cases 5a) and 5b) which can be distinguished between by for example checking the colour of the top right tile.
对于每种情况，仍然可以选择 a 或 b。这取决于草在哪一边。确定这一点的一种方法可能是跟踪边界的方向，但最简单的方法可能是选择边缘旁边的一块瓷砖并查看它的颜色。下图显示了两种情况 5a) 和 5b)，例如可以通过检查右上角瓷砖的颜色来区分它们。
The final enumeration for the original example would then look like this.
原始示例的最终枚举将如下所示。
And after selecting the corresponding edge tile the border would look something like this.
选择相应的边缘平铺后，边框看起来像这样。
As a final note I might say that this would work as long as the boundary is somewhat regular. More precisely, edge tiles that do not have exactly two edge tiles as their neighbours will have to be treated separately. This will occur for edge tiles on the edge of the map which will have a single edge neighbour and for very narrow pieces of terrain where the number of neighbouring edge tiles could be three or even four.
最后，我可能会说，只要边界有点规则，这就会起作用。更准确地说，没有正好有两个边缘图块作为它们的邻居的边缘图块将不得不单独处理。这将发生在地图边缘的边缘瓦片（将有一个边缘邻居）和非常狭窄的地形，其中相邻边缘瓦片的数量可能是三个甚至四个。
回答by robert king
The following square represents a metal plate. There is a "heat vent" by the top right corner. We can see how as the temperature of this point remains constant, the metal plate converges to a constant temperature at each point, being naturally hotter near the top:
下面的方块代表金属板。右上角有一个“散热孔”。我们可以看到当这个点的温度保持恒定时，金属板在每个点都收敛到一个恒定的温度，在顶部附近自然更热：
The problem of finding the temperature at each point can be solved as a "Boundary value problem". However the simplest way to work out the heat at each point is to model the plate as a grid. We know the points on the grid at constant temperature. We set the temperature of all unknown points to be room temperature (as if the vent had only just been turned on). We then let the heat spread through the plate until we reach convergence. This is done by iteration: we iterate through each (i,j) point. We set point(i,j) = (point(i+1, j)+point(i-1,j)+point(i, j+1)+point(i,j-1))/4 [unless point(i,j) has a heat vent of constant temperature]
找到每个点的温度的问题可以作为“边界值问题”来解决。然而，计算每个点的热量的最简单方法是将板建模为网格。我们知道恒温时网格上的点。我们将所有未知点的温度设置为室温（就好像通风口刚刚打开一样）。然后我们让热量通过板传播，直到我们达到收敛。这是通过迭代完成的：我们遍历每个 (i,j) 点。我们设置 point(i,j) = (point(i+1, j)+point(i-1,j)+point(i, j+1)+point(i,j-1))/4 [除非点(i,j)有一个恒温的散热口]
If you apply this to your problem, it is very similar, just average colors instead of temperatures. You would probably need about 5 iterations. I suggest using a 400x400 grid. Thats 400x400x5 = less than 1 million iterations which will be fast. If you only use 5 iterations you probably won't need to worry about holding any points constant color, as they wont shift too much from their original (in fact only points within distance 5 from the color can be effected by the color). Pseudo code:
如果你把这个应用到你的问题上，它是非常相似的，只是平均颜色而不是温度。您可能需要大约 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
回答by perfectionist
Ok, so first thoughts are that automating a perfect solution to the problem requires some rather meaty interpolation maths. Based on the fact that you mention pre-rendered tile images, I assume that the full interpolation solution is not warranted here.
好的，所以第一个想法是自动化一个完美的问题解决方案需要一些相当丰富的插值数学。基于您提到预渲染的平铺图像这一事实，我认为此处不保证完整的插值解决方案。
On the other hand as you said, finishing off the map by hand will lead to a good result... but I also assume that any manual process to fix glitches is also not an option.
另一方面，正如您所说，手动完成地图会带来不错的结果……但我也认为修复故障的任何手动过程也不是一种选择。
Here's a simple algorithm that does not give a perfect result, but that is very rewarding based on the low effort it takes.
这是一个简单的算法，它不会给出完美的结果，但基于它所花费的努力很少，这是非常有益的。
Instead of trying to blend EVERY edge tile, (which means that you need to either know the result of blending the adjacent tiles first - interpolation, or you need to refine the whole map several times and can't rely on pre-generated tiles) why not blend tiles in a alternating checker-board pattern?
而不是尝试混合每个边缘图块，（这意味着您需要先知道混合相邻图块的结果 - 插值，或者您需要多次优化整个地图并且不能依赖预先生成的图块）为什么不以交替的棋盘格图案混合瓷砖呢？
[1] [*] [2]
[*] [1] [*]
[1] [*] [2]
I.e. only blending the tiles starred in the matrix above?
即只混合上面矩阵中加星标的瓷砖？
Assuming that the only permitted steps in value are one-at-a-time, you only have a few tiles to design...
假设值中唯一允许的步骤是一次一个，那么您只有几个图块可以设计......
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]
There will be 16 patterns in total. If you take advantage of rotational and reflectional symmetry there will be even fewer.
总共将有16个模式。如果您利用旋转和反射对称性，则更少。
'A' would be a plain [1] style tile. 'D' would be a diagonal.
'A' 将是一个普通的 [1] 风格的瓷砖。'D' 将是对角线。
There will be small discontinuities at the corners of the tiles, but these will be minor compared to the example you gave.
瓷砖的角落会有小的不连续性，但与您提供的示例相比，这些将是次要的。
If I can I'll update this post with images later.
如果可以的话，我稍后会用图片更新这篇文章。
回答by Ben
I was playing around with something similar to this, it wasn't finished off for a number of reasons; but basically it would take a matrix of 0 and 1, 0 being the ground and 1 being a wall for a maze generator application in Flash. Since AS3 is similar to JavaScript it wouldn't be difficult to rewrite in JS.
我正在玩类似的东西，由于多种原因它没有完成；但基本上它需要一个由 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;
}
Basically this checks every tile around it going from left to right, top to bottom and assumes that edge tiles are always 1. I've also taken the liberty of exporting the images as a file to use as a key:
基本上，这会从左到右、从上到下检查它周围的每个图块，并假设边缘图块始终为 1。我还冒昧地将图像导出为文件以用作密钥：
This is incomplete and probably a hacky way to achieve this, but I thought it might be of some benefit.
这是不完整的，可能是实现这一目标的一种黑客方法，但我认为这可能会有一些好处。
Edit: Screenshot of the result of that code.
编辑：该代码结果的屏幕截图。
回答by elijah
I would suggest a few things:
我建议几点：
it doesn't matter what the "center" tile is, right? it could be 2, but if all the others are 1, it would show 1?
it only matters what the corners are, when there is a difference in the immediate neighbors to the top or side. If all the immediate neighbors are 1, and a corner is 2, it would show 1.
I would probably precalculate all the possible combinations of neighbors, creating an 8 index array with the first four indicating the values of the top/bottom neighbors, and the second indicating the diagonals:
“中心”瓷砖是什么并不重要，对吧？它可能是 2，但如果所有其他都是 1，它会显示 1？
当顶部或侧面的直接邻居存在差异时，只有角落是什么才重要。如果所有的直接邻居都是 1，并且一个角落是 2，那么它会显示 1。
我可能会预先计算所有可能的邻居组合，创建一个 8 索引数组，前四个表示顶部/底部邻居的值，第二个表示对角线：
edges[N][E][S][W][NE][SE][SW][NW] = whatever offset into sprite
edge[N][E][S][W][NE][SE][SW][NW] = 精灵的任何偏移
so in your case, [2][2][1][1][2][2][1][1] = 4 (the 5th sprite).
所以在你的情况下， [2][2][1][1][2][2][1][1] = 4（第 5 个精灵）。
in this case, [1][1][1][1] would be 1, [2][2][2][2] would be 2, and the rest would have to be worked out. But the lookup for a particular tile would be trivial.
在这种情况下，[1][1][1][1] 将是 1，[2][2][2][2] 将是 2，其余的必须计算出来。但是查找特定磁贴将是微不足道的。
