2012-02-08 116 views
5

我正在写一个算法,通过坚持到墙上并按此顺序移动找到它通过迷宫的方式:向下 - 向右 - 向上 - 向左直到找到出口。但是,有时它会陷入无限循环,无法继续。我一直在努力弄清楚什么是错误的几个小时,我没有运气。下面的代码在C++中的迷宫求解算法

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


} 

回答

5

由于Luchian已经发布,该算法(即使正确实施)不适合找出一条路来的所有排序迷宫的:如果你有你的迷宫内的一些循环,你可能只是结束围绕这个循环墙跑来跑去。

另外,看起来,你并不是真的会产生一个迷宫,而是一个大的领域,在边界处有墙壁,在里面有“出口”。如果出口不在靠近墙壁的位置(同样,目前仅在“迷宫”的边界处),那么真正“坚持墙壁”的算法将永远不会找到出口。

既然你不删除SomeDude S,即位置,你已经去过了,你正在处理SomeDude作为Wall以同样的方式,你慢慢地用某种“SomeDude的填补了迷宫“墙”:你直到你到达边界,然后在场地周围逆时针旋转,留下一丝SomeDude秒。

根据你的出发点和出口,你可以很容易地遇到所有四个方向都被阻挡的情况,无论是通过“真实”的墙壁还是之前你留在那里的SomeDude。然后,执行四个if-语句中的任何一个,并且你只是有一个无限循环(因为循环体内没有任何变化)。

一种算法,至极粘到墙上(因此就能够找到出路的几种迷宫),我会建议以下步骤:

  • 首先,进入一个方向,直到你碰到一堵墙。
  • 设置您当前的方向,让墙壁位于右侧。
  • 按照你目前的方向(不要忘记删除您SomeDude -trace),直到
    • 如果你找到了出口。
    • 右侧没有墙:在这种情况下,右转并向前走一步。
    • 或者,你前面有一堵墙。在这种情况下,把离开直到在你前面的路是免费的

这种方式,可以确保,始终存在在你的右手边“一样的”墙,让你的“大棒”到那堵墙。

请记住,如果出口位于某个空闲空间内(因为它始终粘在墙上,出口也必须靠近要找到的墙),此算法无法找到出口。

对于算法找出所有可能的迷宫,你需要有一些回溯:记住每一个点,你有多个选择继续。选择一种方式,并遵循它。如果它是一个死胡同,回到最后的决定点,并采取下一个选择。如果没有办法导致退出,则转到上一个最后一点,依此类推。这是一个递归方法,在图论中被称为“深度优先搜索”(可随意做一些Google搜索,我相信,你会发现很多关于这方面的材料:) ......)

HTH 马丁

+0

感谢真棒答案,马丁。 – 2012-02-08 11:03:36

19

enter image description here

有机会解决它,你必须:

  • 创建Solve()常规和递归调用自身:
    • 如果第1,第2,第3,...是真正Solve已经成功地找到解决
    • 如果第1,第2,第3,...包含虚假的,它必须走回头路,另谋出路
  • 你需要建立的你去过避免无限循环
    • 当你做它需要保持它
    • 标签时,我们进入了死胡同运动场所的缓冲,我们需要消除坏移动
    • ,我们可以通过在猜测燃烧并除去其实现上述,如果它是错的

下面是基于上述概念的原油实现:

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