Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

random cubes

share|improve this question
    
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
add comment

3 Answers

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.

share|improve this answer
add comment
  • 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).

share|improve this answer
1  
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
add comment

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

share|improve this answer
    
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 comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.