Как проверить предыдущий путь на лабиринте С#

Я пытаюсь закодировать алгоритм, который решает проблему лабиринта, но мне сложно скомпрометировать его.

Алгоритм проходит через стены вместо изменения направления после нахождения действительной точки.

Я не понимаю, как проверить предыдущую точку, а затем с этой точки проверить следующий допустимый ход.

Может ли кто-нибудь помочь мне дать мне несколько советов о том, в каком направлении я мог бы пойти?

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

Я попытался реализовать ответ, данный Павлом, но не мог никуда от него уйти, и я полностью потерялся.

Вот что я получил от вашего ответа:

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

Когда я запускаю его, я получаю ошибку.

Когда я проверяю возможные точки и вызывая функцию рекурсивно с помощью

!nextValidMove(map, y-1, x)

Я действительно не понимаю, почему я проверяю nextValidMove (y-1, x), поскольку он уже был прав в начале моего оператора if:

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

Я думал о проверке предыдущей точки вместе, например:

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

Но я получаю ошибку stackoverflow. Я понятия не имею, как выйти оттуда больше.

Ответ 1

Я перезаписал ваш класс MapPathFinder, чтобы он работал.

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

Однако я оставил для вас определенную работу:

Отсутствует правильный путь.
Если есть два правильных пути, этот алгоритм не будет всегда короче, но первый найден.

Ответ 2

Ваши стены определяются тем, что в любой из соседних ячеек есть # или . для пола, S start и F.

В этом случае вы хотите просто проверить ротацию, начиная с, скажем, на север, затем переместиться на следующую позицию, пока вы не вернетесь на Север. Каждая проверка должна быть нажата на стек и выскользнула, когда она никуда не исчезла. Таким образом, по крайней мере, вы сможете каждый раз прослеживать свой путь назад.

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

Рекурсивные вызовы должны затем разворачиваться естественным образом.

Обратите внимание, что вам нужно будет взглянуть на критерии успеха немного лучше, чем я есть, и вам, возможно, придется поиграть с тем, как рутина раскручивается. Здесь приведен код, демонстрирующий, как проверить ваши прилегающие стены.

Обратите внимание, что && выполняет только следующую проверку, если предыдущий был успешным в первую очередь.