• 0

Maze in C


Question

well, we have a program assignment due for unix systems.. he says as long as we cite where we get our code, we can get external code.. i'd rather just make my own... but i'm having trouble thinking of a way to implement this.. any help with the pseudo code would be great...

"There are several simple algorithms for walking through a maze that guarantee finding the exit, if a path exists. For example, place your right hand on the wall to your right and walk forward. Never remove your hand from the wall. If the maze turns to the right, you follow the maze. There may be a shorter path than the one you have taken, but in this way you are guaranteed to get out of the maze. In this algorithm, if you exit from the maze through the entrance, this means that the path from the entrance to the exit does not exist."

Link to comment
Share on other sites

9 answers to this question

Recommended Posts

  • 0

I can see the general idea. If your hand never leaves the wall, then even if you enter a dead end you will come back, because

| ^
| ?< < < <
|-----------
 ? ? ? ? ? ? ? | ^ 
|-----------
| ^ ?> > >
| ^
| ^

and if there is indeed no exit what happens is this

Entrance ? Exit
 ?| ? ? ? ? ? ?| ^
 ?| ? ? ? ? ? ?| ^
 ?| ? ? ? ? ? ?| ^
 ?| ? ? ? ? ? ?| ^
 ?| ? ? ? ? ? ?| ^
 ?| ? ? ? ? ? ?| ^
 ?| ? ? ? ? ? ?| ^
 ?| ? ? ? ? ? ?| ^
(Rest of maze)

(there should be arrows pointing down on the "entrance wall"...)

What you basically tell your program to do is to follow the wall on the right. Always. Forget the corridors, forget the left wall. Concentrate on the right wall.

If something like this happens

| ? ? |
| ? ? |----------
| ? ? |
| ? ? | ? ?---------
| ? ? | 
| ? ? |---------
| ? ? |
| ? ? |

you don't turn right, because your wall still goes on. So you should, regardless of whether the wall is connected to another wall, do this BY THIS ORDER (correct me if I'm wrong)

1) If the wall turns to the left, follow it. (Figure 1)

2) If the wall keeps on in a straight lineEdit: (case above)

3) If the wall turns to the right, follow it. (Figure 2)

Edit:I had previously put 2) first, but I though about it and it isn't.

Figure 1

____________________
 ?< ?< ? <|
 ? ? ? ??^| ? ? ? ? ? ____
| ? ? ? ?|
| ? ? ? ^|____________
| ? ? ? ?|
| ? ? ? ?|
| ? ? ? ^|
| ? ? ? ?|
| ? ? ? ?|

Figure 2

_________________________

? ? ? ?

? ? ? ? ? ? ? ? ?

? ? ? ?

? ? ? ? ? ? ? ?> ? > ?>

______ ? ? ? ? ?____________

? ? ?| ? ? ? ^|

? ? ?| ? ? ? ?|

? ? ?| ? ? ? ^|

? ? ?| ? ? ? ?|

? ? ?| ? ? ? :whistle:

I can't really help you with the code right now, but I think that's the idea.

Edit:After some time I finally got the "images" right :whistle:

Edited by anog
Link to comment
Share on other sites

  • 0

Here's how I would see it going down, and remember that I don't write code that often, so this may not be a perfect explanation.

Assume that this maze is made up of "cells", and that the character would move from cell to cell. The only information that you need about the character is what cell he's in, and what direction he's facing. Each time he gets to a new cell he would do the follow checks:

If there's no wall to his right

----Turn 90 degrees to the right and move one cell forward

Else if there's no wall in front of him

----Move one cell forward

Else if there's no wall to his left

----Turn 90 degrees to the left and move one cell forward

Else

----Turn 180 degrees and move on cell forward

Eventually he would get to the exit with this pattern.

If he ever reaches the coordinates of his starting location again, then the maze has no exit.

[Edit] Oops, fixed a big mistake. :p

[Edit again] Fixed some more mistakes.

Link to comment
Share on other sites

  • 0

Yeah, that's another way of looking at it.

You way is probably simpler than mine, since I'm looking only at the wall. Your "cell system" is easier to understand and implement.

The basic idea is the same, though... :laugh:

Link to comment
Share on other sites

  • 0

The only problem with my approach would actually be getting the maze into the cells format - that would take a pretty good amount of time. But then again so would any other way, unless you're required to also program a graphic analyzer to convert the maze into an understandable format.

Link to comment
Share on other sites

  • 0

I was thinking an array of structs which each have 4 ints named "top", "bottom", "left" and "right", being 1 or 0 for whether or not there's a wall there.

But that's probably because I don't know enough about C++ yet.

Link to comment
Share on other sites

  • 0

K.I.S.S. is my only reason. I'd get too confused with a complex structure. :)

if the array looked like this, you really wouldn't need to differentiate left or right(relative), but north, south, east, west...

000010000
011110000
010011000
010001000
010000010
011100010
010000010
011100010
010000010
011111110
000010000

Link to comment
Share on other sites

  • 0
I was thinking an array of structs which each have 4 ints named "top", "bottom", "left" and "right", being 1 or 0 for whether or not there's a wall there.

But that's probably because I don't know enough about C++ yet.

yeah, first i load in an array from a file that looks like this:

111111111111

111111111111

111111111111

111111111111

111111101111

000111101111

110111100011

110111101011

110111101011

110000001000

111111011111

111111111111

while loading from the file, i also load everything into a struct.. you just gave me the idea to add an element of direction to the struct .. that oughtta get this program squared away.

thanks.

Link to comment
Share on other sites

  • 0

okay.. i've made several algorithms to try and do it.. still no luck.. here's my current code, can anyone see where i'm going wrong?

#include <stdio.h>

typedef struct info
{
 int x;
 int y;
 int hits;
 char c;
 char direction;

} info;



main()
{
  char array[12][12]={0};
  FILE *fptr;
  char c, filename[20];
  int i,j,k=0,l=0,m,n,flag=0, w=0;

  int entrance[2] = {0};


  info work[12][12], current;




  printf("Type file name for maze loading. : ");
  scanf ("%s",filename);


/*-----------------------------------------------------
  below is the algorithm for loading a user-input filename
  into an array. this will be our maze.
*/

  fptr = fopen(filename, "r");

  for (i=0; i<12; i++)
   for (j=0; j<12; j++){
    c=fgetc(fptr);
   while (! ((c== '1') || (c == '0')) )
    c=fgetc(fptr);
    array[i][j] = c;
    work[i][j].c = array[i][j];
    }

    fclose(fptr);




/* ----------------------------------------------------
   below is the algorithm for printing out the loaded maze.
*/

  printf("Maze Loaded into memory.\n");

  for (i=0; i<12; i++)
   for (j=0; j<12; j++){
    if (j == 0)
     printf("\n\t");

    printf("%c ",array[i][j]);
    }

  printf("\n\n\n");




/*  my working struct printout  */

  for (i=0; i<12; i++)
   for (j=0; j<12; j++){
    if (j == 0)
     printf("\n\t");

    printf("%c ",work[i][j].c);
    }

  printf("\n");






/* ----------------------------------------------------
   find the start point in the maze. 
   counterclockwise from top left.
*/

  i = 0;
  for (j=0; i<12; i++){
   if (array[i][j] == '0'){
    entrance[0] = i;            /*down the left side */
    entrance[1] = j;
    flag=1;
    break;
   }
  }


  if (flag == 0){
    j=1; 
    for (i=11; j<12; j++){
     if (array[i][j] == '0'){
      entrance[0] = i;
      entrance[1] = j;          /* across the bottom */
      flag=1;
      break;
     }
    }
  }


  if (flag == 0){
    i=11; 
    for (j=11; i>0; i--){
     if (array[i][j] == '0'){
      entrance[0] = i;
      entrance[1] = j;          /* up the right side */
      flag=1;
      break;
     }
    }
  }


  if (flag == 0){
    j=11; 
    for (i=0; j>0; j--){
     if (array[i][j] == '0'){
      entrance[0] = i;          /* across the top, back to start*/
      entrance[1] = j;
      flag=1;
      break;
     }
    }
  }



  if (flag == 0){
    printf("\nNo Start Point Found. Program Exiting.\n\n\n");
    exit();

  }
  else
    printf("\n    entrance is at location [%d],[%d]\n\n",entrance[0], entrance[1]);


    printf("    now searching for path to exit. . . .\n\n");


/*set entrance point to 'x' */
  work[entrance[0]][entrance[1]].c = 'x';

  work[entrance[0]][entrance[1]].hits++;

  current.x = entrance[0];
  current.y = entrance[1];



/*  my working struct printout  */

  for (i=0; i<12; i++)
   for (j=0; j<12; j++){
    if (j == 0)
     printf("\n\t");

    printf("%c ",work[i][j].c);
    }

  printf("\n");

 current.direction = 'E';

 while(w<20){


   if(current.direction == 'E'){
    if(work[current.x+1][current.y].c == '1'){
  if(work[current.x][current.y+1].c == '0' || work[current.x][current.y+1].c == 'x'){
   work[current.x][current.y].c == 'x';
   current.y++;
  }
  else if(work[current.x][current.y+1].c == '1'){
   if(work[current.x-1][current.y].c == '0' || work[current.x-1][current.y].c == 'x'){
    current.direction = 'N';
    work[current.x][current.y].c == 'x';
    current.x--;
   }
   else if(work[current.x-1][current.y].c == '1'){
     current.direction = 'W';
   }
  }
    else if(work[current.x+1][current.y].c == '0' || work[current.x+1][current.y].c == 'x'){
   current.direction = 'S';
   work[current.x][current.y].c == 'x';
   current.x++;
  }
    }
   }

   
   
       
   else if(current.direction == 'N'){
    if(work[current.x][current.y+1].c == '1'){
  if(work[current.x-1][current.y].c == '0' || work[current.x-1][current.y].c == 'x'){
   work[current.x][current.y].c == 'x';
   current.x--;
  }
  else if(work[current.x-1][current.y].c == '1'){
   if(work[current.x][current.y-1].c == '0' || work[current.x][current.y-1].c == 'x'){
    current.direction = 'W';
    work[current.x][current.y].c == 'x';
    current.y--;
   }
   else if(work[current.x][current.y-1].c == '1'){
     current.direction = 'S';
   }
  }
    else if(work[current.x][current.y+1].c == '0' || work[current.x][current.y+1].c == 'x'){
   current.direction = 'E';
   work[current.x][current.y].c == 'x';
   current.y++;
  }
    }
   }
       



   else if(current.direction == 'S'){
    if(work[current.x][current.y-1].c == '1'){
  if(work[current.x+1][current.y].c == '0' || work[current.x+1][current.y].c == 'x'){
   work[current.x][current.y].c == 'x';
   current.x++;
  }
  else if(work[current.x+1][current.y].c == '1'){
   if(work[current.x][current.y+1].c == '0' || work[current.x][current.y+1].c == 'x'){
    current.direction = 'E';
    work[current.x][current.y].c == 'x';
    current.y++;
   }
   else if(work[current.x][current.y+1].c == '1'){
     current.direction = 'N';
   }
  }
    else if(work[current.x][current.y-1].c == '0' || work[current.x][current.y-1].c == 'x'){
   current.direction = 'W';
   work[current.x][current.y].c == 'x';
   current.y--;
  }
    }
   }

   
   
   
   
   else if(current.direction == 'W'){
    if(work[current.x-1][current.y].c == '1'){
  if(work[current.x][current.y-1].c == '0' || work[current.x][current.y-1].c == 'x'){
   work[current.x][current.y].c == 'x';
   current.y--;
  }
  else if(work[current.x][current.y-1].c == '1'){
   if(work[current.x+1][current.y].c == '0' || work[current.x+1][current.y].c == 'x'){
    current.direction = 'S';
    work[current.x][current.y].c == 'x';
    current.x++;
   }
   else if(work[current.x+1][current.y].c == '1'){
     current.direction = 'E';
   }
  }
    else if(work[current.x-1][current.y].c == '0' || work[current.x-1][current.y].c == 'x'){
   current.direction = 'N';
   work[current.x][current.y].c == 'x';
   current.x--;
  }
    }
   }

   
   








/*  my working struct printout  */

  for (i=0; i<12; i++)
   for (j=0; j<12; j++){
    if (j == 0)
     printf("\n\t");

    printf("%c ",work[i][j].c);
    }

  printf("\n");  
   
  
w++;

 } /* end while loop */


}

oh, if you run it.. put the below in a text file as a test case:

111111111111

111110111111

110000111111

110111101111

110111101111

000111100001

110110101011

110110001011

110111101011

110000001000

111111011111

111111111111

Edited by excessdl
Link to comment
Share on other sites

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.