[go: up one dir, main page]
Scribd
Upload
349 views23 pages

Maze Escape

This C code defines functions for navigating a maze using breadth-first search. It includes functions to read a maze from a file, perform BFS to find the next unexplored point or exit, backtrack to determine the next movement, and write the updated maze and position to a file. Key data structures include a queue to track frontier nodes in BFS, and an array to track goal locations like unexplored points and the exit.

Uploaded by

Himansu Saha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
349 views23 pages

Maze Escape

This C code defines functions for navigating a maze using breadth-first search. It includes functions to read a maze from a file, perform BFS to find the next unexplored point or exit, backtrack to determine the next movement, and write the updated maze and position to a file. Key data structures include a queue to track frontier nodes in BFS, and an array to track goal locations like unexplored points and the exit.

Uploaded by

Himansu Saha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 23

#include <stdio.

h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAX_R 100
#define MAX_C 100
#define MAX_C 100

char input_maze[3][3];
char land[MAX_R][MAX_C];
char facing[10];
int bot_x,bot_y;
char direction_to_move[20];

void transpose(char facing[])
{
//Rotate the Input Maze so that it faces UP
int i,j;
char temp[3][3];

if(strcmp(facing,"UP")==0)
{
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
temp[i][j]=input_maze[i][j];
}
}
else
if(strcmp(facing,"DOWN")==0)
{
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
temp[i][j]=input_maze[3-i-1][3-j-1];
}
}
else
if(strcmp(facing,"LEFT")==0)
{
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
temp[i][j]=input_maze[j][3-i-1];
}
}
else
if(strcmp(facing,"RIGHT")==0)
{
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
temp[i][j]=input_maze[3-j-1][i];
}
}

for(i=0;i<3;i++)
for(j=0;j<3;j++)
input_maze[i][j]=temp[i][j];

}

void render_new_information_on_land()
{
int top_left_x=bot_x-1;
int top_left_y=bot_y-1;
int i,j;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
land[top_left_x+i][top_left_y+j]=input_maze[i][j];
// if(land[top_left_x+i][top_left_y+j]=='b')
// land[top_left_x+i][top_left_y+j]='-';
}
}

}


void read_land_from_file()
{
FILE *f_explore;
int i,j;
int line_no=0;
char str[200];

if((f_explore=fopen("orion_maze_escape.txt","r"))!=NULL)
{
fscanf(f_explore," %d %d %s",&bot_x,&bot_y,&facing);

while(fscanf(f_explore," %s",&str[0])>0&&line_no<MAX_C)
{
for(i=0;i<MAX_C;i++)
land[line_no][i]=str[i];
line_no++;
}

fclose( f_explore );
}
else
{
for(i=0;i<MAX_R;i++)
for(j=0;j<MAX_C;j++)
land[i][j]='X';

bot_x=MAX_R/2;
bot_y=MAX_C/2;
strcpy(facing,"UP");

}
}


void write_land_to_file()
{
FILE *f_explore;
FILE *log;
log=fopen("n_maze_escape.txt","a");
int i,j;
if((f_explore=fopen("orion_maze_escape.txt","w"))!=NULL)
{
fprintf(f_explore,"%d %d %s\n",bot_x,bot_y,direction_to_move);
fprintf(log,"%d %d %s\n",bot_x,bot_y,direction_to_move);

for(i=0;i<MAX_R;i++)
{
for(j=0;j<MAX_C;j++)
{
fprintf(f_explore,"%c",land[i][j]);
fprintf(log,"%c",land[i][j]);

}
fprintf(f_explore,"\n");
fprintf(log,"\n");
}

fclose( f_explore );
fclose( log );
}

}

void write_land_to_file2()
{
FILE *f_explore;
int i,j;
if((f_explore=fopen("orion_maze_escape.dat","w"))!=NULL)
{
fprintf(f_explore,"%d %d %s\n",bot_x,bot_y,direction_to_move);

for(i=0;i<MAX_R;i++)
{
for(j=0;j<MAX_C;j++)
{
fprintf(f_explore,"%c",land[i][j]);
}
fprintf(f_explore,"\n");
}

fclose( f_explore );
}

}


char next_move[20];

void get_next_facing()
{
if(strcmp(facing,"UP")==0)
{
if(strcmp(direction_to_move,"UP")==0)
strcpy(next_move,"UP");
else
if(strcmp(direction_to_move,"DOWN")==0)
strcpy(next_move,"DOWN");
else
if(strcmp(direction_to_move,"LEFT")==0)
strcpy(next_move,"LEFT");
else
if(strcmp(direction_to_move,"RIGHT")==0)
strcpy(next_move,"RIGHT");
}
else
if(strcmp(facing,"DOWN")==0)
{
if(strcmp(direction_to_move,"UP")==0)
strcpy(next_move,"DOWN");
else
if(strcmp(direction_to_move,"DOWN")==0)
strcpy(next_move,"UP");
else
if(strcmp(direction_to_move,"LEFT")==0)
strcpy(next_move,"RIGHT");
else
if(strcmp(direction_to_move,"RIGHT")==0)
strcpy(next_move,"LEFT");
}
else
if(strcmp(facing,"LEFT")==0)
{
if(strcmp(direction_to_move,"UP")==0)
strcpy(next_move,"RIGHT");
else
if(strcmp(direction_to_move,"DOWN")==0)
strcpy(next_move,"LEFT");
else
if(strcmp(direction_to_move,"LEFT")==0)
strcpy(next_move,"UP");
else
if(strcmp(direction_to_move,"RIGHT")==0)
strcpy(next_move,"DOWN");
}
else
if(strcmp(facing,"RIGHT")==0)
{
if(strcmp(direction_to_move,"UP")==0)
strcpy(next_move,"LEFT");
else
if(strcmp(direction_to_move,"DOWN")==0)
strcpy(next_move,"RIGHT");
else
if(strcmp(direction_to_move,"LEFT")==0)
strcpy(next_move,"DOWN");
else
if(strcmp(direction_to_move,"RIGHT")==0)
strcpy(next_move,"UP");
}


}

/**********************************/
//COMPUTE PATH TO NEXT UNEXPLORED POINT (X) or EXIT (e) using BFS

/*******/
//STRUCTURE TO KEEP TRACK OF GOALS = X and e
struct GOALS
{
int x;
int y;
}goal[100];

int goal_N=0;

void add_goal(int x,int y)
{
goal[goal_N].x=x;
goal[goal_N].y=y;
goal_N++;
}

//END


struct QUEUE
{
int x;
int y;
}stk[MAX_R*MAX_C*10];

int stk_N=0;
int stk_beg=0;

void push(int x,int y)
{
stk[stk_N].x=x;
stk[stk_N].y=y;
stk_N++;
}
void pop(int *x,int *y)
{
*x=stk[stk_beg].x;
*y=stk[stk_beg].y;
stk_beg++;
}

struct NODE
{
int visited;
int distance;
int visitedfrom_x;
int visitedfrom_y;
}node[MAX_R][MAX_C];

void init_bfs()
{
int i,j;
for(i=0;i<MAX_R;i++)
{
for(j=0;j<MAX_C;j++)
{
node[i][j].visited=0;
node[i][j].distance=0;
}
}

}

void insert_node(int to_x,int to_y,int from_x,int from_y)
{

if(to_x>=0 && to_x<MAX_R && to_y>=0 && to_y<MAX_C &&
node[to_x][to_y].visited==0)
{
if(land[to_x][to_y]=='-')
{
//INTERMEDIATE PATH
node[to_x][to_y].visited=1;
node[to_x][to_y].distance=node[from_x][from_y].distance+1;
node[to_x][to_y].visitedfrom_x=from_x;
node[to_x][to_y].visitedfrom_y=from_y;
push(to_x,to_y);
}
else
if(land[to_x][to_y]=='X'||land[to_x][to_y]=='e')
{
//GOAL -- DO NOT ADD TO QUEUE
node[to_x][to_y].visited=1;
node[to_x][to_y].distance=node[from_x][from_y].distance+1;
node[to_x][to_y].visitedfrom_x=from_x;
node[to_x][to_y].visitedfrom_y=from_y;
//ADD to GOAL
add_goal(to_x,to_y);
}
}
}



void get_next_goal(int *x,int *y)
{
int min_dist=99999;
int index=0;
int i;
int p,q,d;
for(i=0;i<goal_N;i++)
{
p=goal[i].x;
q=goal[i].y;
d=node[p][q].distance;
if(land[p][q]=='e')
{
*x=p;
*y=q;
return;
}
if(d<min_dist)
{
min_dist=d;
index=i;
}
}
*x=goal[index].x;
*y=goal[index].y;
}

void get_next_goal2(int *x,int *y)
{
//ADD HEURISTICS
//Walk closer to the wall #
//Walk to the X having maximum number of adjacent #
int max_wall=0;
int index=0;
int i,j,k;
int p,q,d;
for(i=0;i<goal_N;i++)
{
p=goal[i].x;
q=goal[i].y;
d=0;
for(j=-1;j<=1;j++)
{
for(k=-1;k<=1;k++)
{
if(land[p+j][q+k]=='#')
d++;
}
}
if(land[p][q]=='e')
{
*x=p;
*y=q;
return;
}
if(d>max_wall)
{
max_wall=d;
index=i;
}
}
*x=goal[index].x;
*y=goal[index].y;
}

void get_next_goal3(int *x,int *y)
{
//HEURISTICS
//Go to X which is furthest from start point (assuming exit will be places furthest
from entry)
int max_dist=0;
int index=0;
int i;
int p,q,d;
int startx=MAX_R/2;
int starty=MAX_C/2;
for(i=0;i<goal_N;i++)
{
p=goal[i].x;
q=goal[i].y;
d=(p-startx)*(p-startx)+(q-starty)*(q-starty);
if(land[p][q]=='e')
{
*x=p;
*y=q;
return;
}
if(d>max_dist)
{
max_dist=d;
index=i;
}
}
*x=goal[index].x;
*y=goal[index].y;
}

void next_visit(int goalx,int goaly,int* nextx, int* nexty)
{
//BACKTRACK

int next_x,next_y;
int curr_x,curr_y;
int prev_x,prev_y;

curr_x=goalx;
curr_y=goaly;

while(curr_x!=bot_x||curr_y!=bot_y)
{
prev_x=curr_x;
prev_y=curr_y;
next_x=node[curr_x][curr_y].visitedfrom_x;
next_y=node[curr_x][curr_y].visitedfrom_y;
curr_x=next_x;
curr_y=next_y;
}

*nextx=prev_x;
*nexty=prev_y;

}


void bfs()
{
//logic here
int i,j;
int x,y;
int found=0;
init_bfs();

push(bot_x,bot_y);
node[bot_x][bot_y].visited=1;


while(stk_N>stk_beg&&!found)
{
pop(&x,&y);

if(land[x][y]=='e')
{
found=1;
break;
}

insert_node(x-1,y,x,y);
insert_node(x,y-1,x,y);
insert_node(x,y+1,x,y);
insert_node(x+1,y,x,y);

}

}


//END BFS
/*****************************************************/


void get_destination()
{


int p,q;
int m,n;
bfs();
get_next_goal3(&m,&n);
next_visit(m,n,&p,&q);

//printf("%d %d\n",p,q);

if(p==bot_x+1)
{
strcpy(direction_to_move,"DOWN");
bot_x++;
}
if(p==bot_x-1)
{
strcpy(direction_to_move,"UP");
bot_x--;
}
if(q==bot_y+1)
{
strcpy(direction_to_move,"RIGHT");
bot_y++;
}
if(q==bot_y-1)
{
strcpy(direction_to_move,"LEFT");
bot_y--;
}

get_next_facing();

// if(strcmp(facing,"UP")==0)
// bot_x--;
// if(strcmp(facing,"DOWN")==0)
// bot_x++;
// if(strcmp(facing,"LEFT")==0)
// bot_y--;
// if(strcmp(facing,"RIGHT")==0)
// bot_y++;


}


int main()
{

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int bot_id;
int i,j,k,l;
char str[200];
scanf(" %d",&bot_id);
for(i=0;i<3;i++)
{
scanf("%s",&str);
for(j=0;j<3;j++)
input_maze[i][j]=str[j];
}


/* ALGO:
Create a Land with all invisible...
XXXXXXXXXXXXXXX
XXXXXXXXXXXXXXX
XXXXXXXXXXXXXXX
XXXXXXXXXXXXXXX

Move to explore as much of unexplored as possible.
When you find the door [e], ENTER.
*/

read_land_from_file();
transpose(facing); // Make the input maze face UP by reading the last direction the bot was
facing from 'orion_maze_escape.dat'
render_new_information_on_land();
get_destination();
write_land_to_file();
printf("%s\n",next_move);

return 0;
}

/*
void display_maze()
{
int i,j;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
printf("%c",input_maze[i][j]);
printf("\n");
}
printf("\n");
}

int main_test_transpose()
{
//TEST TRANSPOSE
char str[200];
char face[200];
int i,j;
for(i=0;i<3;i++)
{
scanf("%s",&str);
for(j=0;j<3;j++)
input_maze[i][j]=str[j];
}
scanf("%s",&face);

transpose(face);
display_maze();


return 0;
}
*/

You might also like