C program : Maze shortest path

ralbhat · Jan 30, 2010

Hey,

I've made a program to find the shortest path in a maze.. doesn't work though. Gives the weirdest error (NEVER seen this one before) on linux.. haven't tested it on windows. Help me!:

Code:

// Maze is :

//

//   __________

//  |O|X|X|  |  |  |

//  |   |  |  |  |X|  |

//  |   |  |  |X|X|  |

//  |   |  |  |X|X|  |

//  |   |X|X|X|X|  |

//  |_ |_ |_| _|_|W|

//

//  where X means that passing is not possible, and blank means passing is possible. O is the starting point,

//  and W is the Final position The shortest path solution for this maze would, hence, be :

//  0,0

//  0,1

//  0,2

//  0,3

//  0,4

//  0,5

//  1,5

//  2,5

//  3,5

//  4,5

//  5,5

//  The top-left corner is 0,0 and the bottom right is 5,5 in numbering.

#include<stdio.h>

int maze[6][6] = {{0,1,1,0,0,0},{0,0,0,0,1,0},{0,0,0,1,1,0},{0,0,0,1,1,0},{0,1,1,1,1,0},{0,0,0,0,0,0}};

int start[2] = {0,0},end[2]={5,5};

typedef struct n{

  int i,j;

  int *history;

  int lenh;

} node;

typedef struct s{

  node *n;

  struct s *next,*prev;

}list;

node *ans = NULL;

list *stack = NULL;

list *ltop;

int found = 0;

void push(node *new);

list *move(list *start);

int isinhistory(int history[],int len,int tofind[2]);

int isfinal(node *candidate);

//void view();

int main(void){

  int i;

  list *lstart;

  node *abc = (node*)malloc(sizeof(node));

  abc->i = start[0];

  abc->j = start[1];

  abc->history = NULL;

  abc->lenh=0;

  stack = (list *)malloc(sizeof(list));

  stack->next = NULL;

  stack->n = abc;

  lstart=stack;

  ltop = stack;

  while(!found) lstart = move(lstart);

  if (found == 1)

    for(i=0;i<(ans->lenh);i++)

     printf("%d,%d\n",ans->history[2*i],ans->history[2*i+1]);

  else if (found == -1)

    printf("No route!");

}

// ----------- isfinal

int isfinal(node *candidate){

  if(candidate->i == end[0])

    if(candidate->j == end[1])

      return 1;

  return 0;

}

// ----------- isinhistory

int isinhistory(int history[],int len,int tofind[2]){

  int i;

  for(i = 0;i<len;i++)

    if(tofind[0] == history[2*i] && tofind[1]==history[2*i+1]) return 1;

  return 0;

}

// ---------- push

void push(node *new){

  list *top = (list *)malloc(sizeof(list));

  top->n=new;

  top->next=ltop;

  top->prev = NULL;

  ltop->prev = top;

  ltop=top;

}

// ---------- move

list *move(list *start){

//  printf("reached move");

  int left[]={(start->n->i)-1,start->n->j},right[]={(start->n->i)+1,start->n->j};

  int up[]={start->n->i,(start->n->j)-1},down[] = {start->n->i,(start->n->j)+1};

  int i;

  node *new = (node *)malloc(sizeof(node));

//  printf("1");

  if((start->n->i)-1>0 && !(isinhistory(start->n->history,start->n->lenh,left))){

    new->i = (start->n->i)-1;

    new->j = (start->n->j);

    new->history = (int *)malloc(2*(start->n->lenh+1));

    new->lenh = (start->n->lenh)+1;

    for(i=0;i<(start->n->lenh);i++){

	new->history[2*i] = start->n->history[2*i];

	new->history[2*i+1] = start->n->history[2*i+1];

    }

    new->history[2*i] = start->n->i;

    new->history[2*i+1] = start->n->j;

    if(isfinal(new)){

      found = 1 ;

      ans= new;

    }

    else push(new);

  }

//  printf("2");

  if((start->n->i)+1<6 && !(isinhistory(start->n->history,start->n->lenh,right))){

    new->i = start->n->i+1;

    new->j = start->n->j;

    new->history = (int *)malloc(2*(start->n->lenh+1));

    new->lenh = (start->n->lenh)+1;

    for(i=0;i<(start->n->lenh);i++){

        new->history[2*i] = start->n->history[2*i];

        new->history[2*i+1] = start->n->history[2*i+1];

    }

    new->history[2*i] = start->n->i;

    new->history[2*i+1] = start->n->j;

    if(isfinal(new)){

      found=1 ;

      ans= new;

    }

    else push(new);

  }

//  printf("3");

  if((start->n->j)-1>0 && !(isinhistory(start->n->history,start->n->lenh,up))){

    new->i = start->n->i;

    new->j = start->n->j-1;

    new->history = (int *)malloc(2*(start->n->lenh+1));

    new->lenh = (start->n->lenh)+1;

    for(i=0;i<(start->n->lenh);i++){

        new->history[2*i] = start->n->history[2*i];

        new->history[2*i+1] = start->n->history[2*i+1];

    }

    new->history[2*i] = start->n->i;

    new->history[2*i+1] = start->n->j;

    if(isfinal(new)){

      found=1 ;

      ans= new;

    }

    else push(new);

  }

//  printf("4");

  if((start->n->j)+1<6 && !(isinhistory(start->n->history,start->n->lenh,down))){

    new->i = start->n->i;

    new->j = start->n->j+1;

    new->history = (int *)malloc(2*(start->n->lenh+1));

    new->lenh = (start->n->lenh)+1;

    for(i=0;i<(start->n->lenh);i++){

        new->history[2*i] = start->n->history[2*i];

        new->history[2*i+1] = start->n->history[2*i+1];

    }

    new->history[2*i] = start->n->i;

    new->history[2*i+1] = start->n->j;

    if(isfinal(new)){

      found =1 ;

      ans= new;

    }

    else push(new);

  }

  if(start==ltop) found = -1;

  list *temp,*top = ltop;

  temp = start;

  start = start->prev;

  start->next = NULL;

  free(temp->n->history);

  free(temp);

//  view();

  return start;

}

// ---- view

/*void view(){

  int dummy;

  list *top = ltop;

  while( top->next !=NULL){

    printf("\n%d\n",top->n->lenh);

    top=top->next;

  }

  scanf("%d",&dummy);

}*/

I've used a stack to keep a list of what I haven't gone through in the maze yet, and the history is used to know what i've already visited. I tried linking my stack both ways, too.

Oh.. there's the image.

HELP!

blufox · Jan 30, 2010

You are freeing something which you should not.

double free?

Did not go through the code fyi.

gamingstill · Jan 31, 2010

use neural networks to solve dis kinda Problems...:hap5::cool2:

hyeah:
it rocks.....

vishalrao · Jan 31, 2010

or find open source freely available code to "study and learn" from . aka plagiarise

j/k

Sanjeet Arora · Jan 31, 2010

next time u write any program make sure that u make most use of comments, so that it is interpretable what u want from each part. It would also make debugging easier.

ralbhat · Jan 31, 2010

Hey guys!

I managed to find an alternate way using doubly-linked lists and a BFS. Thanks anyway!

Sanjeet Arora · Feb 1, 2010

so post it....

booo · Feb 1, 2010

you should learn using gdb and then run it in the debugger. dont forget to add -g compiler option.

the error is happening because you are sending invalid value to free. you are unable to see the function names because you did not enable -g switch so its unable to find the function symbol information.

Just add -g switch to the compilation and you will see which function is actually faulting.

hope that helps

ralbhat · Feb 3, 2010

ok.. here's the code i used in the end :

Code:

// The program randomly populates a 6X6 array with 1's and 0's. It then randomly chooses a start point and an

// end point. It then prints the maze, the coordinates of the start and end points, and the path from the start

// point to the end point.

#include<stdio.h>

#include<stdlib.h>

// ------ Define the structure of a node, i.e. the block in the maze that we consider.

typedef struct n{

  int i,j;

  struct n *prev;

} node;

node *ans;

// -------- Define the maze and the start and end points

int maze[6][6];

int start[2],end[2];

int found = 0;

// Randomly generate this information

void populate(){

  int ch,i,j;

  srand(time(NULL));

  for(i = 0; i<6;i++){

    for(j=0;j<6;j++){

      maze[i][j] = rand()%2;

    }

  }

  start[0] = rand()%6;

  start[1] = rand()%6;

  end[0] = rand()%6;

  end[1] = rand()%6;

  maze[start[0]][start[1]] = 0;

  maze[end[0]][end[1]] = 0;

  printf("The start point is: %d,%d\nThe end point is: %d,%d\n",start[0]+1,start[1]+1,end[0]+1,end[1]+1);

}

// For printing the maze :

void printmaze(){

  int i=0,j=0;

  for(i=0;i<6;i++){

    for(j=0;j<6;j++){

      printf("%d   ",maze[i][j]);

    }

  printf("\n");

  }

}

// ------- We will maintain the levels of nodes in a stack; one present and one future level. Define the stack structure.

typedef struct s{

  node *n;

  struct s *next;

} stack;

// ------ The top pointers of the two stacks that we will make.

stack *top_cur,*top_fut;

// ------ Push() for the stack; we will be pushing nodes into the future stack

void push(node *n){

  stack *new = (stack*)malloc(sizeof(stack));

  new->n = n;

  new->next = top_fut;

  top_fut = new;

}

// ----- isfinal() takes a node and checks if it is the final node.

int isfinal(node *n){

  if ( (n->i)==end[0] && (n->j) == end[1] ) return 1;

  return 0;

}

// ----- move() will analyze the surrent stack and will place all possible futures into the future stack. The future stack then becomes the current stack till

// ----- the final position is reached.

void move(){

  int counter=0;

  top_fut = (stack *)malloc(sizeof(stack));

  top_fut->n = NULL;

  top_fut->next = NULL;

  while(top_cur->next!=NULL){

    node *con;

    con = top_cur->n;

    if(isfinal(con)){

      found=1;

      ans = con;

    }

    int left[] = {con->i-1,con->j},right[]={con->i+1,con->j},up[]={con->i,con->j-1},down[]={con->i,con->j+1};

    if(left[0]>=0 && maze[left[0]][left[1]] == 0){

      node *new=(node*)malloc(sizeof(node));

      new->i = left[0];

      new->j = left[1];

      new->prev = con;

      maze[new->i][new->j]=1;

      push(new);

      counter++;

    }

    if(right[0]<=5 && maze[right[0]][right[1]] == 0){

      node *new = (node *)malloc(sizeof(node));

      new->i=right[0];

      new->j=right[1];

      new->prev = con;

      maze[right[0]][right[1]]=1;

      push(new);

      counter++;

    }

    if(up[1]>=0 && maze[up[0]][up[1]] == 0){

      node *new=(node*)malloc(sizeof(node));

      new->i = up[0];

      new->j = up[1];

      new->prev = con;

      maze[new->i][new->j]=1;

      push(new);

      counter++;

    }

    if(down[1]<=5 && maze[down[0]][down[1]] == 0){

      node *new=(node*)malloc(sizeof(node));

      new->i = down[0];

      new->j = down[1];

      new->prev = con;

      maze[new->i][new->j]=1;

      push(new);

      counter++;

    }

    top_cur = top_cur->next;

  }

  top_cur = top_fut;

  if(counter ==0) found = -1;

}

// ----- view() to view generations

void view(){

 if(top_fut->next!=NULL){

  stack *temp = top_fut;

  printf("\n");

  while(temp->next != NULL){

   printf("%d,%d\t",temp->n->i,temp->n->j);

   temp = temp->next;

  } 

  printf("\n\n");

 }

}

int main(void){

  populate();

  printmaze();

  int counter=0;

  top_cur = (stack*)malloc(sizeof(stack));

  top_cur->n = NULL;

  top_cur->next = NULL;

  node *first = (node *)malloc(sizeof(node));

  first->i = start[0];

  first->j = start[1];

  first->prev = NULL;

  maze[start[0]][start[1]] = 1;

  stack *once=(stack *)malloc(sizeof(stack));

  once->n = first;

  once->next = top_cur;

  top_cur = once;

  once = NULL;

  free(once);

  do{

    move();

//    view();

  }while(found == 0);

  

//  printf("%d,%d\n",ans->i,ans->j);

//  printf("%d\n",found);

//  printf("Out of the while loop\n");

  if(found == 1){

    top_fut = (stack *)malloc(sizeof(stack));

    top_fut->next = NULL;

    top_fut->n = NULL;

//    printf("Done allotting\n");

    while(ans->prev!=NULL){

      push(ans);

      ans = ans->prev;

    }

//    printf("Done ans=ans->prev\n");

    printf("Shortest path :\n");

    printf("%d,%d\n",start[0]+1,start[1]+1);

    while(top_fut->next!=NULL){

      printf("%d,%d\n",top_fut->n->i+1,top_fut->n->j+1);

      top_fut = top_fut->next;

    }

//    printf("Answered\n");

  }

  else

    printf("No path found!\n");

  return 0;

}

Search

Search

C program : Maze shortest path

ralbhat

Inactive

blufox

Inactive

gamingstill

Gamer inside

vishalrao

Global Moral Police

Sanjeet Arora

Inactive

ralbhat

Inactive

Sanjeet Arora

Inactive

booo

BA BA BA BABANANA

ralbhat

Inactive