-
November 21st, 2017, 03:30 AM
#1
Bugfix - BFS Maze, pointer doesn't retain the address (C)
This algorithm is finding a exit path into a labirinth using BFS method(uninformed).
It doesn't run as intended, because of the line "F_start->next=F_stop;" it works at the first iteration (I get smth like 0x24ef0), but at the next one it becomes F_start->next= 0x0. Can someone tell where is the mistake please?
Code:
#include<stdio.h>
#include <time.h>
#include <stdlib.h>
/* 1- up 2-right 3- down 4- left */
int n,m;
int counter=1,Si[10][10],Sf[10][10],test[10][10];
In my example I use o matrix of 5x6 in the file Labirint.txt
Code:
int solution_x[10],solution_y[10],solution_length=0;
int ElementPosition_x, ElementPosition_y;
typedef struct Nodeez
{
int state,predecessor;
int m[10][10];
struct Nodeez *next;
}QUEUE;
QUEUE* F_start=NULL;
QUEUE* T_start=NULL;
QUEUE* F_stop=NULL;
QUEUE* T_stop=NULL;
QUEUE* Node=NULL;
QUEUE* NewNode=NULL;
void Maze_Generation(n,m){
FILE *f;
int i,j,x;
f=fopen("Labirint.txt", "r");
for(i=0;i<n;i++)
for(j=0;j<m;j++){
fscanf(f,"%i",&x);
Si[i][j]= x;
}
printf("Labirinth :\n");
for(i=0;i<n;i++){
for(j=0;j<m;j++){
printf("%i ",Si[i][j]);
}
printf("\n");
}
}
Shows the solution
Code:
void solution(){
int i;
printf("\n\n The solution is :\n\n");
for(i=0;i<solution_length;i++)
printf("(%i,%i) ",solution_x[i],solution_y[i]);
}
If it is on the edges of the labirinth = he got out of the labirinth = thats whats suposed to happen.
7 is the Man that is trying to escape the labirinth eventually
Code:
int testGoal(int a[10][10],int n,int m){
int i,j;
for(j=0;j<m;j++)
if((a[0][j]==7) || (a[n-1][j]==7))
return 1;
for(i=0;i<n;i++)
if((a[i][0]==7) || (a[i][m-1]==7))
return 1;
return 0;
}
QUEUE* initialization(int a[10][10],int S,int P,int n,int m){
QUEUE* Node;
int i,j;
Node=(QUEUE*)malloc(sizeof(QUEUE));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
Node->m[i][j]=a[i][j];
Node->state=S;
Node->predecessor=P;
Node->next=NULL;
return Node;
}
QUEUE* copy_Node(QUEUE* Node)
{
int i,j;
QUEUE* aux = (QUEUE*)malloc(sizeof(QUEUE));
for(i=0;i<n;i++)
for(j=0;j<m;j++)
aux->m[i][j]=Node->m[i][j];
aux->predecessor=Node->predecessor;
aux->state=Node->state;
return aux;
}
void add_QUEUE_Frontier(QUEUE* start,QUEUE* stop,QUEUE* Node){
if(F_start==NULL && F_stop==NULL){
QUEUE* aux = copy_Node(Node);
F_start=(QUEUE*)malloc(sizeof(QUEUE));
F_stop=(QUEUE*)malloc(sizeof(QUEUE));
F_start=aux;
F_stop=aux;
F_start->next=NULL;
F_start->next=F_stop;
F_stop->next=NULL;
}
else{
QUEUE* aux = copy_Node(Node);
F_stop->next=aux;
F_stop=aux;
}
}
void add_QUEUE_Territory(QUEUE* start,QUEUE* stop,QUEUE* Node){
if(T_start==NULL && T_stop==NULL){
QUEUE* aux = copy_Node(Node);
T_start=aux;
T_start->next=T_stop;
T_stop=T_start;
}
else{
QUEUE* aux = copy_Node(Node);
T_stop->next=aux;
T_stop=aux;
}
}
void CreateTestMatrix(int A[10][10], int n, int m){
int i,j;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
test[i][j]=A[i][j];
}
void ElementPosition(int A[10][10],int n,int m){
int i,j;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if(A[i][j]==7){
ElementPosition_x=i;
ElementPosition_y=j;
}
}
int Can_I_Muve(int A[10][10], int muve, int n, int m){
int pozx = ElementPosition_x;
int pozy = ElementPosition_y;
if(muve==1 && (pozx==0 || A[pozx-1][pozy]==1))
return 0;
if(muve==2 && (pozy==m-1 || A[pozx][pozy+1]==1))
return 0;
if(muve==3 && (pozx==n-1 || A[pozx+1][pozy]==1))
return 0;
if(muve==4 && (pozy==0 || A[pozx][pozy-1]==1))
return 0;
return 1;
}
If I reach this function(executeMuveInTest), it means I sucessifully passed the "Can_I_Muve" function, so I must have a new part of the path that leads to the labirinth's exit
I memorize the solution via "executeMuveInTest" function
Code:
void executeMuveInTest(int muve){
solution_length++;
int pozx = ElementPosition_x;
int pozy = ElementPosition_y;
if(muve==1){
test[pozx][pozy]=test[pozx-1][pozy];
test[pozx-1][pozy]=7;
solution_x[solution_length]=pozx-1;
solution_y[solution_length]=pozy;
}
if(muve==2){
test[pozx][pozy]=test[pozx][pozy+1];
test[pozx][pozy+1]=7;
solution_x[solution_length]=pozx;
solution_y[solution_length]=pozy+1;
}
if(muve==3){
test[pozx][pozy]=test[pozx+1][pozy];
test[pozx+1][pozy]=7;
solution_x[solution_length]=pozx+1;
solution_y[solution_length]=pozy;
}
if(muve==4){
test[pozx][pozy]=test[pozx][pozy-1];
test[pozx][pozy-1]=7;
solution_x[solution_length]=pozx;
solution_y[solution_length]=pozy-1;
}
}
Checks if it repeats in the Territory or in the Frontier
Code:
int Check_If_It_Repeats(QUEUE *Fs,int A[10][10],int n,int m){
int i,j;
QUEUE *F1_s;
for(F1_s=Fs;F1_s;F1_s=F1_s->next)
if(CompareMatrix(F1_s->m,A,n,m))
return 1;
return 0;
}
0 - Different 1 - Identical (to CompareMatrix)
Code:
int CompareMatrix(int A[10][10],int B[10][10],int n,int m){
int i,j;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
if (A[i][j]!=B[i][j])
return 0;
return 1;
}
int main() {
int muve;
printf("How many lines does the labirinth have ?\n");
scanf("%i",&n);
printf("How many columns does the labirinth have ?\n");
scanf("%i",&m);
printf("The labirinth has %i lines and %i columns\n",n,m);
Maze_Generation(n,m);
if(testGoal(Si,n,m)==1)
solution();
Node=initialization(Si,1,0,n,m);
add_QUEUE_Frontier(F_start,F_stop,Node);
do{
if(F_start==NULL){
printf("FAIL");
break;
}
Node=copy_Node(F_start);
F_start=F_start->next;
Node->next=NULL;
add_QUEUE_Territory(T_start,T_stop,Node);
for(muve=1;muve<=4;muve++){
CreateTestMatrix(Node->m,n,m);
ElementPosition(test,n,m);
if(Can_I_Muve(test,muve,n,m)==1){
executeMuveInTest(muve);
In the next if it checks if it reapeats in the territory or in frontier,both = 0 means no reapeat
Code:
if(Check_If_It_Repeats(F_start,test,n,m)==0 && Check_If_It_Repeats(T_start,test,n,m)==0){
if(testGoal(test,n,m)==1){
solution();
}
counter++;
NewNode=initialization(test,counter,Node->state,n,m);
add_QUEUE_Frontier(F_start,F_stop,NewNode);
}
}
}
}
while(testGoal(test,n,m)==0); ///if solution was found
return 0;
}
The matrix that I run :
Code:
1 1 0 0 1 0
0 0 1 0 1 1
1 1 0 7 1 1
0 0 0 1 1 1
1 1 0 0 1 1
Thanks !
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|