如何检查在迷宫C#上搜索的上一个路径

Question

我正在尝试编写一个解决迷宫问题的算法,但我正面临一些难以正确应用它.

算法在墙壁上运行,而不是在找到有效点后改变方向.

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

我试图实现保罗给出的答案,但却无法从中得到任何答案,我完全迷失了.

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

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

但是我为你留下了一些工作:

• 没有存储正确的路径.
• 如果有两条正确的路径,则此算法不会始终采用较短的路径,而是首先找到的路径.

Answer 2

你的墙壁是由#任何相邻的单元格中的一个或.地板,S开始和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;

然后递归调用应该自然解除.

请注意,您需要比我在那里更好地查看成功标准,并且您可能需要了解例程如何解开.这里的代码演示了如何检查相邻的墙壁.

请注意,&&只有当前一个检查在第一个位置成功时才执行下一个检查.