algorithm - 有没有一种算法可以随机填充这样的矩阵？

Question

考虑一个 r 行大小和 c 列大小的矩阵例如，给定 r = 19 和 c =11，我们将有一个包含 209 个元素的矩阵。所有元素的赋值为 0。因此我们有一个包含 0 的大矩阵。

给定以下 6 个“区域”Area1:31个元素Area2:35个元素Area3:35个元素Area4:37个元素Area5:32个元素Area6:39个元素

将所有面积元素加起来为 209，因此它们填满了整个矩阵。

是否有一种算法可以用这些区域中的每一个填充矩阵并将元素的值设置为区域名称？我需要的实际上不是设置部分，而是找到一个元素及其附近的元素的算法部分。

矩阵区域应该看起来像...比方说世界地图上的国家领土。所以我们不能在矩阵的左边有“area1”元素，然后在右边有其他区域。这些区域应该被压缩，具有接管矩阵元素时形成的随机“形状”。

基本上，为了更容易理解，我把它想象成在给定大小 (209) 的 map 上创建给定大小的随机区域。

有人可以推荐任何现有算法吗？或者任何方法？

编辑:6 个区域(基于给定的示例)填满了整个空间。不应留下任何背景元素(0 值元素)。我们示例中的 6 个区域应完全填充 209 个元素。

Answer 1

为了保持一些随机性，我这样处理这个问题:

1. 为每个领土生成种子起点

   简单地计算每个地区的随机起点，并限制任何 2 个起点之间必须至少有一些定义的最小距离。这将提供一些增长空间，因此结果看起来更好。

2. 尽你所能种植每颗种子

   简单地迭代扩大每个区域，直到没有间隙(忽略所需的区域大小)

3. 更正尺寸

   所以简单地占领领土i=1并从任何邻近地区放大/缩小它们j>i .然后处理i=2 ...完成后按降序执行相同的操作，因此占据领土i=n并从任何邻居放大/缩小j<i .

   循环整个过程，直到领土具有正确的大小

4. 验证

   bullet #3 可以将一些领土划分为非结果区域，我怀疑这是不受欢迎的。因此，检测到这一点，如果案件再次产生这整个事情。

   要仅针对每个区域进行检测，请找到其第一个有效单元格并进行洪水填充计算该领土有多大。如果大小不匹配，领土已经划分，你应该重新生成。

   如果所有地区的大小都匹配，那么 map 就是相关的，你就完成了

此处预览#1、#2、#3:

表格标题中的数字是领土 actual size - wanted size第一个数字是差距然后进入领土1,2,3 ...

还有我的 C++ 实现:

//---------------------------------------------------------------------------
// generator properties
const int n=7;          // teritories+1
const int mx=19;        // map size
const int my=11;
const int siz[n]={ 0,31,35,35,37,32,39 };   // teritory sizes (first is bordrer)
const int mindist=5;    // min distance between teritory seed points
      int map[mx][my];  // map 0 means no teritory else it is teritory ID
// rendering properties
const int grid=16;      // grid size [pixels]
const DWORD col[n]=     // teritory color table
    {
    0x00000000,         // border (unused)
    0x00FF0000,         // territory 1
    0x0000FF00,         // territory 2
    0x000000FF,         // territory 3
    0x00FFFF00,         // territory 4
    0x0000FFFF,         // territory 5
    0x00FF00FF,         // territory 6
    };
//---------------------------------------------------------------------------
void map_generate()
    {
    int x,y,xx,yy,i,j,e;
    int cnt[n];     // generated teritory size
    int seedx[n];   // start position for teritory
    int seedy[n];

//  AnsiString s="";
//  s+=AnsiString().sprintf("Seed: %X |",RandSeed);

    for (;;)
        {
        // clear map
        cnt[0]=mx*my;
        for (x=0;x<mx;x++)
         for (y=0;y<my;y++)
          map[x][y]=0;
        // start position
        for (i=1;i<n;)
            {
            // ranom position
            seedx[i]=Random(mx);
            seedy[i]=Random(my);
            // find closest seed point x = distance to it
            for (x=mx+my,j=1;j<i;j++)
                {
                y=abs(seedx[i]-seedx[j])+abs(seedy[i]-seedy[j]);
                if (x>y) x=y;
                }
            // if OK use as seed point else repeat the whole thing again...
            if (x>mindist)
                {
                map[seedx[i]][seedy[i]]=i;
                cnt[i]=1; cnt[0]--; i++;
                }
            }

        // un bounded growth fill (can exceeding area)
        for (e=1;e;)
            {
            e=0;
            for (x=   1;x<mx;x++) for (y=0;y<my;y++) { i=map[x][y]; if (i>0){ x--; if (map[x][y]==0) { map[x][y]=i; cnt[i]++; cnt[0]--; e=1; } x++; }}
            for (x=mx-2;x>=0;x--) for (y=0;y<my;y++) { i=map[x][y]; if (i>0){ x++; if (map[x][y]==0) { map[x][y]=i; cnt[i]++; cnt[0]--; e=1; } x--; }}
            for (x=0;x<mx;x++) for (y=   1;y<my;y++) { i=map[x][y]; if (i>0){ y--; if (map[x][y]==0) { map[x][y]=i; cnt[i]++; cnt[0]--; e=1; } y++; }}
            for (x=0;x<mx;x++) for (y=my-2;y>=0;y--) { i=map[x][y]; if (i>0){ y++; if (map[x][y]==0) { map[x][y]=i; cnt[i]++; cnt[0]--; e=1; } y--; }}
            }

        // correct inequalities cnt[] vs. siz[]
        for (;;)
            {
            // stop if all counts are matching
            for (i=1;i<n;i++) if (cnt[i]!=siz[i]) { i=-1; break; } if (i>=0) break;
            // growth i from any neighbor j>i
            for (i=1;i<n;i++)
             for (e=1;(e)&&(cnt[i]<siz[i]);)
                {
                e=0;
                for (x=   1;x<mx;x++) for (y=0;y<my;y++) if ((i==map[x][y])&&(cnt[i]<siz[i])){ x--; j=map[x][y]; if ((i<j)&&(cnt[j]>1)){ map[x][y]=i; cnt[i]++; cnt[j]--; e=1; } x++; }
                for (x=mx-2;x>=0;x--) for (y=0;y<my;y++) if ((i==map[x][y])&&(cnt[i]<siz[i])){ x++; j=map[x][y]; if ((i<j)&&(cnt[j]>1)){ map[x][y]=i; cnt[i]++; cnt[j]--; e=1; } x--; }
                for (x=0;x<mx;x++) for (y=   1;y<my;y++) if ((i==map[x][y])&&(cnt[i]<siz[i])){ y--; j=map[x][y]; if ((i<j)&&(cnt[j]>1)){ map[x][y]=i; cnt[i]++; cnt[j]--; e=1; } y++; }
                for (x=0;x<mx;x++) for (y=my-2;y>=0;y--) if ((i==map[x][y])&&(cnt[i]<siz[i])){ y++; j=map[x][y]; if ((i<j)&&(cnt[j]>1)){ map[x][y]=i; cnt[i]++; cnt[j]--; e=1; } y--; }
                }
            // shrink i from any neighbor j>i
            for (i=1;i<n;i++)
             for (e=1;(e)&&(cnt[i]>siz[i]);)
                {
                e=0;
                for (x=   1;x<mx;x++) for (y=0;y<my;y++) if ((i==map[x][y])&&(cnt[i]>siz[i])){ x--; j=map[x][y]; if (i<j)              { map[x+1][y]=j; cnt[j]++; cnt[i]--; e=1; } x++; }
                for (x=mx-2;x>=0;x--) for (y=0;y<my;y++) if ((i==map[x][y])&&(cnt[i]>siz[i])){ x++; j=map[x][y]; if (i<j)              { map[x-1][y]=j; cnt[j]++; cnt[i]--; e=1; } x--; }
                for (x=0;x<mx;x++) for (y=   1;y<my;y++) if ((i==map[x][y])&&(cnt[i]>siz[i])){ y--; j=map[x][y]; if (i<j)              { map[x][y+1]=j; cnt[j]++; cnt[i]--; e=1; } y++; }
                for (x=0;x<mx;x++) for (y=my-2;y>=0;y--) if ((i==map[x][y])&&(cnt[i]>siz[i])){ y++; j=map[x][y]; if (i<j)              { map[x][y-1]=j; cnt[j]++; cnt[i]--; e=1; } y--; }
                }

            // stop if all counts are matching
            for (i=1;i<n;i++) if (cnt[i]!=siz[i]) { i=-1; break; } if (i>=0) break;
            // growth i from any neighbor j<i
            for (i=n-1;i>0;i--)
             for (e=1;(e)&&(cnt[i]<siz[i]);)
                {
                e=0;
                for (x=   1;x<mx;x++) for (y=0;y<my;y++) if ((i==map[x][y])&&(cnt[i]<siz[i])){ x--; j=map[x][y]; if ((i>j)&&(cnt[j]>1)){ map[x][y]=i; cnt[i]++; cnt[j]--; e=1; } x++; }
                for (x=mx-2;x>=0;x--) for (y=0;y<my;y++) if ((i==map[x][y])&&(cnt[i]<siz[i])){ x++; j=map[x][y]; if ((i>j)&&(cnt[j]>1)){ map[x][y]=i; cnt[i]++; cnt[j]--; e=1; } x--; }
                for (x=0;x<mx;x++) for (y=   1;y<my;y++) if ((i==map[x][y])&&(cnt[i]<siz[i])){ y--; j=map[x][y]; if ((i>j)&&(cnt[j]>1)){ map[x][y]=i; cnt[i]++; cnt[j]--; e=1; } y++; }
                for (x=0;x<mx;x++) for (y=my-2;y>=0;y--) if ((i==map[x][y])&&(cnt[i]<siz[i])){ y++; j=map[x][y]; if ((i>j)&&(cnt[j]>1)){ map[x][y]=i; cnt[i]++; cnt[j]--; e=1; } y--; }
                }
            // shrink i from any neighbor j<i
            for (i=n-1;i>0;i--)
             for (e=1;(e)&&(cnt[i]>siz[i]);)
                {
                e=0;
                for (x=   1;x<mx;x++) for (y=0;y<my;y++) if ((i==map[x][y])&&(cnt[i]>siz[i])){ x--; j=map[x][y]; if (i>j)              { map[x+1][y]=j; cnt[j]++; cnt[i]--; e=1; } x++; }
                for (x=mx-2;x>=0;x--) for (y=0;y<my;y++) if ((i==map[x][y])&&(cnt[i]>siz[i])){ x++; j=map[x][y]; if (i>j)              { map[x-1][y]=j; cnt[j]++; cnt[i]--; e=1; } x--; }
                for (x=0;x<mx;x++) for (y=   1;y<my;y++) if ((i==map[x][y])&&(cnt[i]>siz[i])){ y--; j=map[x][y]; if (i>j)              { map[x][y+1]=j; cnt[j]++; cnt[i]--; e=1; } y++; }
                for (x=0;x<mx;x++) for (y=my-2;y>=0;y--) if ((i==map[x][y])&&(cnt[i]>siz[i])){ y++; j=map[x][y]; if (i>j)              { map[x][y-1]=j; cnt[j]++; cnt[i]--; e=1; } y--; }
                }
            }
        // test if teritories are not divided and regenerate if needed
        for (xx=0,i=1;i<n;i++)
            {
            // clear temp bit
            for (x=0;x<mx;x++)
             for (y=0;y<my;y++)
              map[x][y]&=65535;
            // find first occurence
            j=0;
            for (x=0;x<mx;x++)
             for (y=0;y<my;y++)
              if (map[x][y]==i) { map[x][y]|=65536; j=1; x=mx; y=my; }
            if (!j) { xx=1; break; }        // teritory not found
            // growth fill count into j
            for (e=1;e;)
             for (e=0,x=0;x<mx;x++)
              for (   y=0;y<my;y++)
               if (map[x][y]==i)
                {
                yy=0;
                if ((x>   0)&&(map[x-1][y]>=65536)) yy=1;
                if ((x<mx-1)&&(map[x+1][y]>=65536)) yy=1;
                if ((y>   0)&&(map[x][y-1]>=65536)) yy=1;
                if ((y<my-1)&&(map[x][y+1]>=65536)) yy=1;
                if (yy){ j++; map[x][y]|=65536; e=1; }
                }
            if (j!=siz[i]) { xx=1; break; } // teritory incorrect size
            }
        if (xx) continue;                   // regenerate again
        // clear temp bit
        for (x=0;x<mx;x++)
         for (y=0;y<my;y++)
          map[x][y]&=65535;
        break;                              // al OK so stop
        }

//  for (i=0;i<n;i++) { s+=cnt[i]-siz[i]; s+=" "; }
//  Main->Caption=s;
    }
//---------------------------------------------------------------------------

代码没有优化以尽可能保持简单易懂...(可以重新编码以更快)。