Algoritmo de resolución de laberinto en C++

Question

Estoy escribiendo un algoritmo que encuentra su camino a través de un laberinto pegándose a una pared y moviéndose en este orden: Abajo - Derecha - Arriba - Izquierda hasta que encuentre la salida. Pero, a veces, se bloquea en un ciclo infinito y no puede continuar. He estado tratando de descubrir qué está mal durante horas y no he tenido suerte. Aquí está el código

#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

Como Luchian ya publicado, el algoritmo (incluso si se aplica correctamente) no es adecuado para encontrar su camino fuera de todo tipo de laberintos: Si tiene alguna bucle dentro de su laberinto, que sólo podría terminar corriendo por esta pared de bucles.

Además, como parece, en realidad no se genera un laberinto sino un gran campo con paredes en los bordes y la "salida" en algún lugar dentro de él. Un algoritmo que realmente "se adhiere a una pared" nunca encontrará la salida, si la salida no está cerca de la pared (que, de nuevo, actualmente solo está en los bordes de su "laberinto").

Desde que no estás eliminando los SomeDude s, es decir, las posiciones que ya ha sido, y se está tratando SomeDude la misma manera que un Wall, que está poco a poco llenando el laberinto con algún tipo de "SomeDude -Wall ": baja hasta que tocas el borde y luego das grandes vueltas en sentido antihorario alrededor del campo, dejando un rastro de SomeDude s.

Dependiendo de su punto de partida y de la salida, puede acceder fácilmente a la situación, donde las cuatro direcciones están bloqueadas, ya sea por una pared "real" o por algún SomeDude anterior que dejó allí. Entonces, ninguno de los cuatro if -Declaraciones se ejecuta y usted acaba de tener un bucle infinito (ya que nada se cambia dentro del cuerpo del bucle).

Para un algoritmo, cosa que se pega a una pared (y por tanto sería capaz de encontrar una manera de salir de algunos tipos de laberintos), sugeriría los siguientes pasos:

• En primer lugar, entran en una dirección, hasta que golpees una pared.
• Establezca su dirección actual , de modo que la pared esté a su lado derecho.
• Siga su dirección actual (no se olvide de eliminar su SomeDude -trace) hasta que
  • Usted ha encontrado la salida.
  • No hay pared en su lado derecho: en este caso, gire a la derecha y avance un paso adelante.
  • O bien, hay una pared justo en frente de usted. En este caso, gire izquierda hasta que el camino por delante de usted es libre de

De esta manera, se asegura, que no siempre es "el mismo" pared en el lado derecho, por lo que "palo" a esa pared

Recuerde que este algoritmo no puede encontrar salidas, si la salida está dentro de un espacio libre (dado que siempre se pega a una pared, la salida también debe estar cerca de una pared para encontrarla).

Para un algoritmo que encuentra su salida de todos los laberintos posibles, necesita tener algún tipo de retrocediendo: recuerde cada punto, donde tiene múltiples opciones para continuar. Elija una forma y sígala. Si es un callejón sin salida, regrese al último punto de decisión y tome la siguiente decisión.Si no hay camino que conduzca a la salida, vaya al último punto anterior y así sucesivamente. Este es un enfoque recursivo, conocido como "búsqueda de profundidad en primer lugar" en la teoría de grafos (no dudes en hacer un poco de google, estoy seguro, encontrarás un montón de material sobre esto :) ...)

HTH Martin

Answer 2

para tener la oportunidad de resolverlo, es necesario:

• Crear una rutina recursiva Solve() y llamarse a sí misma:
  • si primero, segundo, tercero, ... son verdaderos Solve ha logrado encontrar una solución
  • si primero, segundo, tercero, ... contiene una falsa, tiene que dar marcha atrás y encontrar otra manera
• es necesario construir un buffer de lugares que ha sido evitar bucles infinitos
  • mientras hace movimientos necesarios para mantener control sobre ella
  • cuando llegamos a un callejón sin salida, tenemos que borrar el mal mueve
  • Podemos implementar lo anterior por la quema de una conjetura y retirar, si es que está mal

He aquí una aplicación crudo basado en los conceptos anteriores:

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