c# - 如何检查在迷宫 C# 上搜索的先前路径

Question

我正在尝试编写解决迷宫问题的算法，但我在正确应用它时遇到了一些困难。

算法在找到有效点后不改变方向而是直接翻墙。

Complete Code on Github

我不清楚如何检查 previousPoint 然后从该点检查下一个有效移动。

有人可以帮我提供一些建议，告诉我该往哪个方向走吗？

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

我试图实现 Paul 给出的答案，但无法真正从中得到任何结果，我完全迷失了。

这就是我从你的回答中得到的:

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))

我想到一起检查previousPoint，像这样:

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

但是我遇到了 stackoverflow 错误。我不知道如何离开那里了。

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

但是我给你留了一些工作:

• 没有存储正确的路径。
• 如果有两条正确的路径，该算法不会总是选择较短的路径，而是选择第一个找到的路径。