Cazeの迷路解決アルゴリズム

Question

私は、迷路を通り、この順番に移動するアルゴリズムを書いています。右下がり - 上左 - 出口が見つかるまで左に移動します。しかし、時には、無限ループに陥り続けることができません。私は数時間何が間違っているのか把握しようとしていましたが、運がなかったのです。あなたは迷路内のいくつかのループを持っている場合は、あなただけになるかもしれない：ここでは、コード

#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

Luchianはすでに掲載したように、アルゴリズムは、（正しく実装しても）迷路のすべての種類のあなたの方法を見つけることは適当ではないのですこのルーピング壁の周りを走っている。

また、実際には迷路を生成するのではなく、境界線に壁があり、その内側に「出口」がある大きなフィールドが生成されます。出口が壁の近くにない場合（実際にはあなたの「迷路」の境界にある）、実際には壁に固執するアルゴリズムは出口を見つけることはありません。

SomeDudeを削除していない、つまりすでに行っていたポジションを削除しておらず、Wallと同じ方法でSomeDudeを処理していると、ゆっくりと「SomeDude -Wall "：あなたは国境に当たってからフィールドの周りを反時計回りの大きな渦巻きになり、痕跡はSomeDudeになります。

開始地点と出口地点によっては、「実際の」壁面か、そこに残った以前のSomeDudeのいずれかによって、4つの方向がすべてブロックされている状況に簡単にぶつかることができます。すると、4つのステートメントのどれも実行されず、無限ループになります（ループ本体内で何も変更されないため）。アルゴリズム、壁にウィッヒスティック（ひいてはのうち、迷路のいくつかの種類の方法を見つけることができるだろう）については

、私は、次の手順をお勧めします：

• まず、入りますあなたが壁に当たるまで、一方向。
• 現在のの方向をに設定して、壁が右側になるようにします。
• 現在の指示に従います（SomeDudetraceを削除することを忘れないでください）。
  • 終了が見つかりました。
  • 右側に壁がありません：この場合、右に曲がり、一歩前に進みます。
  • または、あなたのすぐ前に壁があります。この場合は、あなたの前に道は

、あなたは常にあなたの右側にある「同じ」の壁があることを、確認してください。この方法で解放されるまではを左折、あなたの「スティック」そうその壁に

出口が空きスペースの内側にある場合（このアルゴリズムは常に壁に固執しているため、出口も壁の近くにある必要があります）、このアルゴリズムは出口を見つけることができません。

可能なすべての迷路から抜け出すアルゴリズムについては、バックトラッキングのようにする必要があります。複数の選択肢があります。一方通行を選択し、それに従ってください。それが行き止まりの場合は、決定の最後のポイントに戻り、次の選択肢を取る。終了する方法がない場合は、前の最後の点に移動するなどします。これはグラフ理論の「深さ優先検索」として知られている再帰的アプローチです（グーグルを少しでも自由にしてください、私は確信しています、これについて多くの資料を見つけるでしょう:) ...）

HTH マーティン

Answer 2

それを解決するためにチャンスを持っているために、あなたがしなければならない：

• はSolve()ルーチンを作成し、自分自身を再帰的に呼び出す：
  • 第一、第二、第三、...ある真Solveは第一、第二、第三は、...偽が含まれている場合、それは
  別の方法を後戻りして見つけることがある解決策
• を見つけることに成功した場合
• あなたは、あなたがそれは我々が死んで終わりを打ったとき、それ
• 上のタブを保つ必要がある動きをするように無限ループ
  • を避けるためにしてきた場所のバッファを構築する必要があり、我々は悪い消去する必要があります移動する
  • それは

間違っているならば、我々は推測に燃えて、それを除去することにより、上記のを実装することができますここでは上記の概念に基づいて、粗製の実装です：素晴らしい答え、マーティンのため

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