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

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.

-
Really, this isn't a programming problem. You have to come up with and then decide on the method - aka 'algorithm' - by which you want the squares; implementing it is then a programming problem. To come up with the method? Start with a blank piece of paper - preferably lots of pieces of paper - get drawing, and then describe what you're doing. – AakashM Nov 21 '12 at 9:03

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

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.

-

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, ...)

-
Thanks. In fact I am more interested in converting it into a set of center points (on an x,y grid) and scale descriptions (as in 1 or .5, or 2 for example). I will feed these numbers into a 3d app. – Mrwolfy Nov 22 '12 at 7:09
• 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).

-
This seems like a good solution. – Mrwolfy Nov 20 '12 at 11:28
(I used a similar algorithm for a recursive maze generator in college) This will have the side effect of always having lines that cut through the entire image. – MichaelT Nov 20 '12 at 14:40
@MichaelT: Definitely an issue, but the simplicity and speed of the algorithm arguably makes up for it. It really depends on the use case whether or not this is an appropriate approach to the problem. The example image appears to have been generated with this algorithm as it suffers from the issue you highlighted. – Ant Nov 20 '12 at 15:17