943,955 Members | Top Members by Rank

Ad:
  • C++ Discussion Thread
  • Unsolved
  • Views: 1101
  • C++ RSS
You are currently viewing page 1 of this multi-page discussion thread
Nov 29th, 2008
0

Need help in finding correct method for my program!

Expand Post »
Hello guys, I'm new here, and this is my first post in this forums. Please bear with me if I can't explain what I'm in need of well.

Basically, this is part of my assignment, and I'm supposed to find a path from one end to the other in a maze.

The maze is pre-defined in a text file, and I've got to load it up onto the program. After loading the maze, I'll need to use a function to find the correct pathing and print out the pathing on the maze itself.

I'm a beginner in C++, so I'm kind of stuck at a particular problem.

The problem I'm facing is that, the way I use to search for the path is wrong. I've got no idea how to search for the correct path using a correct method.

A copy of the maze is attached in the file below, because posting here would be rather weird, as the whole maze is gonna look out of shape.

So far, this is my code:

C++ Syntax (Toggle Plain Text)
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. using namespace std;
  5.  
  6. char gameArray[8][16];
  7. int startX = 0;
  8. int startY = 0;
  9. bool positionCheck = false;
  10.  
  11. // Reminder:
  12. // i = y-axis direction
  13. // j = x-axis direction
  14.  
  15. void findPath(void)
  16. {
  17. for (int i = 0; i<8; i++)
  18. {
  19. for (int j = 0; j <16; j++)
  20. {
  21. if (gameArray[i][j] == 'M')
  22. {
  23. if (positionCheck == false)
  24. {
  25. startX = j;
  26. startY = i;
  27. positionCheck = true;
  28. cout << "Mouse is at: " << i << " " << j << endl;
  29. }
  30. }
  31. }
  32. }
  33. // moving in north
  34. if (gameArray[startY-1][startX] == ' ' ) // checking -1 of the y axis for a space. Can be increased to check more spaces at the front.
  35. {
  36. cout << "Replacing path!" << endl;
  37. gameArray[startY-1][startX] = '+'; // if the space is available, change the space to a + sign.
  38. startY--;
  39. findPath(); // recurs to that it'll recheck
  40. }
  41. // moving in south
  42. else if (gameArray[startY+1][startX] == ' ') // same as north
  43. {
  44. cout << "Replacing path!" << endl;
  45. gameArray[startY+1][startX] = '+';
  46. startY++;
  47. findPath();
  48. }
  49. // moving in west
  50. else if (gameArray[startY][startX-1] == ' ')
  51. {
  52. cout << "Replacing path!" << endl;
  53. gameArray[startY][startX-1] = '+';
  54. startX--;
  55. findPath();
  56. }
  57. else if (gameArray[startY][startX+1] == ' ')
  58. {
  59. cout << "Replacing path!" << endl;
  60. gameArray[startY][startX+1] = '+';
  61. startX++;
  62. findPath();
  63. }
  64. }
  65.  
  66.  
  67. char inputStandard(void)
  68. {
  69. ifstream myfile ("standard.txt");
  70.  
  71. if (myfile.is_open())
  72. {
  73. for (int i = 0; i<8; i++)
  74. {
  75. for (int j = 0; j < 16; j++)
  76. {
  77. myfile.get(gameArray[i][j]);
  78. }
  79. }
  80. myfile.close();
  81. }
  82. return 0;
  83. }
  84.  
  85.  
  86. char inputCustom(void)
  87. {
  88. ifstream myfile ("custom.txt");
  89.  
  90. if (myfile.is_open())
  91. {
  92. for (int i = 0; i<8; i++)
  93. {
  94. for (int j = 0; j < 16; j++)
  95. {
  96. myfile.get(gameArray[i][j]);
  97. }
  98. }
  99. myfile.close();
  100. }
  101. return 0;
  102. }
  103.  
  104. void main(void)
  105. {
  106. string status_mode = "NONE";
  107. int choice;
  108. for (int start_loop = 1; start_loop>0; start_loop++)
  109. {
  110. if (status_mode != "NONE")
  111. {
  112. for (int indexrow=0; indexrow<8; indexrow++)
  113. {
  114. for (int indexcol=0; indexcol<16;indexcol++)
  115. {
  116. cout << gameArray[indexrow][indexcol];
  117. }
  118. }
  119. cout << endl;
  120. }
  121. cout << "Active Maze: " << status_mode << endl;
  122. cout << "1. Select Standard Maze" << endl;
  123. cout << "2. Select Custom Maze" << endl;
  124. cout << "3. Find Path" << endl;
  125. cout << "4. Print Path" << endl;
  126. cout << "5. End " << endl;
  127.  
  128. cin >> choice;
  129.  
  130. if (choice == 1)
  131. {
  132. status_mode = "STANDARD";
  133. inputStandard();
  134. cout << "Standard Mode Selected!" << endl << endl;
  135. }
  136. if (choice == 2)
  137. {
  138. status_mode = "CUSTOM";
  139. inputCustom();
  140. cout << "Custom Mode Selected!" << endl << endl;
  141. }
  142. if (choice == 3)
  143. {
  144. findPath();
  145. }
  146. if (choice == 4)
  147. {
  148. cout << "DISABLED. " << endl << endl;
  149. }
  150. if (choice == 5)
  151. {
  152. cout << "EXITING!" << endl;
  153. break;
  154. }
  155. if (!cin)
  156. {
  157. cout << "ERROR IN INPUT!" << endl;
  158. }
  159. }
  160. }

How the final product I'm required to do this somewhat like this...

http://notcliche.com/example.PNG

Any help with regards to a pathing method would be greatly appreciated, and thanks in advance!
Attached Files
File Type: txt standard.txt (136 Bytes, 15 views)
Similar Threads
Reputation Points: 10
Solved Threads: 0
Newbie Poster
Nyaato is offline Offline
11 posts
since Nov 2008
Nov 29th, 2008
0

Re: Need help in finding correct method for my program!

This is actually harder because the maze itself has a lot of extra white space so there is not a unique solution. It will be easier in some ways to program for a maze where all the paths are only one character wide. Best foolproof algorithm is to always keep a wall on your right. When you bump into an obstacle, always turn right, which keeps the wall on your right. You should change the value of the grid where you can walk to a different value to mark what spots you have already travelled. When you are forced to backtrack, mark that direction as a direction that you know is a wrong turn. When given an option, always go somewhere you haven't yet gone. This method will work here too even though the maze has extra white space. Draw it on paper first before tackling the programming part. You need to really understand the algorithm before implementing it.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008
Nov 29th, 2008
0

Re: Need help in finding correct method for my program!

First, it's int main() not void main(). Your compiler may let you use void, but it's not a wise idea to do so, and it's even one keystroke less to type int rather than void.

Second main() usually has two arguments. You can type them in, or leave the parenthesis blank, but I'm not sure using void as a parameter is going to work.

Third, do you know about structs and stacks? They are used in some of the implementations for solving mazes as they can be helpful in setting up the protocols vernon dozier talks about, like keeping tack of whether you've been to a given square or cell of the maze or not and backtracking when the path you have been following becomes blocked.
Reputation Points: 718
Solved Threads: 373
Nearly a Posting Maven
Lerner is offline Offline
2,253 posts
since Jul 2005
Nov 29th, 2008
0

Re: Need help in finding correct method for my program!

Alright, noted and changed my void main() to int main(). Thanks for the advice!

I've use structs before, but not stacks. Haven't learned of that as of yet.

I'm still trying to figure out how to backtrack, as of what VernonDozier had suggested, but I'm not getting far at the moment...

If it's not too much, could I get an example of how it's like? Thanks again!
Reputation Points: 10
Solved Threads: 0
Newbie Poster
Nyaato is offline Offline
11 posts
since Nov 2008
Nov 30th, 2008
0

Re: Need help in finding correct method for my program!

Click to Expand / Collapse  Quote originally posted by Nyaato ...
Alright, noted and changed my void main() to int main(). Thanks for the advice!

I've use structs before, but not stacks. Haven't learned of that as of yet.

I'm still trying to figure out how to backtrack, as of what VernonDozier had suggested, but I'm not getting far at the moment...

If it's not too much, could I get an example of how it's like? Thanks again!
Here is a maze.
C++ Syntax (Toggle Plain Text)
  1. *******
  2. ***
  3. * *
  4. * *****
  5. * *
  6. *******
  7.  
  8. Here is the correct path.
  9.  
  10. *******
  11. oo***oo
  12. *ooooo*
  13. * *****
  14. * *
  15. *******
  16.  
  17. Here is the attempt where you keep the wall to your right.
  18.  
  19.  
  20. *******
  21. oo***
  22. *o *
  23. *o*****
  24. *oooo@*
  25. *******
  26.  
  27. Oops, I hit a wall with a dead end. I have nowhere else to go, so I backtrack (i.e. go where I went before). I know that any spot where I've gone before and where I have no blank spaces and no option to switch directions is a dead end. Mark that dead end with an x so I don't go over it again.
  28.  
  29. *******
  30. oo***
  31. *o *
  32. *o*****
  33. *ooo@x*
  34. *******
  35.  
  36. *******
  37. oo***
  38. *o *
  39. *o*****
  40. *oo@xx*
  41. *******
  42.  
  43. and so on till I get to a spot where I have a new option.
  44.  
  45. *******
  46. oo***
  47. *@ *
  48. *x*****
  49. *xxxxx*
  50. *******
  51.  
  52. I'm back where I was before. Go right again.
  53.  
  54. *******
  55. oo***
  56. *o@ *
  57. *x*****
  58. *xxxxx*
  59. *******
  60.  
  61. Keep going.
  62.  
  63. *******
  64. oo***oo
  65. *ooooo*
  66. *x*****
  67. *xxxxx*
  68. *******
  69.  
Solved! Blank space is where I haven't been. o is where I've been that may possibly be the route, x is where I've been that is definitely not the route, @ is where I am now. When you reach a dead end, turn around and leave x's in your trail until you have an option to go right again. Never go down a path with an x.

This is a trivial example, but hopefully it'll help. Again, draw it out on paper first till you get a better understanding. Don't skip any steps till you really understand it.
Last edited by VernonDozier; Nov 30th, 2008 at 12:03 am.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008
Nov 30th, 2008
0

Re: Need help in finding correct method for my program!

Okay, so far so good. I understood what you've suggested to me. However, I'm still in a pinch.

I got this whole chunk of code done up, and the backtracking works to a certain extend. I know something is wrong with my backtracking, but I've got no idea how to fix it.

C++ Syntax (Toggle Plain Text)
  1. void findPath(void)
  2. {
  3. for (int i = 0; i<8; i++)
  4. {
  5. for (int j = 0; j <16; j++)
  6. {
  7. if (gameArray[i][j] == 'M')
  8. {
  9. if (positionCheck == false)
  10. {
  11. startX = j;
  12. startY = i;
  13. positionCheck = true;
  14. cout << "Mouse is at: " << i << " " << j << endl;
  15. }
  16. }
  17. }
  18. }
  19. // moving in north
  20. if (gameArray[startY-1][startX] == ' ')
  21. {
  22. cout << "Replacing path!" << endl;
  23. gameArray[startY-1][startX] = '+';
  24. startY--;
  25. findPath();
  26. }
  27. // moving in east
  28. else if (gameArray[startY][startX+1] == ' ')
  29. {
  30. cout << "Replacing path!" << endl;
  31. gameArray[startY][startX+1] = '+';
  32. startX++;
  33. findPath();
  34. }
  35. // backtracking
  36. else if (gameArray[startY][startX] == '+')
  37. {
  38. cout << "Backtracking" << endl;
  39. gameArray[startY][startX] = 'X';
  40. if (moveEast == false)
  41. {
  42. startX--;
  43. }
  44. else if (moveNorth == false)
  45. {
  46. startY++;
  47. }
  48. findPath();
  49. }
  50. // checking for max north
  51. else if (gameArray[startY-1][startX] == '*' && moveNorth == true)
  52. {
  53. moveNorth = false;
  54. cout << "Max for north reached!" << endl;
  55. gameArray[startY][startX] = 'X';
  56. startY++;
  57. findPath();
  58. }
  59. // checking for max east
  60. else if (gameArray[startY][startX+1] == '*' && moveEast == true)
  61. {
  62. moveEast = false;
  63. cout << "Max for east reached!" << endl;
  64. gameArray[startY][startX] = 'X';
  65. startX--;
  66. findPath();
  67. }
  68. }

The code above is the whole findPath function. There is something wrong with the backtracking area, but I've got no idea how to fix it.

A screenshot of the problem is displayed in the attachment. Please advise!
Attached Thumbnails
Click image for larger version

Name:	error.PNG
Views:	44
Size:	1.3 KB
ID:	8405  
Reputation Points: 10
Solved Threads: 0
Newbie Poster
Nyaato is offline Offline
11 posts
since Nov 2008
Nov 30th, 2008
0

Re: Need help in finding correct method for my program!

I don't even see a solution to that maze unless you are allowed to move diagonally. I strongly suggest you not allow that if you don't need to as it complicated things significantly from a programming standpoint. Develop a more compact maze. You shouldn't have any paths that are wider than your character. As mentioned, the "keep the wall to the right" method will also solve these "wide path" problems too, but you'll do better to design a maze like I did, where there is a solution without going diagonally and where all the paths are just one unit wide.

We have no way to run your code. In something like this, the problem could easily be anywhere. We don't know what the variables have been initialized to before this function is called. Just looking at what you have, though, I seriously doubt you want the nested for-loop. You probably want a while loop. You need some way to see whether the maze is solved, at which point exit the while loop. You have no idea how many steps it is going to take, so a for-loop doesn't seem like the right approach. You need to post the entire program for anyone to be able to run it. If it is the same program as what you originally posted, you need to say so. We can't assume that.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008
Dec 1st, 2008
0

Re: Need help in finding correct method for my program!

As much as I would like to change the maze, it's not really possible for me to do that, as the maze stated in standard.txt is what I need solve.

I'll paste the whole code here again. I've fixed some of the error I've found, and it should, more or less work properly now, however, there are still some errors around.

I'll work on changing the for loop into while loop, as you've suggested, and it seems quite true, since I've got no idea how many steps I would need to finish the whole maze.

Anyway... here's the whole code. I know it's kind of messy... but bear with me. Thanks again.

C++ Syntax (Toggle Plain Text)
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. using namespace std;
  5.  
  6. char gameArray[8][16];
  7. int startX = 0;
  8. int startY = 0;
  9. bool moveNorth = true; // checks if it is able to move north
  10. bool moveEast = true; // checks if it's able to move east
  11. bool positionCheck = false; // used to check if Mouse's (M) position is located
  12.  
  13. void findPath(void)
  14. {
  15. for (int i = 0; i<8; i++)
  16. {
  17. for (int j = 0; j <16; j++)
  18. {
  19. if (gameArray[i][j] == 'M')
  20. {
  21. if (positionCheck == false)
  22. {
  23. startX = j;
  24. startY = i;
  25. positionCheck = true;
  26. cout << "Mouse is at: " << i << " " << j << endl;
  27. }
  28. }
  29. }
  30. }
  31. // moving in north
  32. if (gameArray[startY-1][startX] == ' ')
  33. {
  34. moveEast = false;
  35. cout << "Replacing path!" << endl;
  36. gameArray[startY-1][startX] = '+';
  37. startY--;
  38. findPath();
  39. }
  40. // moves in the east direction
  41. if (gameArray[startY][startX+1] == ' ')
  42. {
  43. moveNorth = false;
  44. cout << "Replacing path!" << endl;
  45. gameArray[startY][startX+1] = '+';
  46. startX++;
  47. findPath();
  48. }
  49. // moves in the west direction
  50. if (gameArray[startY][startX-1] == ' ')
  51. {
  52. moveEast = false;
  53. moveNorth = false;
  54. cout << "Replacing path!" << endl;
  55. gameArray[startY][startX-1] = '+';
  56. startX--;
  57. findPath();
  58. }
  59. // backtracking
  60. else if (gameArray[startY][startX] == '+')
  61. {
  62. if (moveNorth == false)
  63. {
  64. // backtracking in north direction
  65. cout << "Back tracking!" << endl;
  66. gameArray[startY][startX] = 'X';
  67. startX--;
  68. }
  69. else if (moveEast == false)
  70. {
  71. // backtracking in east direction
  72. cout << "Back tracking!" << endl;
  73. gameArray[startY][startX] = 'X';
  74. startY++;
  75. }
  76. }
  77. // check if north reaches a dead end
  78. else if (gameArray[startY-1][startX] == '*' && moveNorth == true)
  79. {
  80. cout << "Max for north reached!" << endl;
  81. gameArray[startY][startX] = 'X';
  82. startY++;
  83. findPath();
  84. }
  85. // checks if east reaches a dead end
  86. else if (gameArray[startY][startX] == '+' && moveEast == true)
  87. {
  88. cout << "Backtracking" << endl;
  89. gameArray[startY][startX] = 'X';
  90. startY++;
  91. findPath();
  92. }
  93.  
  94. }
  95.  
  96.  
  97.  
  98. char inputStandard(void)
  99. {
  100. ifstream myfile ("standard.txt");
  101.  
  102. if (myfile.is_open())
  103. {
  104. for (int i = 0; i<8; i++)
  105. {
  106. for (int j = 0; j < 16; j++)
  107. {
  108. myfile.get(gameArray[i][j]);
  109. }
  110. }
  111. myfile.close();
  112. }
  113. return 0;
  114. }
  115.  
  116.  
  117. char inputCustom(void)
  118. {
  119. ifstream myfile ("custom.txt");
  120.  
  121. if (myfile.is_open())
  122. {
  123. for (int i = 0; i<8; i++)
  124. {
  125. for (int j = 0; j < 16; j++)
  126. {
  127. myfile.get(gameArray[i][j]);
  128. }
  129. }
  130. myfile.close();
  131. }
  132. return 0;
  133. }
  134.  
  135. void main(void)
  136. {
  137. string status_mode = "NONE";
  138. int choice;
  139. for (int start_loop = 1; start_loop>0; start_loop++)
  140. {
  141. if (status_mode != "NONE")
  142. {
  143. for (int indexrow=0; indexrow<8; indexrow++)
  144. {
  145. for (int indexcol=0; indexcol<16;indexcol++)
  146. {
  147. cout << gameArray[indexrow][indexcol];
  148. }
  149. }
  150. cout << endl;
  151. }
  152. cout << "Active Maze: " << status_mode << endl;
  153. cout << "1. Select Standard Maze" << endl;
  154. cout << "2. Select Custom Maze" << endl;
  155. cout << "3. Find Path" << endl;
  156. cout << "4. Print Path" << endl;
  157. cout << "5. End " << endl;
  158.  
  159. cin >> choice;
  160.  
  161. if (choice == 1)
  162. {
  163. status_mode = "STANDARD";
  164. inputStandard();
  165. cout << "Standard Mode Selected!" << endl << endl;
  166. }
  167. if (choice == 2)
  168. {
  169. status_mode = "CUSTOM";
  170. inputCustom();
  171. cout << "Custom Mode Selected!" << endl << endl;
  172. }
  173. if (choice == 3)
  174. {
  175. cout << "DISABLED." << endl << endl;
  176. findPath();
  177. }
  178. if (choice == 4)
  179. {
  180. cout << "DISABLED. " << endl << endl;
  181. }
  182. if (choice == 5)
  183. {
  184. cout << "EXITING!" << endl;
  185. break;
  186. }
  187. if (!cin)
  188. {
  189. cout << "ERROR IN INPUT!" << endl;
  190. }
  191. }
  192. }
Reputation Points: 10
Solved Threads: 0
Newbie Poster
Nyaato is offline Offline
11 posts
since Nov 2008
Dec 1st, 2008
0

Re: Need help in finding correct method for my program!

You need to provide the original input file too. It is unfortunate that you are stuck with that maze because you now have to design code that can move and check in eight directions rather than four. Also, how do you know where to start and stop? There are no holes in the side of the maze and nothing in your code that reads from the input file that tells you where to start, plus how do you know when you are done? Is there an 'S' and 'F' in the input file or something? You can't start at (0,0) because that's a wall/asterisk.

void main(void)
{
	string status_mode = "NONE";
	int choice;
	for (int start_loop = 1; start_loop>0; start_loop++)
	{
		if (status_mode != "NONE")
		{
			for (int indexrow=0; indexrow<8; indexrow++)
			{
				for (int indexcol=0; indexcol<16;indexcol++)
				{
					cout <<  gameArray[indexrow][indexcol];
				}
			}
			cout << endl;
		}
		cout << "Active Maze: " << status_mode << endl;
		cout << "1. Select Standard Maze" << endl;
		cout << "2. Select Custom Maze" << endl;
		cout << "3. Find Path" << endl;
		cout << "4. Print Path" << endl;
		cout << "5. End " << endl;

		cin >> choice;

		if (choice == 1)
		{
			status_mode = "STANDARD";
			inputStandard();
			cout << "Standard Mode Selected!" << endl << endl;
		}
		if (choice == 2)
		{
			status_mode = "CUSTOM";
			inputCustom();
			cout << "Custom Mode Selected!" << endl << endl;
		}
		if (choice == 3)
		{
			cout << "DISABLED." << endl << endl;
			findPath();
		}
		if (choice == 4)
		{
			cout << "DISABLED. " << endl << endl;
		}
		if (choice == 5)
		{
			cout << "EXITING!" << endl;
			break;
		}
		if (!cin)
		{
			cout << "ERROR IN INPUT!" << endl;
		}
	}
}

It is int main () , not void main () , even if your compiler lets you get away with it. You have what appears to be an infinite loop. See red code above. If that is intentional, you should probably change it to a while (true) loop so it's more obvious that it is intentional.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008
Dec 1st, 2008
0

Re: Need help in finding correct method for my program!

I just took another look at the original standard.txt. It's attached earlier in the thread. No diagonal moves are required. I'm not sure what you did on your post, but it looks like you did a diagonal move or something. There is a 'C' and an 'M' in there too. You need to say what those represent.
Last edited by VernonDozier; Dec 1st, 2008 at 9:52 am.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: Windows Console Mouse operations
Next Thread in C++ Forum Timeline: Segmentation Fault error





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC