Maze Solving Algorithm in C++

Question

I'm writing an algorithm that finds its way through a maze by sticking to a wall and moving in this order: Down - Right - Up - Left until it finds the exit. But, sometimes, it gets stuck in an infinite loop and is unable to continue. I've been trying to figure out what is wrong for hours and I've had no luck. Here's 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 have a chance in solving it, you must:

• Create a Solve() routine and recursively call itself:
  • if 1st, 2nd, 3rd, ... are true Solve has succeeded in finding a solution
  • if 1st, 2nd, 3rd, ... contains a false, it has to backtrack and find another way
• You need to build a buffer of places you've been to avoid infinite loops
  • as you make moves it needs to keep tabs on it
  • when we hit a dead end, we need to erase bad moves
  • we can implement the above by burning in a guess and removing it if it's wrong

Here's a crude 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's 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 version of the above 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's 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>