How to generate a random flood fill of cells with various sizes in C#

Question

In 2 dimensional space I need to create a special kind of flood fill method that would generate a random array based on a set of predefined objects, the red, blue, green, and yellow objects in the image below.

edit: No single "fill object" should overlap another and their placement should appear to be random but it would be fine to add some sort of probability of occurrence for each object. Maybe even place all of the objects except the red 1x1 and until a certain capacity is met, and then fill in the rest with the red.

Now imagine a random result that would like the following.

edit: The result image I have provided shows that everything is always separated with red squares, This could certainly be possible, but not a necessary part of the scope. I drew the image this way in order to eliminate any notion that some color object aside from red is considered "joinable" to other like colored objects. In other words, I didn't want people to think that a 3x3 green object could become a 6x3, as part of the algorithm. It should be treated as a two separate 3x3s that were placed next to each other randomly. To address @jdweng comment, part of the solution could very well entail adding some sort of probability of occurrence field to the FillObject class, and then always treat the 1x1 red squares as the object that makes up space.

Here is the code I have come up with so far. I'm having a tough time thinking this one through to the end. I'm familiar with a standard flood fill, but I'm not sure how to make that work with the randomly sized "fill objects".

//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());
            }
        }
    }
}

I have considered just running through the for loop and testing the list for already created positions and then using a random chance to "drop" in the fill objects if they can fit, but it seems rather inefficient to test the list every loop iteration for the existence of a populated position and then there would also be an issue with testing for offsets for each object. Possibly a recursive method that starts with the largest "fillObject" and then recursively tests and fills, but again it just seems very cumbersome. Is there some clever way of doing this in one loop of the grid that I'm not seeing?

edit: Here are the explicit goals

• Create a method that generates a List object that contains every position on a grid.

• Each grid position should contain the position as int x and int y as fields in the GridPosition class.

• The generated GridPosition objects should should honor the original
  FillObject structures.

• Probability of occurrence for each object is fine, and everything
  left over can be filled with red 1x1 objects.

• Objects of the same color, can be adjacent(even though the result
  image doesn't show this)

• Ideally this is done in a single pass(like a flood fill), but
  recursion is another possibility.

• True randomness isn't necessary, it just needs to look somewhat
  random, but there should also not be the appearance of patterns.

Answer 1

Ok, i had a free hour this morning so i had a stab at this. To make it fast i used unsafe, fixed and pointers. I am not sure whether you wanted an image or not, however this can be used with just a multi dimensional array as well.

FillObject

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

   public int Color { get; set; }

   public int Width { get; set; }
}

Extension Methods

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

Helper Method

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

Main Method

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

Usage

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

Test 100x100 5 blocks 1 padding

Test 100x100 5 blocks 2 padding

Test 100x100 10 blocks 2 padding

Test 100x100 b25 locks 2 padding

Test 100x100 25 blocks 1 padding

Test 100x100 25 blocks 0 padding

Summary

Ok the premise of this was

• To just move across the plane from x then y
• Determine the free space
• Get a list of objects that would fit
• Choose a random one
• Draw it

However, if you play with the specs (i.e random variables) you will find there are biases. That's to say, on the first row it can fit anything it likes. However, subsequent rows it will be limited so it will bias to smaller blocks. And then towards the far extents it will bias to the smallest blacks to fill the image.

Also there is a bias towards a diagonal effect, this is basically just a result of the trying to fit in random blocks on the next line.

There are probably more micro optimizations to make this faster, however it is pretty good and works in milliseconds

Anyway, i guess this is a good starting point and you can add pepper and salt to taste

Good luck