Right Hand Rule Maze Solver

Adak 0 Tallied Votes 3K Views Share

Demonstrates the Right Hand Rule maze solving algorithm, with some sweet console colors and text display and erasing, in Windows.

Note that if the Start is moved away from all the walls in the maze, the right hand rule fails, circling endlessly. Also, a similar failure happens if the Start is put onto an "island" part of the walls in the maze. This algorithm will not solve all mazes.

/* My right hand rule maze solver 
by Adak, Sept. 12, 2013

Algorithm note: The right hand rule means the program
can only know what is on his right side. Unless the 
right side is blocked, no other direction will be checked.

The text writing/erasing is pretty good. ;)

*/

#include <stdio.h>
#include <windows.h>

#define ROWS 19
#define COLS 25
#define WALL 219  
#define TRAIL 111   
#define MSG_ROWS 9
#define MSG_COLS 65
#define DOT '.'

//S=start F=Finish 
unsigned char maze[ROWS][COLS+1]={ 
{"                         "}, //it's easy to make a maze using 8's
{"                         "}, //and have the program change them
{"   8888888888888888888   "}, //into a better looking WALL char 
{"   8.................8   "}, //for you, before the game starts
{"   8.8...88.8......888   "},
{"   8.888.88.8....888.8   "}, //mazes with more than one cycle in
{"   8.8....8.88..8....8   "}, //them, or with their finish away 
{"   8.8888.8.888..8...8   "}, //from any wall, may not be solved 
{"   8.8.......888.888.8   "}, //by a right hand rule maze solver.
{"   8.8888....88..88..8   "}, 
{"   8.....88..8..88...8   "},
{"   8.8888....8....88.8   "},
{"   8..88.8888.8888...8   "},
{"   8..8............8.8   "},
{"   8.888888888888888.8   "},
{"   8.................8   "},
{"   8888F88S88888888888   "},
{"                         "},
{"                         "}
};          

void GoToXY(int r, int c);
void printIt(int dir,int move);
void showMSG(void);

int main(void) {
   int c,r,cr=0,cc=0;  //cr=current row, cc=current col
   int done=0,dir2b=0; //dir2b=holds furture dir value
   int dir=0,move=0;          //directions: north=0,east=1,south=2,west=3;

   //sets the starting location and the wall char
   for(r=0;r<ROWS;r++) {  
      for(c=0;c<COLS;c++) {
         if(maze[r][c]=='S') {
           cr=r;
           cc=c;
         }else if(maze[r][c]=='8')
            maze[r][c]=WALL;
      }
   }
   HANDLE hConsole;
   hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
   SetConsoleTextAttribute(hConsole, 0x1F);  

   showMSG();   
   printIt(dir,move);
   Sleep(2000);
  
   //sets the initial direction only
   if(maze[cr][cc+1]== DOT) {  
         dir=0;  //not dir=1!
   }else if(maze[cr+1][cc]==DOT) {
         dir=1; 
   }else if(maze[cr][cc-1]==DOT) {
         dir=2; 
   }else if(maze[cr-1][cc]==DOT) {
         dir=3;
   }
   //main solving loop
   while(!done) {             
      if(maze[cr][cc] != 'S') maze[cr][cc]= TRAIL;
      if(dir==0) { //North
         if(maze[cr][cc+1] != WALL && maze[cr][cc+1] != 'S') {  
            dir2b=1;
            cc++;
         }else if(maze[cr-1][cc] != WALL && maze[cr-1][cc] != 'S') {
            dir2b=0;
            cr--;
         }else if(maze[cr][cc-1] != WALL && maze[cr][cc-1] != 'S') {
            dir2b=3;
            cc--;
         }else if(maze[cr+1][cc] != WALL && maze[cr+1][cc] != 'S') {
            dir2b=2;
            cr++;
         }
      }      
      if(dir==1) { //East
         if(maze[cr+1][cc] != WALL && maze[cr+1][cc] != 'S') {
            dir2b=2;
            cr++;
         }else if(maze[cr][cc+1] != WALL && maze[cr][cc+1] != 'S') {
            dir2b=1;
            cc++;
         }else if(maze[cr-1][cc] != WALL && maze[cr-1][cc] != 'S') {
            dir2b=0;
            cr--;
         }else if(maze[cr][cc-1] != WALL && maze[cr][cc-1] != 'S') {
            dir2b=3;
            cc--;
         }
      }      
      if(dir==2) { //South
         if(maze[cr][cc-1] != WALL && maze[cr][cc-1] != 'S') {
            dir2b=3;
            cc--;
         }else if(maze[cr+1][cc] != WALL && maze[cr+1][cc] != 'S') {
            dir2b=2;
            cr++;
         }else if(maze[cr][cc+1] != WALL && maze[cr][cc+1] != 'S') {
            dir2b=1;
            cc++;
         }else if(maze[cr-1][cc] != WALL && maze[cr-1][cc] != 'S') {
            dir2b=0;
            cr--;
         }
      }      
      if(dir==3) { //West
         if(maze[cr-1][cc] != WALL && maze[cr-1][cc] != 'S') {
            dir2b=0;
            cr--;
         }else if(maze[cr][cc-1] != WALL && maze[cr][cc-1] != 'S') {
            dir2b=3;
            cc--;
         }else if(maze[cr+1][cc] != WALL && maze[cr+1][cc] != 'S') {
            dir2b=2;
            cr++;
         }else if(maze[cr][cc+1] != WALL && maze[cr][cc+1] != 'S') {
            dir2b=1;
            cc++;
         }
      }
      if(maze[cr][cc]=='F')  //reached the Finish yet?
         done=1;
      maze[cr][cc]='*';
      ++move;
      dir=dir2b;             //dir value calculated above, is assigned
      printIt(dir,move);
      
   }
   GoToXY(30,12);
   printf("Done!\a\a\n");
   GoToXY(1,23);
   printf("\n Algorithm note: The right hand rule means the program\
   \n can only know what is on it's right side. Unless the right\
   \n side is blocked, no other direction will be checked.\n\n ");

   return 0;
}
void showMSG(void) {
   int r,c;

   char message[MSG_ROWS][MSG_COLS]={
      {"\t\t     * A Right Hand Rule Maze Solver *                   "},
      {"\t   'Always keep your right hand on the wall!'              "},
      {"\t     * If possible, turn right.                            "},
      {"\t     * else go straight                                    "},
      {"\t     * else turn left                                      "},
      {"\t     * else turn around                                    "},
      {"\tWhichever way you go, you face that direction.             "},
      {"\tNorth is up, East is right, South is down, and West is left"},
      {"\tRight Hand Rule logic will not solve all mazes.            "}
   };

   HANDLE hConsole;
   hConsole = GetStdHandle(STD_OUTPUT_HANDLE);

   printf("\n\n");
   for(r=0;r<MSG_ROWS;r++) {
      c=0;
      while(message[r][c]!='\0') {
         putchar(message[r][c]);
         Sleep(10);
         ++c;
      }
      printf("\n\n");
      if(r==0)
         printf("\n\n");
   }
   printf("\n\n\tPress Enter When Ready to Continue ");
   fflush(stdout);
   getchar();

   for(r=24;r>0;r-=2) {
      c=64;
      GoToXY(66,r);
      while(c>3) {
         printf("%c\b\b",' ');
         Sleep(10);
         --c;
      }
      if(r==24 || r==6)
         r-=2;
   }
   Sleep(800);
   GoToXY(13,4);
   printf("%s",message[0]);
}

void printIt(int dir,int move) {
   int i,j;
   char *directions[]={"North","East ","South","West "};
   HANDLE hConsole;
   hConsole = GetStdHandle(STD_OUTPUT_HANDLE);
   //Color numbers from 16-31 include blue background
   GoToXY(1,4);   
   for(i=0;i<ROWS;i++) {
      for(j=0;j<COLS;j++) {
         if(maze[i][j]=='*') {
            //blue background with red foregrund: 28 or 0x1C 
            SetConsoleTextAttribute(hConsole, 0x1C); 
            printf("%c",maze[i][j]);
         }else if(maze[i][j]=='S' || maze[i][j]=='F') {
            SetConsoleTextAttribute(hConsole, 0x1E); //yellow
            printf("%c",maze[i][j]);
         }else if(maze[i][j]==TRAIL) {
            SetConsoleTextAttribute(hConsole, 0xB9); //was 79//backgrd: Grey, foregrd: Bright Blue
            printf("%c",maze[i][j]);
         }else { //if(move==0){
            SetConsoleTextAttribute(hConsole, 0xB0); //
            printf("%c",maze[i][j]);
         }
         SetConsoleTextAttribute(hConsole, 0x1F); //white=31
      }
      printf("\n ");
   }
   SetConsoleTextAttribute(hConsole, 31); //white
   GoToXY(30,10);
   printf("Move #%3d is: %s \n",move,directions[dir]);
   Sleep(200);
}
void GoToXY(int r, int c)
{
    // Create a COORD structure and fill in its members.
    COORD coord;
    coord.X = r;
    coord.Y = c;

    // Obtain a handle to the console screen buffer.
    // Since it's a standard handle, no need to close it.
    HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);

    // Call the SetConsoleCursorPosition function.
    SetConsoleCursorPosition(hConsole, coord);
}


/* Console Colors in Windows are organized in blocks of 16. Each block has a different
background to it: 0-15 has a black background, 16-31 has a dark blue background, etc. 


0=Black, 1=Blue, 2=Green, 3=Dark Cyan, 4=Red, 5=Purple, 6=Yellowy Brown, 7=Grey,
8=Dark Grey, 9=Bright Blue, 10=A=Bright Green 11==B=Bright Cyan, 12=C=Bright Red, 
13=D=Bright Magenta, 14=E=Yellow, 15=F=White

Lots more info: http://www.mailsend-online.com/blog/setting-windows-console-text-colors-in-c.html

*/