c# - 蛇形寻路算法异常

Question

我目前正在尝试制作蛇寻路算法。我试图做点什么，但出现了一个我觉得很难的问题。问题是我正在以一种递归方式实现算法，这种方式没有找到一条路径，而是搜索所有可用路径，这导致由于控制台窗口大小过大而导致堆栈溢出异常。

“Grid”是一个二维 bool 数组，与控制台一样大，如果控制台上有类似蛇的一部分，则值为 true。

Direction 是一个包含 Up、Down、Left、Right 值的枚举。 Position 是一个包含两个称为 X 和 Y 的整数的结构。

ScheduledDirections 是一个包含方向的列表，将来会用于在控制台上绘制蛇。

我想做的是快速向该列表添加一条可用路径。 我知道像 A* 这样的寻路算法，但我发现它太复杂且难以实现。

这是我用来查找可用路径的方法:

private static void FindAvailablePath(Position currentPosition, Direction currentDirection)
{
    // break if the snake's path search has ended or it went out of the console
    if (currentPosition.X < 0 || currentPosition.X >= Console.WindowWidth ||
        currentPosition.Y < 0 || currentPosition.Y >= Console.WindowHeight ||
        AIController.isReady)
    {
        return;
    }

    // break if there is something that is blocking the snake's path
    if (Snake.Grid[currentPosition.X, currentPosition.Y])
    {
        return;
    }

    // break if the snake has reached its destination
    if (currentPosition.Equals(AIController.Destination))
    {
        AIController.isReady = true;
        return;
    }

    // if the current path is available, adds it to the collection and checks for the next one
    if (!Snake.Grid[currentPosition.X, currentPosition.Y])
    {
        AIController.scheduledDirections.Add(currentDirection);

        FindAvailablePath(new Position(currentPosition.X + 1, currentPosition.Y), Direction.Right); // right
        FindAvailablePath(new Position(currentPosition.X, currentPosition.Y - 1), Direction.Up);    // up
        FindAvailablePath(new Position(currentPosition.X - 1, currentPosition.Y), Direction.Left);  // left
        FindAvailablePath(new Position(currentPosition.X, currentPosition.Y + 1), Direction.Down);  // down
    }
}

如果有人有更好的想法，我会很高兴听到他们。 谢谢!

Answer 1

您必须确保蛇不会回到它已经“访问过”的位置，否则您的代码将不得不探索无限多的可能性(在相同的四个方 block 中圈出一次、两次、三次, ... , 四十亿次等)。

这意味着您必须记录访问过的职位并对照该列表进行核对。

这应该可以解决问题:

private static void FindAvailablePath(Position currentPosition, Stack<Position> previousPositions, Direction currentDirection, Stack<Drection> previousDirections)
{
    // break if the snake's path search has ended or it went out of the console
    if (currentPosition.X < 0 || currentPosition.X >= Console.WindowWidth ||
        currentPosition.Y < 0 || currentPosition.Y >= Console.WindowHeight)
    {
        return;
    }

    // break if there is something that is blocking the snake's path
    if (Snake.Grid[currentPosition.X, currentPosition.Y])
    {
        return;
    }

    // break if the snake has reached its destination
    if (currentPosition.Equals(AIController.Destination))
    {
        if(AIController.scheduledDirections == null || AIController.scheduledDirections.Count > previousDirections.Count + 1)
        {
            AIController.scheduledDirections = previousDirections.ToList();
            AIController.scheduledDirections.Add(currentDirection);
        }
        return;
    }

    // Break if previously visited
    if(previousPositions.Contains(currentPosition))
    {
        return;
    }


    // if the current path is available, adds it to the collection and checks for the next one
    previousPositions.Push(currentPosition);
    previousDirections.Push(currentDirection);

    FindAvailablePath(new Position(currentPosition.X + 1, currentPosition.Y), previousPositions, Direction.Right, previousDirections); // right
    FindAvailablePath(new Position(currentPosition.X, currentPosition.Y - 1), previousPositions, Direction.Up, previousDirections);    // up
    FindAvailablePath(new Position(currentPosition.X - 1, currentPosition.Y), previousPositions, Direction.Left, previousDirections);  // left
    FindAvailablePath(new Position(currentPosition.X, currentPosition.Y + 1), previousPositions, Direction.Down, previousDirections);  // down

    previousPositions.Pop();
    previousDirections.Pop();
}

此外，专业提示:向您的位置结构添加“左”、“右”、“上”、“下”方法，以返回正确方向的新位置。这使您的代码更具可读性。