how to programtically build a grid of interlocking but random sized squares

Question

I want to create a two dimensional layout of rectangular shapes, a grid made up of random sized cubes. The cubed should fit together and have equal padding or margin (space between). Kind of like a comic book layout, or more like the image attached.

How could I do this procedurally?

Practically, I would probably be using Python and some graphic software to render an image, but I don't know the type of algorithm (or whatnot) I would need to use to generate the randomized grid.

Answer 1

Start with a grid of 1x1 cells. Pick a random spot, merge cells a random amount or till it collides with a larger rectangle.

This will get you something similar to the image you provide.

There's a bigger issues if you don't want a number of smaller cells acting as padding between your bigger cells. A comic book for example, wants to minimize the amount of dead space and have at most ~9 cells. You could pick some points and draw some lines and call those your cells.

//Philip Haubrich, 2012, public domain
//Build instructions: gcc comicPanels.c

#include <stdio.h>  //entirely for printf()
#include <stdlib.h> //Entirely for rand()
#include <time.h> //Entirely to help srand()

#define PAINTINGSIZE_X 79
#define PAINTINGSIZE_Y 20

#define MYNUMBEROFPOINTS 4

#define MINDISTANCEBETWEENBOXES 2
//Because I suck at naming things. You should really fix this before it gets into your codebase.

#define NORTH 0
#define EAST 1
#define SOUTH 2
#define WEST 3

#define WHITE 0
#define BLACK 1

//Or, you know, a struct with .color, .r .g .b .alpha .editablebydeadpool
char g_paintingArea[PAINTINGSIZE_X][PAINTINGSIZE_Y];

void drawLineUntilBlocked(int x, int y, int direction)
{
  do
  {
    g_paintingArea[x][y] = BLACK;
    switch(direction)
    {
    case NORTH:
      y++;
      break;
    case SOUTH:
      y--;
      break;
    case EAST:
      x++;
      break;
    case WEST:
      x--;
      break;
    default:
      printf("I really need to get away from switch statements...\n");
    }
  } while(g_paintingArea[x][y] == WHITE && x > 0 && y > 0 && x < PAINTINGSIZE_X && y < PAINTINGSIZE_Y);
  //dowhile, when you are too lazy to re-arrange the code
}

//Feel free to sub in something like SDL or openGL here
void paint()
{
  int x,y;
  for(y=0; y<PAINTINGSIZE_Y; y++)
  {
    for(x=0; x<PAINTINGSIZE_X; x++)
    {
      printf("%c",g_paintingArea[x][y]);
    }
    printf("\n");
  }
}

int empty(int origx, int origy)
{
  int x,y;
  for(x=origx-MINDISTANCEBETWEENBOXES; x<origx+MINDISTANCEBETWEENBOXES; x++)
  {
    for(y=origy-MINDISTANCEBETWEENBOXES; y<origy+MINDISTANCEBETWEENBOXES; y++)
    { 
      if( x < 0 || y < 0 || x >= PAINTINGSIZE_X || y >= PAINTINGSIZE_Y)
        continue;
      if( g_paintingArea[x][y] == BLACK)
        return 0; //Not empty, there is something nearby
    }
  }
  return 1; //Empty, like my heart
}

void init()
{
  int x,y;
  //initalize to zero
  for(x=0; x<PAINTINGSIZE_X; x++)
  {
    for(y=0; y<PAINTINGSIZE_Y; y++)
    {
      g_paintingArea[x][y] = WHITE;
    }
  }
  //Border, or as I like to call it B-town
  for(x=0; x<PAINTINGSIZE_X; x++)
  {
    g_paintingArea[x][0] = BLACK;
    g_paintingArea[x][PAINTINGSIZE_Y-1] = BLACK;
  }
  for(y=0; y<PAINTINGSIZE_Y; y++)
  {
    g_paintingArea[0][y] = BLACK;
    g_paintingArea[PAINTINGSIZE_X-1][y] = BLACK;
  }

  //oh yeah, this is important
  x = abs(time(NULL));
  srand(x);
}

int main(int argc, char** argv)
{
  int x,y,i; 

  init();

  //That part you actually asked about
  for( i=0; i<MYNUMBEROFPOINTS; i++)
  {
    x = rand() % PAINTINGSIZE_X;
    y = rand() % PAINTINGSIZE_Y;

    if(!empty(x,y))
      continue;

    switch(rand()%3)
    {
    case 0: //4 way
      drawLineUntilBlocked(x,y,NORTH);
      drawLineUntilBlocked(x,y,SOUTH);
      drawLineUntilBlocked(x,y,EAST);
      drawLineUntilBlocked(x,y,WEST);
      break;
    case 1: //North/sourth
      drawLineUntilBlocked(x,y,NORTH);
      drawLineUntilBlocked(x,y,SOUTH);
      break;
    case 2: //East/West
      drawLineUntilBlocked(x,y,EAST);
      drawLineUntilBlocked(x,y,WEST);
      break;
    default:
      printf("Oh god wtf, and other useful error messages\n");
    }
  }
  //If I have to explain to you that this next bit will depend on your platform, then programming may not be for you
  paint();  
  return 0;
}

There are plenty more way to skin a cat.

Answer 2

• Start with a square that describes the entire image.

• Add the square to an empty array.

• For each square in the array:

  • Create a boolean with a random true/false value.
  • If the value is true:
    • Split the square into into 4 equally-sized sub-squares.
    • Add them to the end of the array.
    • Remove the current square from the array.

At the end of the process, you will have an array of randomly-sized squares. Note that you'll probably want to define a minimum size (at which point no more dividing is done) and a maximum size (if the square is larger, always split regardless of the boolean value).

Answer 3

Determine the size and geometry of the image. If you want this to be tiled, the underlying geometry is that of a torus.

Maintain a list of the upper left hand corner of all possible shapes. Initially, this is every possible spot.

Pick a random sized rectangle (within the constraints you have decided - in the example image they are squares and have a maximum size of 4). Place this rectangle in a random upper left hand corner spot.

If the rectangle is too large (overlaps an existing allocated spot), trim the dimension of the rectangle so that it fits.

Remove all of the locations that are covered by this rectangle from the list of possible upper left hand corners.

Repeat until the upper left hand corner list is empty.

Render the resulting array in your preferred way. This is where you would introduce a margin.

---

If you are unfamiliar with any particular graphics library, consider using the ppm format. The key advantage is that you could write out a text file and then use one of the converters (ppmto___) to convert the image to your chosen format (ppmtogif. ppmtojpeg, ...)