地图拼接算法

2020/11/08 09:23 · javascript ·  · 0评论

地图

我正在使用Perlin噪声高度图使用Javascript创建基于图块的RPG,然后根据噪声的高度分配图块类型。

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

在此处输入图片说明

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

然后,引擎根据数组中的值确定切片并将其绘制到画布上。因此,我最终得到了具有逼真的外观的有趣世界:山脉,海洋等。

现在,我想做的下一件事是应用某种混合算法,如果邻居不是同一类型的这将导致图块无缝地融合到其邻居中上面的示例地图是玩家在小地图中看到的。在屏幕上,他们看到了用白色矩形标记的部分的渲染版本。其中图块是使用其图像而不是单色像素渲染的。

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

在此处输入图片说明

我希望这种转变能够发生。

算法

我想出了一个简单的算法,该算法可以遍历视口中的地图,并在每个图块的顶部渲染另一个图像,前提是该图块位于不同类型的图块旁边。(不更改地图!仅渲染一些额外的图像。)该算法的想法是对当前图块的邻居进行剖析:

平铺配置文件的示例

这是引擎可能必须渲染的示例场景,当前图块是标有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的Sprite工作表,我认为这些工作表可以容纳所有可能需要的图块组合。然后,我为游戏中的所有图块复制了此图(白色区域是透明的)。每种类型的图块最终为16个图块(不使用每个Spritesheet上的中心图块。)

砂沙2

理想结果

因此,有了这些新的图块和正确的算法,示例部分将如下所示:

正确

但是我所做的每一次尝试都失败了,算法中总是存在一些缺陷,并且模式最终变得很奇怪。我似乎无法正确处理所有情况,总的来说,这似乎是一种糟糕的做法。

一个办法?

因此,如果任何人都可以提供关于我如何创建此效果的替代解决方案,或者提供什么方向来编写性能分析算法,那么我将不胜感激!

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

第一步是找到所有边缘。在下面的示例中,标有X边缘图块都是绿色图块,其棕褐色图块是其八个相邻图块中的一个或多个。对于不同类型的地形,如果其邻居具有较低的地形编号,则此条件可能会转换为边块。

边砖。

一旦检测到所有边缘瓦片,下一步就是为每个边缘瓦片选择正确的平滑瓦片。这是我对您的平滑砖的表示。

平滑瓷砖。

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

现在,查看一个边缘图块,我们可以通过查看边界的四个最邻近的图块来确定边界的旋转方式。像上面那样用X标记边缘图块,我们有以下六种不同情况。

六例。

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

带有数字的平滑的瓷砖。

每种情况下仍然可以选择a或b。这取决于草在哪一侧。确定该位置的一种方法可能是跟踪边界的方向,但最简单的方法可能是在边缘旁边拾取一个图块并查看其颜色。下图显示了两种情况5a)和5b),可以通过例如检查右上图块的颜色来区分这两种情况。

选择5a或5b。

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

最终枚举。

在选择了相应的边块后,边框看起来像这样。

最后结果。

最后一点,我可能会说,只要边界有些规则,这将起作用。更精确地,与它们的邻居没有完全相同的两个边缘瓦片的边缘瓦片将必须被分别对待。这将发生在地图边缘上的边缘图块(具有单个边缘邻居)和非常狭窄的地形区域中,其中相邻边缘图块的数量可能是三个甚至四个。

下一个正方形代表金属板。右上角有一个“散热孔”。我们可以看到随着该点的温度保持恒定,金属板在每个点处收敛到恒定温度,在顶部附近自然变热:

加热板

找到每个点的温度的问题可以作为“边值问题”解决。但是,计算每个点热量的最简单方法是将板建模为网格。我们知道恒温下网格上的点。我们将所有未知点的温度设置为室温(就好像通风口刚刚打开一样)。然后,我们让热量散布到整个板上,直到达到收敛为止。这是通过迭代完成的:我们迭代每个(i,j)点。我们设置point(i,j)=(point(i + 1,j)+ point(i-1,j)+ point(i,j + 1)+ point(i,j-1))/ 4 [除非[i,j]点有一个恒温的散热孔]

如果将其应用于问题,则非常相似,只是平均颜色而不是温度。您可能需要大约5次迭代。我建议使用400x400的网格。多数民众赞成在400x400x5 =少于一百万次迭代,这将是快速的。如果仅使用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

好的,所以首先想到的是,要自动完美地解决问题,需要一些相当复杂的插值数学。基于您提到预渲染的图块图像这一事实,我认为此处不保证使用完整的插值解决方案。

另一方面,正如您所说,手动完成地图操作会带来不错的结果……但是我还认为,解决故障的任何手动过程也是不可行的。

这是一个无法给出完美结果的简单算法,但是基于它的低投入,这是非常有益的。

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

[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”将是对角线。

磁贴的角部会出现一些小的不连续点,但是与您给出的示例相比,这些不连续点会很小。

如果可以的话,我稍后会用图片更新此帖子。

我当时正在玩类似的游戏,但由于多种原因并没有完成。但基本上,对于Flash中的迷宫生成器应用,它将采用0和1的矩阵,0是地面,1是墙。由于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。我也很自由地将图像导出为文件用作键:

墙砖

这是不完整的,可能是实现这一目标的一个很棘手的方法,但是我认为这可能会有所帮助。

编辑:该代码的结果的屏幕快照。

产生的结果

我建议一些事情:

  • 没关系,“中心”磁贴是什么,对吗?可能是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,其余的将必须计算出来。但是查找特定图块将是微不足道的。

本文地址:http://javascript.askforanswer.com/ditupinjiesuanfa.html
文章标签: ,   ,   ,  
版权声明:本文为原创文章,版权归 javascript 所有,欢迎分享本文,转载请保留出处!

文件下载

老薛主机终身7折优惠码boke112

上一篇:
下一篇:

评论已关闭!