C++中的迷宫求解算法

Maze Solving Algorithm in C++

提问by Hristijan Gjorshevski

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);
}


}

回答by Stephen Quan

To have a chance in solving it, you must:

为了有机会解决它，您必须：

• Create a Solve()routine and recursively call itself:
  • if 1st, 2nd, 3rd, ... are true Solvehas 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

• 创建一个Solve()例程并递归调用自身：
  • if 1st, 2nd, 3rd, ... is trueSolve已成功找到解决方案
  • 如果 1st, 2nd, 3rd, ... 包含一个 false，它必须回溯并找到另一种方式
• 你需要建立一个你去过的地方的缓冲区以避免无限循环
  • 当你采取行动时，它需要密切关注它
  • 当我们走到死胡同时，我们需要消除坏的动作
  • 我们可以通过猜测并在错误时将其删除来实现上述内容

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:

为了说明这一点，我在 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>

回答by MartinStettner

As Luchian already posted, the algorithm (even if implemented correctly) is not suitable to find your way out of all sort of mazes: If you have some loop inside your maze, you might just end up running around this looping wall.

正如 Luchian 已经发布的那样，该算法（即使正确实施）并不适合从各种迷宫中找到出路：如果你的迷宫中有一些循环，你可能最终会绕过这个循环墙。

Also, as it seems, you don't really generate a maze but rather a big field with walls at the borders and the "exit" somewhere inside it. An algorithm, which really "sticks to a wall" will never find the exit, if the exit is not near the wall (which, again, is currently only at the borders of your "maze").

此外，看起来，你并没有真正生成一个迷宫，而是一个边界有墙的大领域，里面有一个“出口”。如果出口不在墙附近（同样，目前仅在“迷宫”的边界处），那么真正“粘在墙上”的算法将永远找不到出口。

Since you're not removing the SomeDudes, i.e. the positions you've already been, and you're treating SomeDudethe same way as a Wall, you're slowly filling up the maze with some kind of "SomeDude-Wall": You go just down until you hit the border and then go in big counterclockwise spirals around the field, leaving a trace of SomeDudes.

由于您没有删除SomeDudes，即您已经在的位置，并且您SomeDude以与 a 相同的方式对待Wall，您正在用某种“SomeDude-Wall”慢慢填满迷宫：您只是向下直到你到达边界，然后绕着场地逆时针旋转，留下一个SomeDudes的痕迹。

Depending on your starting point and the exit, you can easily run into the situation, where all four directions are blocked, either by a "real" wall or by some previous SomeDudeyou left there. Then, none of the four if-Statements is executed and you just have an infinite loop (since nothing is changed inside the loop body).

根据您的起点和出口，您很容易遇到所有四个方向都被“真实”墙或SomeDude您之前离开的墙挡住的情况。然后，四个if-Statements 都不执行，您只有一个无限循环（因为循环体内部没有任何更改）。

For an algorithm, wich sticks to a wall (and thus would be able to find a way out of some kinds of mazes), I would suggest the following steps:

对于一个粘在墙上的算法（因此能够找到摆脱某些迷宫的方法），我建议执行以下步骤：

• First, go into one direction, until you hit a wall.
• Set your current direction, so that the wall is at your right side.
• Follow your current direction (don't forget to delete your SomeDude-trace) until either
  • You've found the exit.
  • There is no wall at your right side: In this case, turn right and go one step forward.
  • Or, there is a wall just in front of you. In this case, turn leftuntil the way ahead of you is free

• 首先，朝一个方向走，直到撞到一堵墙。
• 设置您当前的方向，使墙位于您的右侧。
• 按照您当前的方向（不要忘记删除您的SomeDude-trace），直到
  • 你已经找到出口了。
  • 您的右侧没有墙：在这种情况下，向右转并向前走一步。
  • 或者，你面前有一堵墙。在这种情况下，转左，直到你前进的道路是免费的

This way, you ensure, that there is always "the same" wall at your right side, so you "stick" to that wall.

这样，您可以确保在您的右侧总是有“相同”的墙，因此您“坚持”在那堵墙上。

Remember, that this algorithm cannot find exits, if the exit is inside some free space (since it always stick to a wall, the exit must also be near a wall to be found).

请记住，该算法无法找到出口，如果出口在某个空闲空间内（因为它总是粘在墙上，所以出口也必须靠近墙才能找到）。

For an algorithm which finds its way out of all possible mazes, you need to have some sort of backtracking: Remeber every point, where you have multiple choices to continue. Choose one way, and follow it. If it's a dead-end, go back to tha last point of decision and take the next choice. If no way leads to the exit, go to the previous last point and so on. This is a recursive approach, known as "depth-first-search" in graph theory (feel free to do a bit of googling, I'm confident, you'll find a lot of material about this :) ...)

对于能从所有可能的迷宫中找到出路的算法，您需要进行某种回溯：记住每个点，在那里您有多种选择可以继续。选择一种方式，并遵循它。如果这是一个死胡同，请回到最后的决定点并做出下一个选择。如果没有办法通向出口，则转到上一个最后一个点，依此类推。这是一种递归方法，在图论中称为“深度优先搜索”（随意使用谷歌搜索，我有信心，你会找到很多关于此的材料:) ...）

HTH Martin

HTH马丁