随机平铺布局

Question

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

谁能给我指出正确的方向，任何可能对此有帮助的东西？或者一些我能读到的基本概念，都是在这种背景下的？

例如，在这张图片中，有一个已经创建的形状(黄色)，我可能正在接收一个新的磁贴，它可能是1x1、2x2或3x3。试着找到一个好的方法来弄清楚我可以把新的瓷砖放在哪里，这样它就会接触到当前瓷砖的最大数量。

图片来源：alt text http://osomer.com/grid.JPG

Answer 1

或者，您可以将此问题视为黄色瓷砖对蓝色/背景的“侵蚀”。要做到这一点，在每一步，让一个黄色的瓷砖添加一个固定的数字“侵蚀和”E的所有背景瓷砖相邻的主要方向(也许是该分数的一小部分，以背景瓷砖的对角)。

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

对于2x2或3x3的瓷砖，只能从适当地“适合”2x2或3x3正方形的瓷砖中拾取(即，2x2或3x3的瓷砖与其边缘被侵蚀的瓷砖，这样它就不会与已放置的瓷砖重叠)。但实际上，你永远不会得到像逐个侵蚀/瓦片放置一样自然的东西。

通过在每次迭代中保持侵蚀和，可以节省重新计算侵蚀和的时间，只有当您添加新的瓦片时，才会增加它周围的瓦片的侵蚀和(简单的+=)。在这一点上，它基本上与另一个建议的答案相同，尽管有不同的视角/哲学。

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

Erosion Sums http://img199.imageshack.us/img199/4766/erosion.png

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

Answer 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);
}

Answer 3

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

• generating random fractal terrain (查看“Cloudy Skies”一节，想象一下您将其转换为“b/w”，或者在您的示例中为erosion (查看“random fractal terrain”下的图像)

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

现在，我将采用您对添加新tiles的指导规则的定义(但不要认为这一定是相同的问题)，我将其理解为：

给定两个形状(假设是位图)，找出形状的相对位置，使接触边的数量最大

我还会假设

不允许旋转重叠

• 您可以在合并后的形状中留下空洞you
• you not rotate shapes

在这种情况下，您需要测试的解决方案少于x_y解决方案，并且在每个解决方案中，您需要-如果有重叠，则丢弃-如果它们没有接触，则丢弃它们-如果它们接触，则计算常见的边缘数量以上三个测试可以通过扫描所有黄色瓷砖(数量为konst_x*y)在固定时间内完成

因此，上述操作可以在O(n^4)中轻松完成，这对您来说足够了吗？