首页 文章

Map 拼贴算法

提问于
浏览 次
150

Map

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

Map 最终看起来像这样（在迷你 Map 视图中） .

enter image description here

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

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

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

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

enter image description here

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

算法

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

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个瓷砖（不使用每个spritesheet上的中心瓷砖 . ）

Sand

Sand2

理想的结果

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

Correct

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

解决方案？

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

javascript html5 algorithm canvas

5 回答

  • 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.

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

    回复于
  • 5

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

    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
    回复于
  • 2

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

    另一方面，正如你所说，手工完成 Map 将导致良好的结果...但我也认为任何修复故障的手动过程也不是一种选择 .

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

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

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

    在瓷砖的角落会有小的不连续性，但与你给出的例子相比，这些不连续性会很小 .

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

    回复于
  • 115

    我正在玩类似的东西，但由于种种原因没有完成;但基本上它需要一个0和1,0的矩阵，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

    回复于
  • 12

    我会建议一些事情：

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

    • 只有角落是什么才重要，当顶部或侧面的近邻存在差异时 . 如果所有直接邻居都是1，并且角落是2，则它将显示1 .

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

    edge [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，其余的将必须计算出来 . 但是对特定图块的查找将是不重要的 .

    回复于

相关问题