11

我需要将瓷砖放置在一个从中心点向外辐射的大网格上，这种方式看起来是有机的和随机的。新瓷砖需要在网格上找到至少接触 1 个其他瓷砖的开放空间。

任何人都可以向我指出任何可能对此有所帮助的方向吗？或者我能读到的一些基本概念就是这样的？

例如，在这张图片中，已经创建了一个形状（黄色），我可能正在接收一个新的瓷砖，它可能是 1x1、2x2 或 3x3。试图找到一种好方法来确定我可以放置新瓷砖的位置，以便它接触到当前瓷砖的最大数量。

图片： 替代文字 http://osomer.com/grid.JPG

4

4 回答 4

3

或者，您可以解决这个问题，因为黄色瓷砖在蓝色/背景处“腐蚀”掉。要做到这一点，在每一步，让一个黄色瓷砖在基本方向上与其相邻的所有背景瓷砖的“侵蚀总和” E中添加一个固定数字（也许是对角相邻的背景瓷砖的一小部分） ）。

然后，当需要放置新图块时，您可以为每个背景图块选择一个从 0 到E的随机数；最伟大的被“侵蚀”掉了。或者，您可以做一个简单的加权随机选择，其中E是它们的权重。

对于 2x2 或 3x3 瓷砖，您只能从适合“适合”其中的 2x2 或 3x3 正方形的瓷砖中挑选（即，2x2 或 3x3 边缘的腐蚀瓷砖，这样它就不会与已经 -放置的瓷砖）。但实际上，您永远不会得到像一对一侵蚀/瓷砖放置那样自然的东西。

您可以通过让它们在每次迭代中持续存在来节省重新计算侵蚀和的时间，只有当您添加一个新瓷砖时，才会将其周围的侵蚀和加起来（一个简单的+=）。在这一点上，它与建议的另一个答案基本相同，尽管有不同的观点/哲学。

侵蚀和E的样本网格，直接基数邻居为 +4，对角邻居为 +1：

侵蚀总和 http://img199.imageshack.us/img199/4766/erosion.png

E较高的最有可能被“侵蚀”掉；例如，在这一个中，西面和南面的两个小入口最有可能被黄色侵蚀掉，其次是北面和东面的较小海湾。最不可能的是那些几乎没有碰到黄色的角落。您可以通过为每个图块分配一个从 0 到E的随机数并侵蚀具有最高随机数的一个，或进行简单的加权随机选择，或通过您选择的任何决策方法来决定哪一个。

于 2010-06-25T06:25:56.723 回答
2

对于纯随机，您从一个空网格和一个“候选”列表（也是空的）开始。

将第一个图块放在网格的中心，然后将每个相邻的图块添加到您刚刚放入“候选”列表的图块中。然后，每回合，在“候选”列表中选择一个随机条目并在那里放置一个图块。查看您刚刚放置瓷砖的位置旁边的每个相邻网格位置，对于每个也是空的网格位置，下次将其放在“候选”列表中（如果还没有的话）。

为避免在您的瓷砖网格中创建孔洞，请根据已填充的相邻瓷砖的数量增加选择网格位置的概率（因此，如果只有一个相邻的瓷砖已被填充，则可能性较低。如果它们都已填充，它的概率很高）。

在伪代码中：

grid = new array[width,height];
candidates = new list();

function place_tile(x,y) {
   // place the tile at the given location
   grid[x,y] = 1;

   // loop through all the adjacent grid locations around the one
   // we just placed
   for(y1 = y - 1; y1 < y + 1; y1++) {
       for(x1 = x - 1; x1 < x + 1; x1++) {
           // if this location doesn't have a tile and isn't already in
           // the candidate list, add it
           if (grid[x,y] != 1 && !candidates.contains(x1,y1)) {
               candidates.add(x1,y1);
           }
       }
   }
}

// place the first tile in the centre
place_tile(width/2, height/2);

while (!finished) {
   // choose a random tile from the candidate list
   int index = rand(0, candidates.length - 1);

   // place a tile at that location (remove the entry from
   // the candidate list)
   x, y = candidates[index];
   candidates.remove(index);
   place_tile(x, y);
}
于 2010-06-25T05:06:09.493 回答
1

您的问题的问题是“有机和随机”可以是许多不同的东西。让我显示两个链接

  • 生成随机分形地形（查看“多云天空”部分并想象您将其转换为黑白，或者在您的情况下为黄色/背景）。
  • 模拟侵蚀（查看“侵蚀”下的图像）

以上两个样本对我来说是“有机的和随机的”，但您可能对这些样本不满意。所以，我认为你必须更好地定义什么是“有机和随机”。

现在，我将采用您对添加新瓷砖的指导规则的定义（但不要认为这一定是同一个问题），我将其解读为：

给定两个形状（假设是位图）找到形状的相对位置，使得接触边的数量最大

我也会假设

  • 不允许重叠
  • 您可以在生成的合并形状内留下孔
  • 你不能旋转形状

在这种情况下，您需要测试少于 x y 的解决方案，并且在每个解决方案中您需要 - 如果有重叠则丢弃它 - 如果它们不接触则丢弃它 - 如果它们接触则计算共同边的数量 所有三个上述测试可以通过扫描所有黄色瓷砖（数量为 konst x*y）在恒定时间内完成

所以，以上可以在 O(n^4) 中轻松完成，这对你来说足够了吗？

于 2010-06-25T08:54:39.633 回答
0

计算对偶图的随机生成树，即顶点为单元格中心的网格。为此，从网格的中心开始并进行随机深度优先搜索。然后绘制细胞来增加距中心的树距离。

于 2010-06-25T11:46:46.820 回答