洪水填充和scanLine算法是基于线的洪水，但是我想要基于平方的洪水。

Question

我有一个填充算法(洪水填筑)来填充一个24x24矩阵，如下所示(矩阵在这里是24x24，但在生产中要大得多)：

Main code:

  var cspots,    // number of spots per group
      gArr=[];   // global array which contains all group spots

  var tArr = new Array(gArr.length);   // touch array for flood-fill
  for(var spot in inArr) {
    for (var tspot in tArr)  // initialise touch array 
      tArr[tspot]=0;
    for(gspot in gArr) {     // find lowest open y*24+x ordinal
      if (gArr[gspot][0] == 0) 
        break;
      tArr[gspot]=1;
    }
    cspots = inArr[spot].GD;
    userFill(gArr[gspot][1],gArr[gspot][2],inArr[spot].KY,tArr);
  }

function userFill(x,y,elem,tArr) {
  var gord, qt=0;
  if (!cspots) return;
  if ((x >= 0) && (x <= 23) && (y >= 0) && (y <= 23)) {
    gord = y*24 + x;
    if (gArr[gord][0] != 0 || tArr[gord]) 
      return;
    gArr[gord][0] = elem;
    tArr[gord] = 1;
    --cspots;
    userFill(x+1,y,elem,tArr);
    userFill(x-1,y,elem,tArr);
    // before the y-change we need to see if there are any open spots on this line
    for(gord=y*24; gord<=(y*24)+23; gord++) {
      if (gArr[gord][0] == 0) {
        qt=1;
        break;
      }
    }
    if (!qt) {
      userFill(x,y+1,elem,tArr);
      userFill(x,y-1,elem,tArr);
    }
  }
};

这是一个标准的洪水填充递归算法(附带一个用于标记任何触摸的触摸数组)，在更改y-值之前，我将检查在每个x平面上是否将所有x-值设置为非零。这产生了这样一个矩阵：

问题是，它看起来不太好(国际海事组织)，因为大部分地区是沿x平面线。我想要的是每个不同的群体区域尽可能多地以正方形的形式存在。类似于此示例(使用字母表示不同的组区域)：

V V V W W W W X X X X X
V V Y W W W W X X X X Z
Y Y Y W W W W Z Z Z Z Z
Y Y   W W W W Z Z Z Z Z
... and so on

因此，我将userFill修改为查看一个boxX变量，它只是每个区域的(sqrt )+1，希望我可以使用它来限制每个区域的形状。还有一个preX变量来存储每个组区域的锚点，所以我知道添加了多少个点。以下是新的userFill：

Main code:

  var tArr = new Array(gArr.length);
  for(var spot in inArr) {
    for (var tspot in tArr)  // initialise touch array 
      tArr[tspot]=0;
    for(gspot in gArr) {     // find lowest open y*24+x ordinal
      if (gArr[gspot][0] == 0) 
        break;
      tArr[gspot]=1;
    }
    cspots = inArr[spot].GD;
    boxX = Math.ceil(Math.sqrt(cspots));
    preX = gArr[gspot][1];
    userFill(gArr[gspot][1],gArr[gspot][2],inArr[spot].KY,tArr);
  }

function userFill(x,y,elem,tArr) {
  var gord, qt=0;
  if (!cspots) return;
  if ((x >= 0) && (x <= 23) && (y >= 0) && (y <= 23)) {
    gord = y*24 + x;
    if (gArr[gord][0] != 0 || tArr[gord]) 
      return;
    gArr[gord][0] = elem;
    tArr[gord] = 1;
    --cspots;
    // before the x-change we need to see if we have done a boxX number of changes to maintain square-shape
    if (Math.abs(x-preX) == boxX) {
      userFill(preX,y+1,elem,tArr);
      userFill(preX,y-1,elem,tArr);
      return;
    }
    userFill(x+1,y,elem,tArr);
    userFill(x-1,y,elem,tArr);
    // before the y-change we need to see if there are any open spots on this line
    for(gord=y*24; gord<=(y*24)+boxX; gord++) {
      if (gArr[gord][0] == 0) {
        qt=1;
        break;
      }
    }
    if (!qt) {
      userFill(x,y+1,elem,tArr);
      userFill(x,y-1,elem,tArr);
    }
  }
};

唯一的区别是，我检查是否添加了boxX点，然后递归调用userFill来更改y平面。

这是输出结果，看起来更好，因为大多数区域都是方形的，但很明显，它需要工作(缺少大部分的斑点，浅蓝的群区域形状很奇怪，一点也不像方形)，但是我想知道是否有一个更好的算法可以将洪水从基于线的填充变为基于正方形的填充。

更新：

我想我想出了一个算法。从矩阵中最低点的一个点开始。然后，在这个点周围加上一个周围的点的平方，然后再加上一个较大的正方形，直到点耗尽为止。所以：

0     (first spot in matrix (0,0))

1 1
0 1   (add 3 spots to make it a 2x2 square)

2 2 2
1 1 2
0 1 2   (add 5 spots to make it a 3x3 square)

and so on

这是可以做到的，即使一些方块是画出来的，你是在其他方块的基础上建造的。例如(X和Y是预先存在的正方形)：

  X
X X Y Y
X X Y Y

在矩阵(0,2)中的最低点中放置新群的第一个点

0 X
X X Y Y
X X Y Y

尝试并建立一级广场(一个'X‘将阻塞一个1级点)

1 1
0 X
X X Y Y
X X Y Y

试着建造二层广场

2 2 2
1 1 2
0 X 2
X X Y Y
X X Y Y

第三级

3 3 3 3
2 2 2 3
1 1 2 3
0 X 2 3
X X Y Y
X X Y Y

第4级

4 4 4 4 4
3 3 3 3 4
2 2 2 3 4
1 1 2 3 4
0 X 2 3 4
X X Y Y
X X Y Y

。。诸若此类。我现在只需要找到实现。

更新2

我已经创建了宽度优先算法，如下所建议的，它工作得更好。这是代码和所生成的图像(这对于10个组中的每个组来说都是非常方形的)。

function bfsFill(x,y,elem,tArr) {
  var gord, i=0, pt, queue=[], cnt=0;
  if (!cspots) return;
  if (isOutOfBounds(x,y)) return;
  queue.push([x,y]);
  while(cspots>0 && queue.length>0) {
    pt = queue.shift(); 
    gord = pt[1]*24 + pt[0];
    tArr[gord] = 1;
    gArr[gord][0] = elem;
    --cspots;
    var rArr = neighbours(pt);
    async.eachSeries(rArr, function(el, cb2) {
      if (!isOutOfBounds(el[0],el[1])) {
        gord = el[1]*24 + el[0];
        if (tArr[gord] == 0 && gArr[gord][0] == 0) {
          for(var qi in queue) {
            if (queue[qi][0] == el[0] && queue[qi][1]==el[1]) {
              cb2();
              return;
            }
          }
          queue.push(el);
        }
      }
      cb2();
    }, function(err) {
    });
  }
};

制作的图像文件：

Answer 1

在发布这个答案时，您的代码看起来有点像这样(下面的代码被很快地拼凑在一起，可能有用，也可能不起作用)：

function fill ( x, y, touched, elem ) {
    if ( count <= 0 ) return;
    if ( isOutOfBounds(x,y) ) return;

    const idx = y*24 + x;

    if ( gArr[idx][0] != 0 || touched[idx] ) return;

    touched[idx] = true;
    gArr[idx][0] = elem;
    count--;

    fill(x+1, y, touched, elem);
    fill(x-1, y, touched, elem);
    fill(x, y+1, touched, elem);
    fill(x, y-1, touched, elem);
}

这种写作方式的问题在于，在考虑其他3条路径之前，它总是选择右边的路径。这导致程序只向右移动，从而耗尽了它的点位。这样的搜索称为深度优先搜索(DFS)。

相反，如果我们能从一个点开始移动我们的网格，而不是盲目地遵循我们找到的第一条路径，那就太好了。存在一种著名的算法，它被称为广度优先搜索(BFS)。它大致如下(再一次，这段代码可能无法工作，即使您实现了缺失的部分)：

function fill ( starting_point, count, elem ) {
    if ( count <= 0 ) return;
    if ( isOutOfBounds(starting_point) ) return;

    let touched = Array(gArr.length).fill(false);
    let queue = [starting_point];

    while ( count > 0 && queue.length > 0 ) {
        let p = queue.shift();

        touched[p.idx] = true;
        gArr[p.idx][0] = elem;

        for ( let neighbor of neighbors(p) ) {
            if ( !isOutOfBounds( neighbor ) ) {
                if ( !touched[ neigbor.idx ] && gArr[ neigbor.idx ][0] == 0 ){
                    touched[ neighbor.idx ] = true;
                    queue.push(neighbor);
                }
            }
        }
    }
}

这是做的是，它把点绘制在一个队列中，然后按照它们被放入的顺序来查看它们。

当然，添加到队列中的第一组点是洪水开始点的邻居，然后是这些点的邻居，等等。有效地建立了一个不断扩大的正方形。

希望这能有所帮助！