Snake寻路算法异常

本文关键字：异常 算法 寻路 Snake | 更新日期: 2023-09-27 18:00:37

我目前正在尝试制作一个snake寻路算法。我试着做点什么，但出现了一个我觉得很难的问题。问题是，我是以递归的方式实现算法的，它不会找到一个路径，而是搜索所有可用的路径，这会导致堆栈溢出异常，因为控制台窗口很大。

"Grid"是一个与控制台一样大的二维布尔数组，如果控制台上有类似蛇的部分，则值为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
    }
}

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

Snake寻路算法异常

你必须确保蛇不会回到它已经"访问"过的位置，否则你的代码将不得不探索无限多的可能性（在同一个四个正方形中绕一圈，一次，两次，三次，…，四十亿次，等等）。

这意味着你必须记录访问过的职位，并对照该列表进行检查。

这应该会奏效：

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

此外，专业提示：在你的位置结构中添加一个"Left"、"Right"、"Top"、"Down"方法，这些方法会在正确的方向上返回一个新的位置。这使您的代码可读性更强。

相关文章：