c# - 如何在 C# 中生成具有各种大小的单元格的随机洪水填充

Question

在二维空间中，我需要创建一种特殊的洪水填充方法，该方法将根据一组预定义对象(下图中的红色、蓝色、绿色和黄色对象)生成随机数组。

编辑:单个“填充对象”不应与另一个重叠，它们的放置应该看起来是随机的，但为每个对象添加某种出现概率会很好。甚至可以将除红色 1x1 之外的所有物体都放置到一定容量，然后用红色填充其余部分。

现在想象一个随机结果如下。

edit:我提供的结果图像显示所有内容总是用红色方 block 分隔，这当然是可能的，但不是范围的必要部分。我以这种方式绘制图像是为了消除任何认为除了红色之外的某些颜色对象被认为与其他类似颜色对象“可连接”的想法。换句话说，我不希望人们认为 3x3 的绿色物体可以变成 6x3，作为算法的一部分。它应该被视为两个独立的 3x3 随机相邻放置。为了解决@jdweng 评论，部分解决方案很可能需要向 FillObject 类添加某种出现概率字段，然后始终将 1x1 红色方 block 视为构成空间的对象。

这是我到目前为止编写的代码。我很难把这件事想到底。我熟悉标准的填充，但我不确定如何使用随机大小的“填充对象”。

//Defined objects that make up the grid fill
public class FillObject
{
    public int xDim { get; set; }
    public int yDim { get; set; }

    public string color { get; set; }

    public FillObject(int x, int y, string c)
    {
        xDim = x;
        yDim = y;
        color = c;
    }
}

//container for information about a position on the grid
public class GridPosition
{
    public int xPosition { get; set; }
    public int yPosition { get; set; }

    public string color { get; set; }
}

public class GridGenerator
{
    //declare the intitial possible fill objects
    public static FillObject[] fillObjects = new FillObject[]
    {
        new FillObject(1, 1, "red"),
        new FillObject(2, 2, "blue"),
        new FillObject(3, 3, "green"),
        new FillObject(4, 4, "yellow")
    };

    //Generic list of grid positions
    public List<GridPosition> grid = new List<GridPosition>();

    //Method to generate random grid filled with the fill objects
    public void GenerateGrid(int startX, int startY, int endX, int endY)
    {
        //Iterate through grid and set each "cell" to a color based on the original fill objects
        for(int x = startX; x <= endX; x += 1)
        {
            for(int y = startY; y <= endY; y += 1)
            {
                grid.Add(new GridPosition());
            }
        }
    }
}

我考虑过只运行 for 循环并测试列表中已经创建的位置，然后使用随机机会“放入”填充对象(如果它们适合)，但在每个循环中测试列表似乎效率很低迭代是否存在填充位置，然后测试每个对象的偏移量也会出现问题。可能是一种递归方法，从最大的“fillObject”开始，然后递归测试和填充，但它又一次看起来非常麻烦。在我没有看到的网格的一个循环中是否有一些聪明的方法可以做到这一点？

编辑:这是明确的目标

• 创建一个生成列表对象的方法包含网格上的每个位置。

• 每个网格位置应包含 int x 和 int y 的位置GridPosition 类中的字段。

• 生成的 GridPosition 对象应遵循原始对象
  FillObject 结构。

• 每个对象出现的概率都很好，什么都
  剩下的可以用红色 1x1 对象填充。

• 相同颜色的物体，可以相邻(即使结果
  图片没有显示这个)

• 理想情况下，这是一次性完成的(如洪水填充)，但是
  递归是另一种可能性。

• 不需要真正的随机性，只是看起来有点
  随机的，但也不应该有图案的出现。

Answer 1

好吧，我今天早上有空，所以我试了一下。为了让它更快，我使用了 unsafe、fixed 和指针。我不确定您是否想要图像，但这也可以仅与多维数组一起使用。

填充对象

public class FillObject
{
   public FillObject(int width, Color color)
   {
      Width = width;
      Color = color.ToArgb();
   }

   public int Color { get; set; }

   public int Width { get; set; }
}

扩展方法

public static class Extensions
{
   public static Color NextColor(this Random r) => Color.FromArgb(r.Next(256), r.Next(256), r.Next(256));

   public static FillObject GetObject(this List<FillObject> objects, int maxSize, Random rand)
   {
      var nextObjs = objects.Where(o => o.Width <= maxSize)
                              .ToList();
      return nextObjs[rand.Next(nextObjs.Count)];
   }
}

辅助方法

public static unsafe bool GetMaxSize(int x, int y, Size size, int* array, int pad, out int maxSize)
{

   maxSize = 0;

   //we cant be within pad distance of anything else or the edges
   for (var y2 = y - pad; y2 < y + pad; y2++)
      for (var x2 = x - pad; x2 < x + pad; x2++)
         if (y2 < 0 || x2 < 0 || y2 >= size.Height || x2 >= size.Width || *(array + x2 + y2 * size.Width) != 0)
            return false;

   // so what do we have left
   for (var y2 = y - pad; y2 < y + 1; y2++)
   {
      var max = maxSize > 0 ? maxSize : _largest + pad;
      maxSize = 0;
      for (var x2 = x; x2 < size.Width && x2 < x + max; x2++, maxSize++)
         if (*(array + x2 + y2 * size.Width) != 0)
            break;
   }

   // safety first
   maxSize = Math.Min(maxSize - pad, Math.Min(size.Width - x - pad, size.Height - y - pad));

   return maxSize > 0;
}

主要方法

public static unsafe void Generate(Size size, int* array, int pad)
{
   for (var y = 0 + pad; y < size.Height; y++)
      for (var x = 0 + pad; x < size.Width; x++)
      {
         // no maxSize bail
         if (!GetMaxSize(x, y, size, array, pad, out var maxSize))
            continue;

         // pick a random one
         var nextObj = _objects.GetObject(maxSize, _rand);

         // draw the thing
         for (var y2 = y; y2 < y + nextObj.Width; y2++)
            for (var x2 = x; x2 < x + nextObj.Width; x2++)
               *(array + x2 + y2 * size.Width) = nextObj.Color;

         // start again outside that width
         // remembering the loop will increment this anyway 
         x += nextObj.Width + pad - 1;
      }
}

用法

private static unsafe void Main(string[] args)
{

   _objects = Enumerable.Range(0, 25)
                        .Select((i, i1) => new FillObject(i, _rand.NextColor()))
                        .ToList();

   _largest = _objects.Max(x => x.Width);

   var size = _rand.Next(100, 100);

   using (var bmp = new Bitmap(size, size, PixelFormat.Format32bppPArgb))
   {
      var bitmapData = bmp.LockBits(new Rectangle(0, 0, size, size), ImageLockMode.ReadWrite, PixelFormat.Format32bppPArgb);
      var data = (int*)bitmapData.Scan0;
      Generate(new Size(size, size), data, 1);
      bmp.UnlockBits(bitmapData);
      bmp.Save(@"D:\TestImage.bmp");
   }
}

测试 100x100 5 个 block 1 个填充

测试 100x100 5 block 2 填充

测试 100x100 10 个 block 2 个填充

测试 100x100 b25 locks 2 padding

测试 100x100 25 个 block 1 个填充

测试 100x100 25 block 0 填充

总结

好的前提是

• 从 x 到 y 移动穿过平面
• 确定可用空间
• 获取适合的对象列表
• 随机选择一个
• 画出来

但是，如果您使用规范(即随机变量)，您会发现存在偏差。也就是说，在第一行它可以放任何它喜欢的东西。但是，后续行将受到限制，因此它将偏向于较小的 block 。然后在远处，它会偏向最小的黑色来填充图像。

还有对角线效应的偏差，这基本上只是试图在下一行中放入随机 block 的结果。

可能有更多的微优化来使它更快，但是它非常好并且可以在几毫秒内运行

无论如何，我想这是一个很好的起点，你可以加入胡椒粉和盐调味

祝你好运