4

I am currently developing an tile editor for my tile based isometric engine and am currently working on the auto-tiling features.

At this point, based on the marching squares algorithm and using an bitmask, I have been able to calculate the correct corner assets to place around a tile type.

For some time I have been attempting to surround a specific tile type with an lower matching tile type. Think how the Starcraft editor(Staredit) would automatically surround an tile type with an lower matching asset.

Notice on this image from staredit how high grass is a higher asset then high dirt:

1

For example I have 3 assets ordered by their respective height. Think as the asset 3 represents a high wall, and the lower assets would represent lower walls. These assets would be placed into the metadata. 0 would represent an empty tile within the metadata.

(3,2,1)

First the 3 asset would be placed in the metadata on the location selected by the user. 

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

Then the 3 asset would be surrounded by the 2 asset

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

Finally the 2 asset would be surrounded by the 1 asset. The end result should look something like this.

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

After this process the autotiling algorithm would be executed in order to calculate the correct assets/corners for each metadata value.

Another example of this would be from this HTML5 application. Notice how the walls are the highest assets, followed by grass, then dirt and finally water. Each asset is surrounded by an lower asset. Marching Squares HTML5 Demo

I have looked into the flood fill algorithm but it seems that it does not apply to what I am trying to accomplish.

If anyone has a solution or any advice on what algorithm I should use in order to accomplish this task, please feel free to respond to this question.

The language I am using for my engine is Flash As3.

Spektre
  • 49,595
  • 11
  • 110
  • 380
Dan Medinsky
  • 51
  • 6

2 Answers2

1

I am solving this problem by specific order of tile indexes. Take a look at the tile set I use:

The index also determines the rotation/corner of the tile for each used material. So from index you know which material it is and which position/rotation it is. This info is then used for auto filling of missing corners (smoothing edges). See:

To get better feeling of this try the demo from the first link and play with the smooth edges button on few terrain tiles.

The algorithm is a bit confusing as you need to detect which corner is missing. For example In my code for terrain smooth it looks like this:

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;
    }
//---------------------------------------------------------------------------

Where 16 is the terrain brick and { 0,..,11 } are the rotations and join bricks. For more refference here is oldersource code this was based on:

The code simply converts 8 neighbors of processed map position (tile) into string where 0 means empty position and 1 means terrain brick (16) is present. Then masked comparison is applied to detect each case of missing corner/join tile.

You can do this similarly for each supported material ...

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
0

The best way I have found of doing this is to use BFS or Dijkstra to automatically balance the map data.

Dan Medinsky
  • 51
  • 6