C ++中的迷宫求解算法 [英] Maze Solving Algorithm in C++

问题描述

我正在编写一种算法，可以通过粘在墙上并按以下顺序移动来找到通过迷宫的方式：下-右-上-左，直到找到出口。但是，有时它陷入无限循环，无法继续。数小时以来，我一直在努力找出问题所在，但我没有走运。这是代码

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


}

推荐答案

要想解决这个问题，您必须：

To have a chance in solving it, you must:

• 创建 Solve（）例程并递归调用自己：
  
  
  
  
  • 如果第1，第2，第3，...是真实的解决已成功找到解决方案
  
  
  • 如果第1、2、3，...包含错误，则必须回溯并找到另一种方式
  
  
  • 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
    
    
    • as您采取行动时需要保持警惕
    
    
    • 当我们陷入僵局时，我们需要消除不良举动
    
    
    • 我们可以实现上述目标通过烧掉一个猜测并在错误的情况下将其删除
    
    

    这是一个粗略的实现基于上述概念：

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

    为了说明这一点，我在Javascript中使用了上述版本：

    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>

    这篇关于C ++中的迷宫求解算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！