Maze Escape

#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);

{
{
fprintf(f_explore,"%c",land[i][j]);
fprintf(log,"%c",land[i][j]);

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

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);

{
{
fprintf(f_explore,"%c",land[i][j]);
}
fprintf(f_explore,"\n");
}

}

}

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)
{
else
else
else
}
else
if(strcmp(facing,"LEFT")==0)
{
else
else
else
}
else
if(strcmp(facing,"RIGHT")==0)
{
else
else
else
}

}

/**********************************/
//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;
{
{
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;
{
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;
{
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;
}
*/

Maze Escape

Uploaded by

Copyright:

Available Formats

Maze Escape

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Maze Escape

Uploaded by

Copyright:

Available Formats

What is the algorithm trying to solve?

How does it represent the maze?

#include <stdio.

You might also like