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
*/We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.