需要基于图块的编辑器的算法

Question

我目前正在为我的基于图块的等距引擎开发一个图块编辑器，并且目前正在研究自动平铺功能。

此时，基于行进方块算法并使用位掩码，我已经能够计算出正确的角资产以放置在图块类型周围。

一段时间以来，我一直在尝试用较低匹配的图块类型包围特定的图块类型。想一想星际争霸编辑器 (Staredit) 将如何自动用较低匹配的资产包围一个图块类型。

来自 staredit 的这张图片请注意，高草比高泥土更有价值：

例如，我有 3 个资产按其各自的高度排序。认为资产 3 代表一堵高墙，而较低的资产代表较低的墙。这些资产将被放入元数据中。 0 表示元数据中的空磁贴。

(3,2,1)

首先，资产 3 将被放置在用户选择的位置的元数据中。

0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,3,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0

然后资产 3 将被资产 2 包围

0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,2,2,2,0,0,0
0,0,0,2,3,2,0,0,0
0,0,0,2,2,2,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0

最终 2 资产将被 1 资产包围。最终结果应该是这样的。

0,0,0,0,0,0,0,0,0
0,0,1,1,1,1,1,0,0
0,0,1,2,2,2,1,0,0
0,0,1,2,3,2,1,0,0
0,0,1,2,2,2,1,0,0
0,0,1,1,1,1,1,0,0
0,0,0,0,0,0,0,0,0

在此过程之后，将执行自动拼贴算法，以便为每个元数据值计算正确的 assets/corners。

另一个例子来自这个 HTML5 应用程序。请注意墙壁是最高资产，其次是草地，然后是泥土，最后是水。每个资产都被一个较低的资产包围。 Marching Squares HTML5 Demo

我研究了洪水填充算法，但它似乎不适用于我要完成的任务。

如果有人对我应该使用什么算法来完成这个任务有解决方案或任何建议，请随时回复这个问题。

我的引擎使用的语言是 Flash As3。

Answer 1

我正在通过图块索引的特定顺序解决这个问题。看看我用的瓷砖套装：

该索引还确定了每个使用的 material 的图块的 rotation/corner。所以从索引你知道它是哪个 material 和哪个 position/rotation 。此信息然后用于自动填充缺失的角（平滑边缘）。参见：

为了更好地感受这一点，请尝试第一个 link 的演示，并在几个地形图块上使用平滑边缘按钮。

该算法有点混乱，因为您需要检测缺少哪个角。例如，在我的地形平滑代码中，它看起来像这样：

int isometric::str_cmp(const AnsiString &a,const AnsiString &b) // wildcard string compare a="01 01" with b="0? 11" for filtering edges in map_random.
    {
    int i; char aa,bb;
    for (i=1;i<=11;i++)
        {
        aa=a[i];
        bb=b[i];
        if ((aa!=bb)&&(aa!=' ')&&(bb!='?')) return 0;
        }
    return 1;
    }
//---------------------------------------------------------------------------
void isometric::str_map_diamond  (AnsiString &s,int x,int y,int z)
    {
    s="000 000 000";
    if (y>0)
        {
        if ((x>    0)&&(map[z][y-1][x-1]==16)) s[ 1]='1';
        if (            map[z][y-1][x  ]==16)  s[ 2]='1';
        if ((x<gxs-1)&&(map[z][y-1][x+1]==16)) s[ 3]='1';
        }
        if ((x>    0)&&(map[z][y  ][x-1]==16)) s[ 5]='1';
        if (            map[z][y  ][x  ]==16)  s[ 6]='1';
        if ((x<gxs-1)&&(map[z][y  ][x+1]==16)) s[ 7]='1';
    if (y<gys-1)
        {
        if ((x>    0)&&(map[z][y+1][x-1]==16)) s[ 9]='1';
        if (            map[z][y+1][x  ]==16)  s[10]='1';
        if ((x<gxs-1)&&(map[z][y+1][x+1]==16)) s[11]='1';
        }
    }
//---------------------------------------------------------------------------
void isometric::str_map_staggered(AnsiString &s,int x,int y,int z)
    {
    s="000 000 000";
    if ((y>   1)     &&(map[z][y-2][x  ]==16)) s[ 1]='1';
    if (y>0)                                                               
        {                                                                  
        if (int (y&1)==0){                                                 
        if ((x>    0)&&(map[z][y-1][x-1]==16)) s[ 5]='1';
        if             (map[z][y-1][x  ]==16)  s[ 2]='1';                  
        }else{                                                             
        if             (map[z][y-1][x  ]==16)  s[ 5]='1';                  
        if ((x<gxs-1)&&(map[z][y-1][x+1]==16)) s[ 2]='1';                  
        }}                                                                 
        if ((x>    0)&&(map[z][y  ][x-1]==16)) s[ 9]='1';                  
        if             (map[z][y  ][x  ]==16)  s[ 6]='1';                  
        if ((x<gxs-1)&&(map[z][y  ][x+1]==16)) s[ 3]='1';                  
    if (y<gys-1)
        {                                                                  
        if (int (y&1)==0){                                                 
        if ((x>    0)&&(map[z][y+1][x-1]==16)) s[10]='1';                  
        if             (map[z][y+1][x  ]==16)  s[ 7]='1';                  
        }else{                                                             
        if             (map[z][y+1][x  ]==16)  s[10]='1';                  
        if ((x<gxs-1)&&(map[z][y+1][x+1]==16)) s[ 7]='1';                  
        }}
    if ((y<gys-2)    &&(map[z][y+2][x  ]==16)) s[11]='1';
    }
//---------------------------------------------------------------------------
void isometric::map_smooth()
    {
    int x,y,z,r;
    AnsiString s;
    map_solid();    // do not work properly on hollow surfaces
    // tile + 8 neighbors -> string "000 000 000"
    void (__closure *_compute_s)(AnsiString &s,int x,int y,int z)=NULL;
    if (map_mode==_isometric_map_mode_diamond  ) _compute_s=str_map_diamond  ;
    if (map_mode==_isometric_map_mode_staggered) _compute_s=str_map_staggered;
    if (_compute_s==NULL) return;
    for (z=gzs-1;z>=0;z--)
        {
        // filter out too small holes
        for (r=1;r;)
         for (r=0,y=0;y<gys;y++)
          for (x=0;x<gxs;x++)
            {
            _compute_s(s,x,y,z);
                 if (str_cmp(s,"??? 101 ???")) { map[z][y][x]=16; s[6]='1'; r=1; }
            else if (str_cmp(s,"?1? ?0? ?1?")) { map[z][y][x]=16; s[6]='1'; r=1; }
            else if (str_cmp(s,"1?? ?0? ??1")) { map[z][y][x]=16; s[6]='1'; r=1; }
            else if (str_cmp(s,"??1 ?0? 1??")) { map[z][y][x]=16; s[6]='1'; r=1; }
            }
        // smooth edges
        for (y=0;y<gys;y++)
         for (x=0;x<gxs;x++)
            {
            _compute_s(s,x,y,z);
                 if (str_cmp(s,"?1? ?01 ???")) map[z][y][x]= 9;
            else if (str_cmp(s,"??? ?01 ?1?")) map[z][y][x]=10;
            else if (str_cmp(s,"??? 10? ?1?")) map[z][y][x]=11;
            else if (str_cmp(s,"?1? 10? ???")) map[z][y][x]=12;
            else if (str_cmp(s,"??? ?01 ???")) map[z][y][x]= 5;
            else if (str_cmp(s,"??? ?0? ?1?")) map[z][y][x]= 6;
            else if (str_cmp(s,"??? 10? ???")) map[z][y][x]= 7;
            else if (str_cmp(s,"?1? ?0? ???")) map[z][y][x]= 8;
            else if (str_cmp(s,"?01 ?00 ???")) map[z][y][x]= 1;
            else if (str_cmp(s,"??? ?00 ?01")) map[z][y][x]= 2;
            else if (str_cmp(s,"??? 00? 10?")) map[z][y][x]= 3;
            else if (str_cmp(s,"10? 00? ???")) map[z][y][x]= 4;
            }
        // fill space below slopes to avoid artifacts
        if (z)
        for (y=0;y<gys;y++)
         for (x=0;x<gxs;x++)
          if (map[z][y][x]>0)
           map[z-1][y][x]=16;
        }
    _redraw=true;
    }
//---------------------------------------------------------------------------

其中 16 是地形砖，{ 0,..,11 } 是旋转和连接砖。有关更多参考，请参阅基于以下内容的旧源代码：

Improving performance of click detection on a staggered column isometric grid

代码简单地将已处理地图位置（瓦片）的 8 个邻居转换为字符串，其中 0 表示空位置，1 表示存在地形块 (16)。然后应用掩码比较来检测每个丢失 corner/join tile.

的情况

您可以对每个支持的 material ...

执行类似的操作

Answer 2

我发现这样做的最佳方法是使用 BFS 或 Dijkstra 自动平衡地图数据。

需要基于图块的编辑器的算法

In need for an algorithm for a tile based editor

algorithm

math

tiles

actionscript-3

isometric