Help with a random walk

**pxleyes** · 02-26-2004

I am trying to write a program that does a random walk across a multi-dimensional array. To say the least, I am stuck; This is the description of what I want and what I got:

Write a program that generates a “random walk” across a 10x10 integer array. The array will contain integers (all 0 initially). The program must randomly “walk” from element to element, always going up, down, left, or right by one element. The elements visited by the program will be labeled with the numbers 1 to 30, in the order visited. Here is an example of the desired output,

1 0 0 0 0 0 0 0 0 0
2 3 4 0 0 0 0 0 0 0
0 0 5 0 0 0 13 14 15 0
0 0 6 7 8 9 12 0 16 0
0 0 0 0 0 10 11 0 17 18
0 0 0 0 0 0 0 0 0 19

0 0 0 0 0 24 23 22 21 20
0 0 0 0 0 25 0 0 0 0
0 0 0 0 0 26 27 28 0 0
0 0 0 0 0 0 0 29 30 0

# include <stdlib.h>
# include <time.h>
…
…

main () {

srand ((unsigned) time (NULL)); /* This is to seed the randomizing function. USE THIS FUNCTION ONLY ONCE AT THE START OF MAIN. */

That has to be used in main, but i dont know how to use it.

This is all I have so far:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10

int a[N][N]={0};

int boundary(int a[N][N], int r, int c, int GO){
  for(c=0; c<=9; c++){
    for(r=0; r<=9; r++){
       if (a[c][r]==0){
          return GO;}
       }
   }
}

int walk(int move, int walk, int GO){
  if (GO){
   move=rand () % 4;
  }
}

main()
{
int r,c;

      for(c=0; c<=9; c++){
        for(r=0; r<=9; r++){
          printf("%d \t", a[c][r]);
        }
      }

      system("PAUSE");
}

The desidered output didn't show up like it was suppsosed to, but its a 10x10 array with the numbers being hte walk.

**quzah** · 02-26-2004

Here's the general idea:

Code:

startx = rand()%10; /* pick starting x coordinate */
starty = rand()%10; /* pick starting y coordinate */

while steps less than 30
    mark this spot with the step number
    move direction rand % 4
    if( direction_ok( xcoord, ycoord, move ) )
        update xcoord and ycoord
    else
    if( other_direction( xcoord, ycoord, move ) )
        update xcoord and ycoord with other
    else
        dead_end

Basicly, pick a starting location. Then move one direction at random if that space is set to zero. If it isn't, you'll have to check the other directions to see if they're valid. If none are valid, you're at a dead end. Quit, or implement back tracking.

Quzah.

**c99** · 02-27-2004

This is my second prototype after editing .

Code:

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ROWS		10
#define COLS		10
#define MOVES		20
#define DIRECTIONS	4


int main(void)
{
	int i, j, x, y, direction;

	enum { FALSE, TRUE           };
	enum { up, down, left, right };


	static int iarray[ROWS][COLS], proxime[DIRECTIONS];


	srand((unsigned)time(NULL));
	
/*
	Determine origin coordinates.
*/
	x = rand() % COLS;
	y = rand() % ROWS;

/*
	Start making some moves.
*/	
	i = 0;

	while (++i <= MOVES)
	{
		iarray[x][y] = i;

		
/*
	Determine whether any possible coordinate is out of bounds or occupied.
*/
		if (iarray[x + 1][y] || ((x + 1) == COLS))
			proxime[up] = TRUE;

		if (iarray[x][y - 1] || ((y - 1) < 0    ))
			proxime[down] = TRUE;

		if (iarray[x - 1][y] || ((x - 1) < 0    ))
			proxime[left] = TRUE;

		if (iarray[x][y + 1] || ((y + 1) == ROWS))
			proxime[right] = TRUE;		
		
/*
	Determine if any coordinates are within proximity.
*/
		if (proxime[0] && proxime[1] && proxime[2] && proxime[3])
		{
			printf("Deadlock. Please try again.\n");

			return EXIT_FAILURE;
		}

/*
	Choose a direction from available direction(s) at random.
*/
		while (iarray[x][y])
		{
			direction = rand() % 4;

			switch (direction) {

			case 0: if (!proxime[up   ]) ++x;
				break;
			case 1: if (!proxime[down ]) --y;
				break;
			case 2: if (!proxime[left ]) --x;
				break;
			case 3: if (!proxime[right]) ++y;
				break;
			default:
				break;
			}
		}
		for (j = 0; j < DIRECTIONS; j++) proxime[j] = 0;
	}


/*
	Display result to stdout.
*/
	printf("\n\n");

	for (i = 0; i < ROWS; i++)
	{
		for (j = 0; j < COLS; j++)
		{
			if (iarray[i][j] == 0)
			{
				printf("    ");
			}
			else
			{
				printf("%3d ", iarray[i][j]);
			}
		}
		printf("\n\n");
	}

	return EXIT_SUCCESS;
}

**Prelude** · 02-27-2004

>This is my prototype.
Not bad, but I do have one question about your code if you won't take offense and jump down my throat when I ask it.

>i ^= i;
Don't you think this is just a bit too obscure to make sense in the way you use it? i = 0 would work just as well, and I haven't met a programmer yet that doesn't understand such a simple assignment. I have, however, met many people who wouldn't know how an XOR self-assignment works and would be confused if they saw it.

**c99** · 02-27-2004

Prelude.

Absolutely, I've edited my code, hopefully, to increase readability.

Now it displays only the actual path taken by the program.

Criticism is very welcome, I expect it.

**pxleyes** · 02-27-2004

interesting stuff guys. I was wondering if there was a way to split it up into a bunch of functions with only printing the array at the end. I know its not efficient, but just wondering.

To clarify. this is what I have come up with so far:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int a[10][10];

/*defines array*/
int init_array(int a[10][10], int r, int c) {
	for(r=0; r<=9; r++) {
		for(c=0; c<=9; c++) {
			a[c][r]=0;
		}
	}
}

/*
  checks to see if the position has a move made on it yet
  returns 0 if position if free, -1 if not
*/
int check_pos(int c, int r, int GO) {
	if (a[c][r] == 0) {
		return GO;
	} else {
		return 0;
	}
}

/*
  creates the direction for the move to make
	0 = up
	1 = right
	2 = left
	3 = down
*/
int direction(int d) {;
	d=rand() % 4;
	return d;
}

/*moves the number to the next position*/
int walk(int d, int c, int r, int GO, int m, int a[10][10]) {
	if (GO) {
		for(m=1; m<=30; m++) {
			if (d=0)
				a[c+1][r]=m;
			else if (d=1)
				a[c][r+1]=m;
			else if (d=2)
				a[c][r-1]=m;
			else if (d=3)
				a[c-1][r]=m;
		}
	}
}


int main() {
	int r,c;
	for(r=0; r<=9; r++){
		for(c=0; c<=9; c++){
			printf("%d \t", a[c][r]);
		}
	}
	system("PAUSE");
}

**Prelude** · 02-27-2004

>I was wondering if there was a way to split it up into a bunch of functions with only printing the array at the end
Of course. That would really be a better solution anyway. If you look at c99's code, you'll see that the code outside of the walk algorithm only relies on iarray. So if you declare iarray in main and pass it to a walk function, you can separate the algorithm from the driver with relative ease. For example:

Code:

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ROWS		10
#define COLS		10
#define MOVES		20
#define DIRECTIONS	4

int walk(int iarray[ROWS][COLS])
{
  int i = 0, j, x, y, direction;
  static int proxim[DIRECTIONS];

  enum { FALSE, TRUE           };
  enum { up, down, left, right };

  x = rand() % COLS;			/* Assign start position */
  y = rand() % ROWS;			/*			 */

  while (++i <= MOVES)
  {
    iarray[x][y] = i;

    if (iarray[x + 1][y] || ((x + 1) == COLS))
      proxim[up] = TRUE;

    if (iarray[x][y - 1] || ((y - 1) < 0    ))
      proxim[down] = TRUE;

    if (iarray[x - 1][y] || ((x - 1) < 0    ))
      proxim[left] = TRUE;

    if (iarray[x][y + 1] || ((y + 1) == ROWS))
      proxim[right] = TRUE;		

    if (proxim[0] && proxim[1] && proxim[2] && proxim[3])
    {
      printf("Deadlock. Please try again.\n");

      return EXIT_FAILURE;
    }

    while (iarray[x][y])		/* Find empty coords	*/
    {
      direction = rand() % 4;	/* Choose a direction	*/

      switch (direction) {

      case 0: if (!proxim[up   ]) ++x;
        break;
      case 1: if (!proxim[down ]) --y;
        break;
      case 2: if (!proxim[left ]) --x;
        break;
      case 3: if (!proxim[right]) ++y;
        break;
      default:
        break;
      }
    }
    for (j = 0; j < DIRECTIONS; j++) proxim[j] = 0;
  }

  return EXIT_SUCCESS;
}

int main(void)
{
  int i, j;
  static int iarray[ROWS][COLS];

  srand((unsigned)time(NULL));

  if (walk(iarray) == EXIT_FAILURE)
  {
    return EXIT_FAILURE;
  }

  printf("\n\n");				/* Display results	*/

  for (i = 0; i < ROWS; i++)
  {
    for (j = 0; j < COLS; j++)
    {
      if (iarray[i][j] == 0)
      {
        printf("    ");
      }
      else
      {
        printf("%3d ", iarray[i][j]);
      }
    }
    printf("\n\n");
  }

  return EXIT_SUCCESS;
}

>I've edited my code, hopefully, to increase readability.
That wasn't really my point. It's a short leap to realizing that i ^= i means i = i ^ i. My point was that not many people these days know that XORing a variable with itself will result in 0. Since your way doesn't buy anything over i = 0, there's no real reason to use it.

And now your code exhibits undefined behavior because you access i before initializing it.

**wudmx** · 02-27-2004

this took me almost 2 hours, i'm not a c expert. but i want to contribute my results:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define	LEN	10	// number of colums and rows of the matrix
#define	NO_LEN	30	// try to build our number-row til NO_LEN

int matrix[LEN][LEN];
int wrong[] = { 0, 0, 0, 0 };	// contains information which direction can be accessed
								// 0 = accessible, 1 = not accessible

int computeNextPos(int *, int *);
void printMatrix();

int main() {

	int counter = 1, end = 0, pos_x, pos_y, i, j, ret;
	
	for(i=0; i<LEN; i++) {
		for(j=0; j<LEN; j++) {
			matrix[i][j] = 0;
		}
	}

	srand(time(0));
	pos_x = rand() % LEN;
	pos_y = rand() % LEN;
	matrix[pos_x][pos_y] = counter;
	
	while(!end && counter < NO_LEN) {
		
		ret = computeNextPos(&pos_x, &pos_y);
		
		if(ret == 0) {
			end = 1;		
			printf("dead end with counter #%2d\n", counter);

		} else if(ret == 1) {
			matrix[pos_x][pos_y] = ++counter;
			wrong[0] = wrong[1] = wrong[2] = wrong[3] = 0;

		} else {
			continue;		
		}
	}
	printMatrix();	
	return 0;
}

int computeNextPos(int *x, int *y) {

	int rand_value;
	
	rand_value = rand() % 4;

	if(wrong[0] == 1 && wrong[1] == 1 && wrong[2] == 1 && wrong[3] == 1) {
		return 0;
	}
	
	switch(rand_value) {

		case 0:	if( (0 <= *y - 1) && (matrix[*x][*y-1] == 0)) {
					(*y)--;
					return 1;
				} else {
					wrong[rand_value] = 1;
				}
				break;

		case 1:	if( LEN > *x + 1 && matrix[*x+1][*y] == 0) {
					(*x)++;
					return 1;
				} else {
					wrong[rand_value] = 1;
				}
				break;

		case 2:	if( LEN > *y + 1 && matrix[*x][*y+1] == 0) {
					(*y)++;
					return 1;
				} else {
					wrong[rand_value] = 1;
				}
				break;

		case 3:	if( 0 <= *x - 1 && matrix[*x-1][*y] == 0) {
					(*x)--;
					return 1;
				} else {
					wrong[rand_value] = 1;
				}
				break;
					
		default: 
				break;
	}
	
	return 2;
}

void printMatrix() {
	int i, j;
	
	for(i=0; i<LEN; i++) {
		for(j=0; j<LEN; j++) {
			printf("%3d ", matrix[j][i]);
		}
		
		printf("\n");
	}

}

hope this code is okay!

bye
wudmx

**pxleyes** · 02-27-2004

wudmx, i like your code, but I have one question.

Is there anyway to code it without pointers, I dont know them yet, so I am having trouble withthat. Id like it to be written in all functions like you ahve it, but without pointers.

**quzah** · 02-27-2004

Here's my quick hack. It has no backtracking, since that wasn't a requirement. Normally I wouldn't, but since there've been a handfull of others already, why not:

Code:

#include <stdio.h>
#include <time.h>

#define STEPS 30
#define XSIZE 10
#define YSIZE 10
#define NORTH 0
#define EAST  1
#define SOUTH 2
#define WEST  3
#define EXITS 4

int move( unsigned short int m[XSIZE][YSIZE], unsigned short int x, unsigned short int y );
int show( unsigned short int m[XSIZE][YSIZE] );
int main( void )
{

        unsigned short int maze[XSIZE][YSIZE]={0};
        unsigned short int xstart = 0, ystart = 0;
        srand( time( 0 ) );

        xstart = rand() % EXITS;
        ystart = rand() % EXITS;

        move( maze, xstart, ystart );
        show( maze );

        return 0;
}

int move( unsigned short int m[XSIZE][YSIZE], unsigned short int x, unsigned short int y )
{
        static unsigned short int counter = 1;

        if( counter < STEPS && m[x][y] == 0 )
        {
                unsigned short int n=0, e=0, s=0, w=0;
                m[x][y] = counter++;

                n = y > 0 && m[x][y-1] == 0 ? 1 : 0;
                e = x+1 < XSIZE && m[x+1][y] == 0 ? 1 : 0;
                s = y+1 < YSIZE && m[x][y+1] == 0 ? 1 : 0;
                w = x > 0 && m[x-1][y] == 0 ? 1 : 0;

                switch( rand() % EXITS )
                {
                        case 0: if( n ) y--; else if( e ) x++; else
                                if( s ) y++; else if( w ) x--; break;
                        case 1: if( e ) x++; else if( s ) y++; else
                                if( w ) x--; else if( n ) y--; break;
                        case 2: if( s ) y++; else if( w ) x--; else
                                if( n ) y--; else if( e ) x++; break;
                        case 3: if( w ) x--; else if( n ) y--; else
                                if( e ) x++; else if( s ) y++; break;

                }
                move( m, x, y );

        }
        return 0;
}

int show( unsigned short int m[XSIZE][YSIZE] )
{
        unsigned short int x=0, y=0;

        for( y = 0; y < YSIZE; y++ )
        {
                for( x = 0; x < XSIZE; x++ )
                        printf( "[%2d]", m[x][y] );
                printf("\n");
        }
}

Enjoy.

Quzah.
[edit]Removed unused variable.[/edit]
[reedit]Apparently when I pasted in from vi, it left out the show function. Well it's here now... heh.[/reedit]

**pxleyes** · 02-27-2004

My deadline is approaching fast, here is what I have translated, changed for my code. Something is WRONG because it only prints the first and last value, as in 1 and 30. If you guys can fix it in like, o, an hour, I would be so appreciative.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define	N	10	/* number of colums and rows of the array */
#define	MOVES	30	/* try to build our number-row til MOVES */

int a[N][N];
int wrong[] = { 0, 0, 0, 0 };	/* contains information which direction can be accessed */
								/* 0 = accessible, 1 = not accessible */

/*defines array*/
int init_array(int r, int c) {
	for(r=0; r<=9; r++) {
		for(c=0; c<=9; c++) {
			a[c][r]=0;
		}
	}
}

int computeNextPos(int r, int c, int m) {         /* does the walk and combines it all */

	int rand_value;
	
	rand_value = rand() % 4;

	if(wrong[0] == 1 && wrong[1] == 1 && wrong[2] == 1 && wrong[3] == 1) {
		return 0;
	}
	
	switch(rand_value) {

		case 0: if( N > c + 1 && a[r][c+1] == 0) {
                    a[c+1][r]=m;
					return 1;
				} else {
					wrong[rand_value] = 1;
				}
				break;

		case 1: if( N > r + 1 && a[r+1][c] == 0) {
                    a[c][r+1]=m;
					return 1;
				} else {
					wrong[rand_value] = 1;
				}
				break;

		case 2: if( 0 <= r - 1 && a[r-1][c] == 0) {
                    a[c][r-1]=m;
					return 1;
				} else {
					wrong[rand_value] = 1;
				}
				break;

		case 3: if( 0 <= c - 1 && a[r][c-1] == 0) {
                    a[c-1][r]=m;
					return 1;
				} else {
					wrong[rand_value] = 1;
				}
				break;
					
		default: 
				break;
	}
	
	return 2;
 }

void printArray() {
	int i, j;
	
	for(i=0; i<N; i++) {
		for(j=0; j<N; j++) {
			printf("%3d ", a[j][i]);
		}
		
		printf("\n");
	}
	system("PAUSE");
}

int main() {

	int counter = 1, end = 0, x, y, i, j, m, ret;
	
	srand(time(0));
	x = rand() % N;
	y = rand() % N;
	a[x][y] = counter;
	
	while(!end && counter < MOVES) {
		
		ret = computeNextPos(x, y, m);
		
		if(ret == 0) {
			end = 1;		
			printf("dead end with counter #%2d\n", counter);

		} else if(ret == 1) {
			a[x][y] = ++counter;
			wrong[0] = wrong[1] = wrong[2] = wrong[3] = 0;

		} else {
			continue;		
		}
	}
	printArray();
	return 0;
}

**pxleyes** · 02-27-2004

Ok, I took out the init_array inside the position function. Thatt was one problem. Now I am getting 4 1s and a 30. HELP

found another problem, i was looping 30 30 times essentially. taking out the problem

Thread: Help with a random walk

Thread Tools

Search Thread

Display

Help with a random walk

Similar Threads

Lesson #3 - Math

Another brain block... Random Numbers

Request for comments

How do I restart a random number sequence.

Best way to generate a random double?