有没有这样的随机填充矩阵的算法？
有没有这样的随机填充矩阵的算法？
提问于 2017-04-26 09:19:26
考虑一个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)上创建任意大小的区域。
有没有你能建议的现有算法？或者有什么办法吗？
编辑:6个地区(基于给定的例子)，填补整个空间。不应留下背景元素(0值元素)。我们的示例中的6个区域应该完全填充209个元素。
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-04-27 13:24:19
为了保持一些随机性，我这样处理这个问题：
- 生成每个的种子起始点 简单地计算每个区域的随机起点，约束条件是任何两个起始点之间必须至少有一定的最小距离。这将为增长提供一些空间，因此结果看起来更好。
- 在你可以的时候种植每一颗种子 只需迭代地扩大每个领土，直到不存在缺口(忽略所需的领土大小)。
- 更正尺寸
因此，只需将领土
i=1，并扩大/缩小他们从任何邻近的领土j>i。然后处理i=2..。当这样做时，按递减顺序做同样的事情，因此，以区域i=n为例，并从任何邻居j<i中放大/缩小。 把这整件事循环起来，直到领土有正确的大小。 - 验证 #3可以将一些区域划分为非后续区域，我怀疑这是不可取的。因此，检测这个，如果这个案例再次生成这整个事件。 要检测到这一点，只需为每个领土找到它的第一个有效的单元格和洪水填充计数，该领土是多么的bigg。如果不匹配的面积，领土已经被划分，你应该再次生成。 如果所有领土都匹配大小，那么地图是相关的，你就完成了
在这里预览#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;
}
//---------------------------------------------------------------------------代码并没有被优化到尽可能简单易懂的程度.(可以被重新编码得快得多)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/43629968
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号