Algorithm to fill a grid

1. Jan 29, 2006

calluscus

2. Jan 30, 2006

Sartak

Well, what exactly are you trying to accomplish? If the grid is small enough, you could fill in the grid with integers, 1 ... r * c, and then for each cell, swap its value with another, random cell, that is to the right or below the current cell. This is similar to Knuth's shuffling algorithm except in two dimensions. C code follows.

Code (Text):

#include <stdlib.h>

#define X (80)
#define Y (24)

int main()
{
int x, y; /* current grid position */
int i, j; /* x, y for random grid position with which to swap*/
int k;    /* auxiliary variable to fill out the initial sorted grid */
int t;    /* auxiliary variable for swapping */
int grid[X][Y];

srand(time(NULL)); /* seed the random number generator */
k = 0;

/* fill in the grid with (1, 2, ..., x*y) */
for (y = 0; y < Y; ++y)
for (x = 0; x < X; ++x)
grid[x][y] = ++k;

for (y = 0; y < Y; ++y)
for (x = 0; x < X; ++x)
{
/* select a random row between this one and the last one */
j = rand() % (Y - y) + y;

if (j == y)
{
/* if it's on the current row, select a column to our right */
i = rand() % (X - x) + x;
}
else
{
/* if it's on a row below, select _any_ column */
i = rand() % X;
}

/* swap */
t = grid[i][j];
grid[i][j] = grid[x][y];
grid[x][y] = t;
}

/* do stuff with the grid here */

return 0;
}

(note: I have not even so much as compiled the above code, but hopefully you can follow what I'm trying to do)

Last edited: Jan 30, 2006
3. Jan 30, 2006

ty very much