Algorithm for solving a maze in C ++

Question

I am writing an algorithm that makes its way through the maze, sticking to the wall and moving in this order: Down - Right - Up - Left until it finds a way out. But sometimes it gets stuck in an endless cycle and cannot continue. I tried to find out what was wrong for several hours, and I was out of luck. Here is the code

#include <iostream> #include <windows.h> const int MazeWidth = 30; const int MazeHeight = 20; const char MazeExit = '$'; const char Wall = '#'; const char Free = ' '; const unsigned char SomeDude = 254; COORD MazeExitCoords; COORD StartingPoint; using namespace std; char Maze [MazeHeight][MazeWidth]; void FillDaMaze(){ MazeExitCoords.X = MazeWidth - 20; MazeExitCoords.Y = 2; StartingPoint.X = 3; StartingPoint.Y = MazeHeight - 3; for(int i = 0; i < MazeHeight; i++){ for(int ii = 0; ii < MazeWidth; ii++){ if(i == 0 || i == MazeHeight - 1 || ii == 0 || ii == MazeWidth - 1){ Maze[i][ii] = Wall; } else{ Maze[i][ii] = Free; } if(i == MazeExitCoords.Y && ii == MazeExitCoords.X){ Maze[i][ii] = MazeExit; } else if(i == StartingPoint.Y && ii == StartingPoint.X){ Maze[i][ii] = SomeDude; } } } } void PrintDaMaze(int color){ SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),color); for(int i = 0; i < MazeHeight; i++){ for(int ii = 0; ii < MazeWidth;ii++){ cout << Maze[i][ii]; } cout << endl; } } void FindYourWayThroughTheMaze(){ if(Maze[StartingPoint.Y + 1][StartingPoint.X] != Wall && Maze[StartingPoint.Y + 1][StartingPoint.X ] != SomeDude){ StartingPoint.Y++; } else if(Maze[StartingPoint.Y][StartingPoint.X + 1] != Wall && Maze[StartingPoint.Y][StartingPoint.X + 1] != SomeDude){ StartingPoint.X++; } else if(Maze[StartingPoint.Y - 1][StartingPoint.X] != Wall && Maze[StartingPoint.Y - 1][StartingPoint.X ] != SomeDude){ StartingPoint.Y--; } else if(Maze[StartingPoint.Y][StartingPoint.X - 1] != Wall && Maze[StartingPoint.Y][StartingPoint.X - 1] != SomeDude){ StartingPoint.X--; } Maze[StartingPoint.Y][StartingPoint.X] = SomeDude; } int main(){ FillDaMaze(); PrintDaMaze(10); while(StartingPoint.X != MazeExitCoords.X || StartingPoint.Y != MazeExitCoords.Y){ FindYourWayThroughTheMaze(); system("CLS"); PrintDaMaze(10); Sleep(50); } } 

Answer 1

To be able to solve it, you must:

• Create a Solve() procedure and call yourself recursively:
  • if 1st, 2nd, 3rd, ... true Solve managed to find a solution
  • if the 1st, 2nd, 3rd, ... contains a lie, he must return and find another way
• You need to create a buffer from the places you were to avoid endless loops
  • when you make moves you need to keep track of this
  • when we hit a dead end we need to erase bad moves
  • we can implement the above by writing down the assumption and deleting it if it is incorrect

Here is a rough implementation based on the above concepts:

 #include "stdafx.h" #include <stdio.h> const int MazeHeight = 9; const int MazeWidth = 9; char Maze[MazeHeight][MazeWidth + 1] = { "# #######", "# # #", "# ### # #", "# # # #", "# # # ###", "# # # #", "# ### # #", "# # #", "####### #", }; const char Wall = '#'; const char Free = ' '; const char SomeDude = '*'; class COORD { public: int X; int Y; COORD(int x = 0, int y = 0) { X = x, Y = y; } COORD(const COORD &coord) { X = coord.X; Y = coord.Y; } }; COORD StartingPoint(1, 0); COORD EndingPoint(7, 8); void PrintDaMaze() { for (int Y = 0; Y < MazeHeight; Y++) { printf("%s\n", Maze[Y]); } printf("\n"); } bool Solve(int X, int Y) { // Make the move (if it wrong, we will backtrack later. Maze[Y][X] = SomeDude; // If you want progressive update, uncomment these lines... //PrintDaMaze(); //Sleep(50); // Check if we have reached our goal. if (X == EndingPoint.X && Y == EndingPoint.Y) { return true; } // Recursively search for our goal. if (X > 0 && Maze[Y][X - 1] == Free && Solve(X - 1, Y)) { return true; } if (X < MazeWidth && Maze[Y][X + 1] == Free && Solve(X + 1, Y)) { return true; } if (Y > 0 && Maze[Y - 1][X] == Free && Solve(X, Y - 1)) { return true; } if (Y < MazeHeight && Maze[Y + 1][X] == Free && Solve(X, Y + 1)) { return true; } // Otherwise we need to backtrack and find another solution. Maze[Y][X] = Free; // If you want progressive update, uncomment these lines... //PrintDaMaze(); //Sleep(50); return false; } int _tmain(int argc, _TCHAR* argv[]) { if (Solve(StartingPoint.X, StartingPoint.Y)) { PrintDaMaze(); } else { printf("Damn\n"); } return 0; } 

To illustrate, I have a higher version in Javascript:

 const MazeWidth = 9 const MazeHeight = 9 let Maze = [ "# #######", "# # #", "# ### # #", "# # # #", "# # # ###", "# # # #", "# ### # #", "# # #", "####### #" ].map(line => line.split('')) const Wall = '#' const Free = ' ' const SomeDude = '*' const StartingPoint = [1, 0] const EndingPoint = [7, 8] function PrintDaMaze() { //Maze.forEach(line => console.log(line.join(''))) let txt = Maze.reduce((p, c) => p += c.join('') + '\n', '') let html = txt.replace(/[*]/g, c => '<font color=red>*</font>') $('#mazeOutput').html(html) } async function Solve(X, Y) { // Make the move (if it wrong, we will backtrack later. Maze[Y][X] = SomeDude; // If you want progressive update, uncomment these lines... PrintDaMaze() await sleep(100) // Check if we have reached our goal. if (X == EndingPoint[0] && Y == EndingPoint[1]) { return true } // Recursively search for our goal. if (X > 0 && Maze[Y][X - 1] == Free && await Solve(X - 1, Y)) { return true } if (X < MazeWidth && Maze[Y][X + 1] == Free && await Solve(X + 1, Y)) { return true } if (Y > 0 && Maze[Y - 1][X] == Free && await Solve(X, Y - 1)) { return true } if (Y < MazeHeight && Maze[Y + 1][X] == Free && await Solve(X, Y + 1)) { return true } // Otherwise we need to backtrack and find another solution. Maze[Y][X] = Free // If you want progressive update, uncomment these lines... PrintDaMaze() await sleep(100) return false } function sleep(ms) { return new Promise((resolve) => setTimeout(resolve, ms)) } (async function() { if (await Solve(StartingPoint[0], StartingPoint[1])) { console.log("Solved!") PrintDaMaze() } else { console.log("Cannot solve. :-(") } })() 

 <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script> <pre id="mazeOutput"> </pre> 

Answer 2

As Luchian already wrote, the algorithm (even if it is executed correctly) is not suitable in order to find a way out of all kinds of labyrinths: if you have a loop inside your labyrinth, you can simply run along this loop wall.

In addition, as it seems to you, you really do not create a maze, but rather a large field with walls on the borders and an “exit” somewhere inside it. An algorithm that really "sticks to the wall" will never find a way out unless the way out is next to the wall (which again is only at the borders of your "maze").

Since you are not SomeDude s, that is, the positions that you have already been, and you treat SomeDude same as Wall , you slowly fill the maze of some “SomeDude-Wall”: you go down until you click on the border and then go to the big opponents counterclockwise around the field, leaving a trace of SomeDude s.

Depending on your starting point and exit, you can easily encounter a situation where all four directions are blocked, either by a “real” wall, or by some previous SomeDude that you left there. Then none of the four if -Statements is executed, and you just have an infinite loop (since nothing changes in the loop body).

For an algorithm that attaches to a wall (and therefore can find a way out of some types of mazes), I would suggest the following steps:

• First, go in one direction until you click on the wall.
• Set the current direction so that the wall is on the right.
• Follow your current direction (remember to remove SomeDude -trace) until
  • You have found a way out.
  • There is no wall on the right side: in this case, turn right and take a step forward.
  • Or there is a wall right in front of you. In this case, turn left until your path is clear.

This way you guarantee that there is always the “same” wall on your right side, so you stick to that wall.

Remember that this algorithm cannot find the outputs if the output is inside some free space (since it always sticks to the wall, the output must also be near the wall to be found).

For an algorithm that finds its way out of all the possible mazes, you need to have some kind of rollback: remember every point where you have several options for continuing. Choose one of the methods and follow it. If this is a dead end, go back to the last decision point and make the next choice. If no path exits, go to the previous last point and so on. This is a recursive approach, known as "depth search in graph theory" (feel free to do some search queries, I'm sure you will find a lot of material about this :))

NTN Martin