c# - 如何避免使用 A* 寻路偷工减料？

在我第二次尝试使用 A* 时，我设法计算了回溯所需的所有值。还用 S 标记起始单元格，用 B 阻止，用 F 标记目标单元格。

现在对于回溯，我将简单地跟随具有最低 G 值的单元格，从目标单元格开始。

在这里，我将遵循 G=24 => G=10 => S。

如您所见，此解决方案将创建一条无效路径，因为在这种情况下它会穿过墙壁。

在计算网格的值时，这与切角一起挂起。正如你在这里看到的。一个人会回溯:G=50 => G= 40，这里接下来会取 G=20。这导致切角。

我认为在计算每个相邻单元格的值时会出现这个问题。如果在将相邻单元格添加到当前单元格时设置一些限制，也许我可以避免这种情况？

public List<Cell> GetAdjacent(Cell _currentCell, List<Cell> _closedList, List<Cell> _gridList)
    {
        List<Cell> adjacentList = new List<Cell>();
        List<Cell> gridList = _gridList;
        List<Cell> closedList = _closedList;
        Cell currentCell = _currentCell;

        foreach (Cell cell in gridList)
        {
            bool containedInClosedList = closedList.Any(c => c.id == cell.id);

            if (!cell.blocked && !containedInClosedList &&
                ((cell.positionCR.X == currentCell.positionCR.X - 1 && cell.positionCR.Y == currentCell.positionCR.Y) ||
                (cell.positionCR.X == currentCell.positionCR.X + 1 && cell.positionCR.Y == currentCell.positionCR.Y) ||
                (cell.positionCR.X == currentCell.positionCR.X && cell.positionCR.Y == currentCell.positionCR.Y - 1) ||
                (cell.positionCR.X == currentCell.positionCR.X && cell.positionCR.Y == currentCell.positionCR.Y + 1) ||
                (cell.positionCR.X == currentCell.positionCR.X - 1 && cell.positionCR.Y == currentCell.positionCR.Y - 1) ||
                (cell.positionCR.X == currentCell.positionCR.X - 1 && cell.positionCR.Y == currentCell.positionCR.Y + 1) ||
                (cell.positionCR.X == currentCell.positionCR.X + 1 && cell.positionCR.Y == currentCell.positionCR.Y - 1) ||
                (cell.positionCR.X == currentCell.positionCR.X + 1 && cell.positionCR.Y == currentCell.positionCR.Y + 1)))
            {
                adjacentList.Add(cell);
            }

        }



        return adjacentList;
    }

我定义的自定义成本也会有问题吗？我为直线单元格取了 G=10，对角单元格取了 G=14。

我认为这是阻止我完成算法的最后一件事，所以我期待任何帮助或 build 性的意见。

提前致谢!

最佳答案

正如埃里克在上面的评论中提到的那样，您可以生成一个包含八个可能邻居的列表，并检查它们是否有效。这里的有效不仅意味着检查它们是否被阻塞，您还应该在这里检查切角。

关于c# - 如何避免使用 A* 寻路偷工减料？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17492124/