visual - Cómo verificar la ruta anterior buscada en un laberinto C#

hola mundo c# visual studio 2017

Question

Estoy tratando de codificar un algoritmo que resuelve un problema de laberinto, pero tengo algunas dificultades para aplicarlo correctamente.

El algoritmo se ejecuta sobre las paredes en lugar de cambiar la dirección después de encontrar el punto válido.

Código completo en Github

No entiendo claramente cómo verificar el PreviousPoint y luego, desde ese punto, verificar el próximo movimiento válido.

¿Podría alguien ayudarme a darme algunos consejos sobre en qué dirección podría ir?

class MapPathFinder
{
public bool[,] correctPath = new bool[12,12];
public int[,] previousPoint = new int[12, 12];
public bool startPointFound = false;
public bool nextValidMove(MapFile map, int y, int x)
{
if ((y == map.width) && (x == map.height)) {
return false; //Checks if at the edge and terminates the method
}
if ((map.Matrix[y, x]) == 1 ) {
return true; // check if at a wall and terminate the method
}
if (y != 0)
{
if (nextValidMove(map, y-1,x))
{
map.Matrix[y, x] = 9; //changes the color of the position
correctPath[y, x] = true;
return correctPath[y, x];
}
if (y != map.width - 1) //check if at the limit of the map
{
if (nextValidMove(map,y + 1, x))
{
map.Matrix[y, x] = 9;
correctPath[y, x] = true;
return correctPath[y, x];
}
}
if (x != 0)
{
if (nextValidMove(map, y, x - 1))
{
map.Matrix[y, x] = 9;
correctPath[y, x] = true;
return correctPath[y, x];
}
}
if (x != map.height - 1)
{
if (nextValidMove(map, y, x + 1))
{
map.Matrix[y, x] = 9;
correctPath[y, x] = true;
return correctPath[y, x];
}
}
}
return false;
}
public bool PathFinder(MapFile map)
{
for (int y = 1; y < map.width; y++)
{
for (int x = 1; x < map.height; x++)
{
var status = MapDisplay.DisplayMap(map);
if (status)
{
nextValidMove(map, x, y);
}
}
}
return true;
}

Traté de implementar la respuesta dada por Paul, pero realmente no pude obtener nada de eso y estoy completamente perdido.

Eso es lo que obtuve de tu respuesta:

public bool nextValidMove(MapFile map, int y, int x)
{
if ((y == map.width) || (x == map.height)) return false;
if(y<0 || x<0) return false;
if ((map.Matrix[y, x]) == 1) return true; // check if at a wall and terminate the method
if (map.Matrix[y, x] == 5) return map.end;
if (y - 1 >= 0 && map.Matrix[y-1, x] == 2 && !nextValidMove(map, y-1, x))
{
map.Matrix[y, x] = 9;
previousPoint[y, x] = map.Matrix[y, x];
return false;
}
// Test the East wall...
if (x + 1 <= map.width - 1 && map.Matrix[y + 1, x] == 2 && !nextValidMove(map, y, x+1))
{
map.Matrix[y, x] = 9;
previousPoint[y, x] = map.Matrix[y, x];
return false;
}
// Test the South wall...
if (y + 1 <= map.height - 1 && map.Matrix[y, x + 1] == 2 && !nextValidMove(map, y+1,x))
{
map.Matrix[y, x] = 9;
previousPoint[y, x] = map.Matrix[y, x];
return false;
}
// Test the West wall...
if (x - 1 >= 0 && map.Matrix[y, x - 1] == 2 && !nextValidMove(map, y, x-1))
{
map.Matrix[y, x] = 9;
previousPoint[y, x] = map.Matrix[y, x];
return false;
}
return false;
}

Cuando lo ejecuto me sale un error de desbordamiento de pila.

Cuando estoy revisando los puntos posibles y llamando a la función recursivamente con

!nextValidMove(map, y-1, x)

Realmente no entiendo por qué estoy revisando nextValidMove (y-1, x), ya que ya era cierto al principio de mi declaración if:

if(map.Matrix[y-1, x] == 2 && !nextValidMove(y-1,x))

Pensé en revisar el punto anterior juntos, así:

if(nextValidMove(map, y - 1, x)&&!previousPoint[y-1,x])

Pero estoy recibiendo un error de stackoverflow. Ya no tengo ni idea de cómo salir de allí.

Answer 1

He reescrito tu clase de MapPathFinder para que funcione.

class MapPathFinder
{
public const byte WALL = 1;
public const byte ROAD = 2;
public const byte START = 3;
public const byte FINISH = 5;
public const byte ALREADY_THERE = 9;
public bool NextValidMove(MapFile map, int x, int y)
{
// Check edges
if (x < 0 || x > map.width || y < 0 || y > map.height)
return false;
byte currentPosition = map.Matrix[x, y];
// Check walls or already there
if (currentPosition == WALL || currentPosition == ALREADY_THERE)
return false;
// Print
var status = MapDisplay.DisplayMap(map);
if (status)
{
// Check finish
if (currentPosition == FINISH)
{
return true; // We''ve arrived!
}
// Road
//
// Set ALREADY THERE
map.Matrix[x, y] = ALREADY_THERE;
// Left
if (NextValidMove(map, x - 1, y))
return true;
// Right
if (NextValidMove(map, x + 1, y))
return true;
// Up
if (NextValidMove(map, x, y - 1))
return true;
// Down
if (NextValidMove(map, x, y + 1))
return true;
// Not the correct path..
map.Matrix[x, y] = ROAD;
}
return false;
}
public bool PathFinder(MapFile map)
{
// Looking for start point
for (int x = 0; x < map.width; x++)
{
for (int y = 0; y < map.width; y++)
{
if (map.Matrix[x, y] == START)
return NextValidMove(map, x, y);
}
}
return false;
}
}

Sin embargo te dejé un trabajo:

• No almacenar el camino correcto.
• Si hay dos caminos correctos, este algoritmo no tomará siempre el más corto, sino el primero que se encuentre.

Answer 2

Sus paredes están determinadas por el # en cualquiera de las celdas adyacentes o a . Para el piso, S inicio y F acabado.

En ese caso, simplemente desea verificar de forma rotativa, comenzando en, digamos, Norte, luego pasar a la siguiente ronda de posición, hasta que regrese a Norte. Cada cheque debe colocarse en la pila y quitarse cuando no llega a ninguna parte. De esa manera, al menos, podrás rastrear tu camino hacia atrás cada vez.

// Test to see if we''ve found Utopia...
if(map.Matrix[x, y] == ''F'') return true;
// Test the North wall...
if(y-1>=0 && map.Matrix[x, y-1]==''.'' && !nextValidMove(map, x, y-1)) return false;
// Test the East wall...
if(x+1<=map.width && map.Matrix[x+1, y]==''.'' && !nextValidMove(map, x+1, y)) return false;
// Test the South wall...
if(y+1<=map.height && map.Matrix[x, y+1]==''.'' && !nextValidMove(map, x, y+1)) return false;
// Test the West wall...
if(x-1>=0 && map.Matrix[x-1, y]==''.'' && !nextValidMove(map, x-1, y)) return false;

Las llamadas recursivas deberían entonces desenrollarse naturalmente.

Tenga en cuenta que tendrá que ver los criterios de éxito un poco mejor que los que tengo allí, y es posible que deba jugar con la forma en que se desenvuelve la rutina. El código aquí ofrece una demostración, sin embargo, de cómo revisar las paredes adyacentes.

Observe que && solo realiza la siguiente verificación si la anterior fue exitosa en primer lugar.