Finding a path in a maze using C++

How to solve a maze with C++ ?

The following picture represents a simple maze of 10*10 blocks. Note that our program will take a maximum of 40*40 dimensions for example, this picture is only to simplify your imagination process🙂
The maze will be represented by a 2 dimensional array.

maze

Functions definitions:

  1. main() is the main program, that is used to call all other functions.
  2. setCoord() is an void type function, that takes 2 params, number of rows and cols of the the maze.
  3. fillMaze() is a void type function, that takes 3 params, a maze ptr, number of its rows and cols.
  4. valMaze() is an integer type function, that takes 5 params, a maze ptr, number of its rows and cols, an eNtry(x,y) ptr, an eXit(x,y) ptr.
  5. findPos() is an integer type function, that takes 5 params, a maze ptr, number of its rows and cols, (x,y) ptr, accum num.
  6. /* additional functions will be added later */

I’m gonna present the program as functions first then glue everything together at the end to avoid complixity.

I would like also to take this chance to thank the following people who have helped me a lot with this progress: خالد الشايع, TheNapsterBoy, علي الشمري, عمر العادل.

Caution: WordPress source code parser SUCKS, danger of falling asteroids! use helmets as precaution😛

/*	gets the width and height of the maze
	checking for the allowed range */
void setCoord(int &nrows,int &ncols) {
	if (ncols < = 0 || ncols > 40) {
		printf ("Enter maze width: ");
		scanf_s  ("%d",&ncols);
	}
	if (nrows < = 0 || nrows > 40) {
		printf ("Enter maze height: ");
		scanf_s  ("%d",&nrows);
	}
	if (nrows < = 0 || nrows > 40 || ncols < = 0 || ncols > 40) {
		printf  ("Invalid width or height detected\n\n");
		setCoord(nrows,ncols);	// recursive call
	}
}

/* prompt user to fill the maze */
void fillMaze(char ** maze,int nrows,int ncols) {
printf (“\n\nFill in a maze as you would like it to appear\n”
“[Wall: 1] [Exit: 2] [Path: 3] ”
“[Entry: 4]\n”
“Example:\n\n”
“111111\n”
“433132\n”
“131131\n”
“133331\n”
“111111\n\n”);
int col = 0;
char c;
for (int row = 0; row < nrows; row++) { c = 0; while (col <= ncols) { c = _getch(); if (c > ‘0’ && c < '5' && col < ncols) { printf ("%c",c); maze[row][col] = c; col++; } else if (c == 0x0d && col == ncols) { printf ("\n"); maze[row][col] = 0; col = 0; break; } else if (c == '\x08') { /* emulate a backspace press fills in a blank char then backspace again */ printf ("\x08\xFF\x08"); if (col != 0) col--; } } } printf ("\n"); } [/sourcecode] [sourcecode language="cpp"] /* validates the maze for common mistakes */ int valMaze(char ** maze,int nrows,int ncols,int ** npos,int ** xpos) { int i, j, w_ok, w = 0, e = 0, num; for (i = 0; i < ncols; i++) { if (maze[0][i] == '1') w++; if (maze[nrows-1][i] == '1') w++; } for (i = 1; i < nrows-1; i++) { if (maze[i][0] == '1') w++; if (maze[i][ncols-1] == '1') w++; } w_ok = nrows * ncols - (nrows-2) * (ncols-2) - 2; if (w_ok != w) { printf ("\t\xF9 Ambiguous error detected with " "your walls\n\t" "make sure you have 1 entry and 1 exit " "points\n\t" "all other wall cells must be equal '1'\n"); e++; } findPos(maze,nrows,ncols,npos,num); if (*npos[0] == NULL && *npos[1] == NULL) { printf ("\t\xF9 No entry point was detected " "and NO, parachutes are not allowed!\n"); e++; } else if (num != 1) { printf ("\t\xF9 Multiple entry points were " "detected\n\t" "maze entry, exit maze, maze exit, " "entry maze... I'm lost *_*\n"); e++; } findPos(maze,nrows,ncols,xpos,num); if (*xpos[0] == NULL && *xpos[1] == NULL) { printf ("\t\xF9 No exit point was detected " "and NO, digging is not allowed!\n"); e++; } else if (num != 1) { printf ("\t\xF9 Multiple exit points were " "detected\n\t" "maze entry, exit maze, maze exit, " "entry maze... I'm lost *_*\n"); e++; } for (i = 1; i < nrows-1; i++) { for (j = 1; j < ncols-1; j++) { if (maze[i][j] == '4' || maze[i][j] == '2') { printf ("\t\xF9 Ambiguous error detected " "with your maze\n\t" "make sure it doesn't contain any entry or exit points inside\n"); e++; i = nrows; j = ncols; } } } printf ("\n"); if (e != 0) { printf ("\t\xF9 Errors were detected with " "your maze design\n\t" "thus no further operations are " "allowed\n\t" "press any key to exit the program.."); cin.get(); return 1; } else { printf ("\t\xF9 No errors were detected with " "your maze design\n\t" "GOD speed\n\n"); } return 0; } [/sourcecode] [sourcecode language="cpp"] /* find (x,y) position for both entry and exit returns an integer that decides if there is more than 1 entry/exit */ int findPos(char ** maze,int nrows,int ncols,int ** pos,int &num) { int i; num = 0; for (i = 1; i < ncols-1; i++) { if (maze[0][i] == '4' && num == 0) { *pos[1] = 0; *pos[0] = i; num++; } else if (maze[0][i] == '4' && num != 0) { num++; } else if (maze[nrows-1][i] == '4' && num == 0) { *pos[1] = nrows-1; *pos[0] = i; num++; } else if (maze[nrows-1][i] == '4' && num != 0) { num++; } } for (i = 1; i < nrows-1; i++) { if (maze[i][0] == '4' && num == 0) { *pos[1] = i; *pos[0] = 0; num++; } else if (maze[i][0] == '4' && num != 0) { num++; } else if (maze[i][ncols-1] == '4' && num == 0) { *pos[1] = i; *pos[0] = ncols-1; num++; } else if (maze[i][ncols-1] == '4' && num != 0) { num++; } } return num; } [/sourcecode] We will continue with new functions soon.

18 Responses to “Finding a path in a maze using C++”

  1. Good, and clear…

    But!
    May you check the following lines in the code?

    Line number 11, 27, 30, 31, and 34. Each of which has got a syntax error except the last one(34) which has got two syntax errors repeated twice on the same line. Totally, there are exactly six syntax errors. You can spot them easily in the usage of the following operators in the suggested lines:
    << and <=.
    These operators are composed. That is, no way to be separated by spaces. Just join them together by deleting the redundant invalid spaces among them.

    Of course you DO NOT have to write my name in this project acknowledgment.
    :happy:

    Best wishes…

  2. Thanks for pointing that out dear Raghad and welcome to my blog.

    However I must say that it’s not my fault to have a left over space between > and >, blame the parser of WordPress because that’s how I got it when I saved it. As you can see, line # 35 is error free, line # 26 is also error free.. it’s only a matter of bad parsing😉

    Anyway I will try and fix that tomorrow at night to make sure you notice.

    If it happens again in future posts and I couldn’t care less to fix it, trust me, I only publish error-free code🙂

    Enjoy.

  3. As I have promised, I tried several times to remove the space but it didn’t work😦
    I guess then people will have to live with this fact🙂

  4. Thanks a lot…

    Don’t worry!
    It’s clear to the C++ programmers, if necessary you may make a red-colored CAUTION that points these kinds of errors out to the users of this code.

    I am thankful…
    :happy:

  5. I’ve edited this post today, WordPress parser is even worse than I thought! it was forcing conversion of some code snippets into smilies!
    God damn it I don’t want to switch auto conversion off, WordPress programmers you suck!

  6. Hi Dear Plz Uplad Complete Project File Of This Program This Code Is Not Working Proply:::::

  7. I Am Using Visual Stdio If You Have Time Make This Maze In Visual Project And Upload Here Compressed ZIP File

  8. or upload here in cpp file or cpp file in compressed zip file Thanks
    PLZ Reply Soon…
    Beacuse I Want to take maze game as my final project

  9. it’s not workin proparly…
    can you re-try for me again…

  10. I haven’t written in my blog for ages.. if you are really interested reply to this comment w/ your exact email address in the email address field and I will mail you the project I submitted to my teacher in the college. Perhaps it’s not well written as I planned to do in this post originally but oh well, you still can figure out how it’s working and do your own I hope.

    Good luckk mahem.
    p.s: I wanted to mail you the project but your email differ in both your comments, perhaps a typo?

  11. Man this is just wonderful, i would like to give it
    a try, if you can and want plz send me the project
    to my mail.
    thnxxxxxxx…

  12. George,PH Says:

    Xacker pls help me this program is my case study, i already used the program but theres a one error at the first line void setCoord(……)
    why? pls help me my email is x2_city@yahoo.com xacker pls pls pls. i love your maze program. is it incomplete? or complete??

  13. Sorry to all of my visitors for not keeping up with my Blog.. I haven’t been able to find time and motivation to continue blogging..

    anyway, for those who have requested the maze algorithm I haven’t been able to *pimp* the code as I hoped.

    the following link contains the project files of the program, it’s the old version, *but works*
    if you have any question don’t hesitate to ask.

    http://www.4shared.com/file/141934021/4b5f5f46/MazeSolver.html

  14. i think this is c# not c++
    thanks

  15. Think again!😉

  16. سعيد Says:

    thank you

  17. Very thanks for maze solver
    Is there any way to randomize maze everytime we run the program

  18. It`s complicated…………………….

    😦

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: