API tools faq
paste
Advertisement
Cinestra

Path Finder with Path pruning

Cinestra
Mar 31st, 2023
21
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 14.44 KB | None | 0 0
raw download clone embed print report
  1. #include <iostream>
  2. #include <cassert>
  3. #include <queue>
  4. #include <stack>
  5. #include <string>
  6.  
  7. using namespace std;
  8.  
  9. class Coord
  10. {
  11. public:
  12. Coord(int r, int c) : m_row(r), m_col(c) {}
  13. int r() const { return m_row; }
  14. int c() const { return m_col; }
  15. private:
  16. int m_row;
  17. int m_col;
  18. };
  19.  
  20. // Returns true if a path exists from (starting_row, starting_col) to (ending_row, ending_col)
  21. bool pathExists(string maze[], int number_of_rows, int number_of_cols, int starting_row, int starting_col, int ending_row, int ending_col)
  22. {
  23. // Initialize a Queue of Coordinates
  24. queue<Coord> queue_of_coordinates;
  25.  
  26. // Push the Queue by putting in the starting row and starting col
  27. // Assignment instructions that starting point is always going to be a "." and not a wall
  28. queue_of_coordinates.push(Coord(starting_row, starting_col));
  29.  
  30. // The maze is an array of strings
  31. // While we have only defined the rows of the string, the "columns" of the string are implict because they are each of the individual characters of the string
  32. // We will overwrite that as D to mark it as discovered
  33. maze[starting_row][starting_col] = 'D';
  34.  
  35. while (!queue_of_coordinates.empty())
  36. {
  37. // Pop the queue by taking the coordinate in queue and popping it
  38. // Different from stack because stack pops the most recent item whereas queue pops the item that has been there the longest
  39. Coord current = queue_of_coordinates.front();
  40. queue_of_coordinates.pop();
  41.  
  42. int current_row = current.r();
  43. int current_col = current.c();
  44.  
  45. if (current_row == ending_row && current_col == ending_col)
  46. return true;
  47.  
  48. // Remember to use IF statements for the following, not else if statements
  49. // You need to put each and every possible point on the stack
  50.  
  51. // First, check EAST, which is (r, c+1)
  52. if (maze[current_row][current_col + 1] == '.')
  53. {
  54. queue_of_coordinates.push(Coord(current_row, current_col + 1));
  55. maze[current_row][current_col + 1] = 'D';
  56. }
  57.  
  58. // Second, check NORTH, which is (r-1, c)
  59. if (maze[current_row - 1][current_col] == '.')
  60. {
  61. queue_of_coordinates.push(Coord(current_row - 1, current_col));
  62. maze[current_row - 1][current_col] = 'D';
  63. }
  64.  
  65. // Third, check WEST, which is (r, c-1)
  66. if (maze[current_row][current_col - 1] == '.')
  67. {
  68. queue_of_coordinates.push(Coord(current_row, current_col - 1));
  69. maze[current_row][current_col - 1] = 'D';
  70. }
  71.  
  72. // Finally, check SOUTH, which is (r+1, c)
  73. if (maze[current_row + 1][current_col] == '.')
  74. {
  75. queue_of_coordinates.push(Coord(current_row + 1, current_col));
  76. maze[current_row + 1][current_col] = 'D';
  77. }
  78. }
  79.  
  80. return false;
  81. }
  82.  
  83. void printMaze(string maze[], int number_of_rows, int number_of_cols)
  84. {
  85. for (int i = 0; i < number_of_rows; i++)
  86. {
  87. for (int j = 0; j < number_of_cols; j++)
  88. {
  89. cout << maze[i][j];
  90. }
  91. cout << endl;
  92. }
  93.  
  94. cout << endl;
  95. }
  96.  
  97. bool isDeadEnd(string maze[], int starting_row, int starting_col, int ending_row, int ending_col, int current_row, int current_col)
  98. {
  99. // If there are 3 directions unavailable, then it is a dead end
  100. // There will always be one direction available (the one that lead to that point).
  101. //
  102. // 3 different characters mark if a direction is unavailable: walls, N, or .
  103. // . represents a path never taken when proving if the path exists or not
  104. // x represents a wall that we obviously we cannot walk into
  105. // N represents a point we've marked that leads nowhere
  106.  
  107. if (current_row == starting_row && current_col == starting_col)
  108. return false;
  109.  
  110. if (current_row == ending_row && current_col == ending_col)
  111. return false;
  112.  
  113. int number_of_directions_unavailable = 0;
  114.  
  115. // First, check EAST, which is (r, c+1)
  116. if (maze[current_row][current_col + 1] == '.' || maze[current_row][current_col + 1] == 'X' || maze[current_row][current_col + 1] == 'N')
  117. number_of_directions_unavailable++;
  118.  
  119. // Second, check NORTH, which is (r-1, c)
  120. if (maze[current_row - 1][current_col] == '.' || maze[current_row - 1][current_col] == 'X' || maze[current_row - 1][current_col] == 'N')
  121. number_of_directions_unavailable++;
  122.  
  123. // Third, check WEST, which is (r, c-1)
  124. if (maze[current_row][current_col - 1] == '.' || maze[current_row][current_col - 1] == 'X' || maze[current_row][current_col - 1] == 'N')
  125. number_of_directions_unavailable++;
  126.  
  127. // Last, check SOUTH, which is (r+1, c)
  128. if (maze[current_row + 1][current_col] == '.' || maze[current_row + 1][current_col] == 'X' || maze[current_row + 1][current_col] == 'N')
  129. number_of_directions_unavailable++;
  130.  
  131.  
  132.  
  133. if (number_of_directions_unavailable > 2)
  134. {
  135. maze[current_row][current_col] = 'N';
  136. return true;
  137. }
  138.  
  139. return false;
  140. }
  141.  
  142. void isDeadEndAfterRetrace(string maze[], int starting_row, int starting_col, int ending_row, int ending_col, int current_row, int current_col)
  143. {
  144. if (current_row == starting_row && current_col == starting_col)
  145. return;
  146.  
  147. if (current_row == ending_row && current_col == ending_col)
  148. return;
  149.  
  150. int number_of_directions_unavailable = 0;
  151.  
  152. // First, check EAST, which is (r, c+1)
  153. if (maze[current_row][current_col + 1] == '.' || maze[current_row][current_col + 1] == 'X' || maze[current_row][current_col + 1] == 'N' || maze[current_row][current_col + 1] == 'D')
  154. number_of_directions_unavailable++;
  155.  
  156. // Second, check NORTH, which is (r-1, c)
  157. if (maze[current_row - 1][current_col] == '.' || maze[current_row - 1][current_col] == 'X' || maze[current_row - 1][current_col] == 'N' || maze[current_row - 1][current_col] == 'D')
  158. number_of_directions_unavailable++;
  159.  
  160. // Third, check WEST, which is (r, c-1)
  161. if (maze[current_row][current_col - 1] == '.' || maze[current_row][current_col - 1] == 'X' || maze[current_row][current_col - 1] == 'N' || maze[current_row][current_col - 1] == 'D')
  162. number_of_directions_unavailable++;
  163.  
  164. // Last, check SOUTH, which is (r+1, c)
  165. if (maze[current_row + 1][current_col] == '.' || maze[current_row + 1][current_col] == 'X' || maze[current_row + 1][current_col] == 'N' || maze[current_row + 1][current_col] == 'D')
  166. number_of_directions_unavailable++;
  167.  
  168. if (number_of_directions_unavailable > 2)
  169. {
  170. maze[current_row][current_col] = 'N';
  171. return;
  172. }
  173.  
  174. return;
  175. }
  176.  
  177. bool findDirections(string maze[], int number_of_rows, int number_of_cols, int starting_row, int starting_col, int ending_row, int ending_col)
  178. {
  179. /*
  180. * Psuedo Code Approach:
  181. * First run to check if the path even exists
  182. * Checking if the path exists marks each discoverable area as a D
  183. *
  184. * For this approach because we are checking individual paths, we will use a stack
  185. *
  186. * We'll mark each point we retrace as R
  187. * Go through each D until you reach either the beginning or nowhere
  188. * If you reach the beginning, then that is the path and we will write directions
  189. * We will check the surroundings to see if it ends up in nowhere
  190. * We will then pop the stack to go back to the previous point
  191. *
  192. * One problem that arises is that if you find a path, there are still some coordinates that were pushed onto the stack that didn't lead anywhere
  193. * After we've found a path, we will write a helper program that checks every non starting and ending point to ensure that they are connected in front and behind
  194. * That is to say that each non starting and ending point R is connected to two other Rs
  195. */
  196.  
  197. /*
  198. Psuedo Code Approach #2:
  199. * First run to check if the path even exists
  200. * Checking if the path exists marks each discoverable area as a D
  201. *
  202. *
  203. */
  204.  
  205. /*
  206.  
  207. bool check_pathExists = pathExists(maze, number_of_rows, number_of_cols, starting_row, starting_col, ending_row, ending_col);
  208.  
  209. if (check_pathExists == false)
  210. {
  211. cout << "There are no directions because there is no path that exists." << endl;
  212. return false;
  213. }
  214.  
  215. */
  216.  
  217. // If a path exists, but it's because you do nothing, simply say do nothing
  218. if (starting_row == ending_row && starting_col == ending_col)
  219. {
  220. cout << "There are no directions because the start point is the same as the end point." << endl;
  221. return true;
  222. }
  223.  
  224. stack<Coord> stack_of_retraced_coords;
  225. stack_of_retraced_coords.push(Coord(ending_row, ending_col));
  226.  
  227. // Instead of popping coordinates, we will actually keep them in the stack
  228. // We will pop coordinates when we reach a dead end or reach the end
  229. while (!stack_of_retraced_coords.empty())
  230. {
  231. Coord current = stack_of_retraced_coords.top();
  232.  
  233. int current_row = current.r();
  234. int current_col = current.c();
  235.  
  236. if (current_row == starting_row && current_col == starting_col)
  237. {
  238. break;
  239. }
  240. // Now that we've put all the possibilities on the stack, let's check if the current is at a dead end or not
  241. // If it is at a dead end, we will mark that point as N and then pop it from the stack
  242. // Popping the current stack will mean we will go to the previous point and then check if is also a dead end after we updated this current point to N
  243.  
  244. while (isDeadEnd(maze, starting_row, starting_col, ending_row, ending_col, current_row, current_col))
  245. {
  246. stack_of_retraced_coords.pop();
  247.  
  248. current = stack_of_retraced_coords.top();
  249. current_row = current.r();
  250. current_col = current.c();
  251. }
  252.  
  253. // Need to make sure that we actually are moving even if it isn't a dead end
  254. int has_moved = 0;
  255.  
  256. // First, check EAST, which is (r, c+1)
  257. if (maze[current_row][current_col + 1] == 'D')
  258. {
  259. stack_of_retraced_coords.push(Coord(current_row, current_col + 1));
  260. maze[current_row][current_col + 1] = 'R';
  261. has_moved++;
  262. }
  263.  
  264. // Second, check NORTH, which is (r-1, c)
  265. if (maze[current_row - 1][current_col] == 'D')
  266. {
  267. stack_of_retraced_coords.push(Coord(current_row - 1, current_col));
  268. maze[current_row - 1][current_col] = 'R';
  269. has_moved++;
  270. }
  271.  
  272. // Third, check WEST, which is (r, c-1)
  273. if (maze[current_row][current_col - 1] == 'D')
  274. {
  275. stack_of_retraced_coords.push(Coord(current_row, current_col - 1));
  276. maze[current_row][current_col - 1] = 'R';
  277. has_moved++;
  278. }
  279.  
  280. // Last, check SOUTH, which is (r+1, c)
  281. if (maze[current_row + 1][current_col] == 'D')
  282. {
  283. stack_of_retraced_coords.push(Coord(current_row + 1, current_col));
  284. maze[current_row + 1][current_col] = 'R';
  285. has_moved++;
  286. }
  287.  
  288. if (has_moved == 0)
  289. stack_of_retraced_coords.pop();
  290. }
  291.  
  292. while (!stack_of_retraced_coords.empty())
  293. {
  294. Coord current = stack_of_retraced_coords.top();
  295. int current_row = current.r();
  296. int current_col = current.c();
  297. isDeadEndAfterRetrace(maze, starting_row, starting_col, ending_row, ending_col, current_row, current_col);
  298. stack_of_retraced_coords.pop();
  299. }
  300.  
  301. return true;
  302. }
  303.  
  304. void prunePath(string maze[], int number_of_rows, int number_of_cols, int starting_row, int starting_col, int ending_row, int ending_col)
  305. {
  306. // If a path exists, but it's because you do nothing, simply say do nothing
  307. if (starting_row == ending_row && starting_col == ending_col)
  308. return;
  309.  
  310. stack<Coord> stack_of_walkable_coords;
  311. stack_of_walkable_coords.push(Coord(starting_row, starting_col));
  312.  
  313. while (!stack_of_walkable_coords.empty())
  314. {
  315. Coord current = stack_of_walkable_coords.top();
  316.  
  317. int current_row = current.r();
  318. int current_col = current.c();
  319.  
  320. if (current_row == ending_row && current_col == ending_col)
  321. return;
  322.  
  323. // Now that we've put all the possibilities on the stack, let's check if the current is at a dead end or not
  324. // If it is at a dead end, we will mark that point as N and then pop it from the stack
  325. // Popping the current stack will mean we will go to the previous point and then check if is also a dead end after we updated this current point to N
  326.  
  327. int has_moved = 0;
  328.  
  329. // First, check EAST, which is (r, c+1)
  330. if (maze[current_row][current_col + 1] == 'R')
  331. {
  332. stack_of_walkable_coords.push(Coord(current_row, current_col + 1));
  333. maze[current_row][current_col + 1] = 'W';
  334. has_moved++;
  335. }
  336.  
  337. // Second, check NORTH, which is (r-1, c)
  338. else if (maze[current_row - 1][current_col] == 'R')
  339. {
  340. stack_of_walkable_coords.push(Coord(current_row - 1, current_col));
  341. maze[current_row - 1][current_col] = 'W';
  342. has_moved++;
  343. }
  344.  
  345. // Third, check WEST, which is (r, c-1)
  346. else if (maze[current_row][current_col - 1] == 'R')
  347. {
  348. stack_of_walkable_coords.push(Coord(current_row, current_col - 1));
  349. maze[current_row][current_col - 1] = 'W';
  350. has_moved++;
  351. }
  352.  
  353. // Last, check SOUTH, which is (r+1, c)
  354. else if (maze[current_row + 1][current_col] == 'R')
  355. {
  356. stack_of_walkable_coords.push(Coord(current_row + 1, current_col));
  357. maze[current_row + 1][current_col] = 'W';
  358. has_moved++;
  359. }
  360.  
  361. if (has_moved == 0)
  362. {
  363. maze[current_row][current_col] = 'N';
  364. stack_of_walkable_coords.pop();
  365. }
  366. }
  367.  
  368. return;
  369. }
  370.  
  371. int main()
  372. {
  373. string maze1[10] = {
  374. "XXXXXXXXXX",
  375. "X.X..X...X",
  376. "X.XX.X.XXX",
  377. "X....X.X.X",
  378. "XX.X.X...X",
  379. "XXX..X.X.X",
  380. "X...X...XX",
  381. "X.XX..X.XX",
  382. "X....X...X",
  383. "XXXXXXXXXX",
  384. };
  385.  
  386. string maze2[10] = {
  387. "XXXXXXXXXX",
  388. "X.X..X...X",
  389. "XXXX.X.XXX",
  390. "X....X.X.X",
  391. "XX.X.X...X",
  392. "XXX..X.X.X",
  393. "X...X...XX",
  394. "X.XX..X.XX",
  395. "X....X...X",
  396. "XXXXXXXXXX",
  397. };
  398.  
  399. string maze3[10] = {
  400. "XXXXXXXXXX",
  401. "XX.....XXX",
  402. "X..XX....X",
  403. "X...X...XX",
  404. "X.X.XXX..X",
  405. "XXXX..X..X",
  406. "XX....X..X",
  407. "X.......XX",
  408. "X..XXXXXXX",
  409. "XXXXXXXXXX",
  410. };
  411.  
  412. string maze4[10] = {
  413. "XXXXXXXXXX",
  414. "XX.....XXX",
  415. "X..XX....X",
  416. "X...X...XX",
  417. "X.X.XXX..X",
  418. "XXXX..X..X",
  419. "XX....X..X",
  420. "X.X.....XX",
  421. "X..XXXXXXX",
  422. "XXXXXXXXXX",
  423. };
  424.  
  425. string maze5[6] = {
  426. "XXXXXX",
  427. "XX.XXX",
  428. "XX.XXX",
  429. "X...XX",
  430. "XX.XXX",
  431. "XXXXXX",
  432. };
  433.  
  434. string maze6[10] = {
  435. "XXXXXXXXXX",
  436. "X.XXXXXXXX",
  437. "X...XXXX.X",
  438. "X.XXXXXX.X",
  439. "X.XXXXXX.X",
  440. "X.XXXXXX.X",
  441. "X.XXXXXX.X",
  442. "X.XXXXXX.X",
  443. "X........X",
  444. "XXXXXXXXXX",
  445. };
  446.  
  447. cout << "Maze 5" << endl;
  448. pathExists(maze5, 6, 6, 4, 2, 1, 2);
  449. printMaze(maze5, 6, 6);
  450. findDirections(maze5, 6, 6, 4, 2, 1, 2);
  451. printMaze(maze5, 6, 6);
  452.  
  453. cout << "Maze 1" << endl;
  454. pathExists(maze1, 10, 10, 8, 6, 1, 1);
  455. printMaze(maze1, 10, 10);
  456. findDirections(maze1, 10, 10, 8, 6, 1, 1);
  457. printMaze(maze1, 10, 10);
  458.  
  459. cout << "Maze 6" << endl;
  460. pathExists(maze6, 10, 10, 8, 8, 1, 1);
  461. printMaze(maze6, 10, 10);
  462. findDirections(maze6, 10, 10, 8, 8, 1, 1);
  463. printMaze(maze6, 10, 10);
  464.  
  465. cout << "Maze 3" << endl;
  466. pathExists(maze3, 10, 10, 4, 3, 7, 1);
  467. printMaze(maze3, 10, 10);
  468. findDirections(maze3, 10, 10, 4, 3, 7, 1);
  469. printMaze(maze3, 10, 10);
  470. prunePath(maze3, 10, 10, 4, 3, 7, 1);
  471. printMaze(maze3, 10, 10);
  472.  
  473. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!