如何避免使用A*寻路算法时走捷径？

Question

在我的第二次尝试中，我成功计算出追溯所需的所有值。同时用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。

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

提前感谢！

- チーズパン

---

您直行的成本指标为10，对角线移动的成本指标为14是合理的，但存在一个小潜在问题。A*算法要求其正确性的近似度量低估到目标的距离。如果您使用欧几里得度量作为近似度量，则可能会高估14和10乘以根号2之间的差异，约为1％。这样微小的高估不太可能产生非常糟糕的结果，但值得考虑是否有更好的加权方式可以保持指标可接受。 - Eric Lippert

你告诉我：路径中哪些情况下会出现拐角被切断的情况？只有四种情况，所以你应该能够轻松列举它们。 - Eric Lippert

你的问题不是权重问题，而是你允许这种情况发生。你有一个方法来确定相邻节点；如果相邻节点会切角，就不要将其添加到列表中。 - Eric Lippert

我还注意到你的方法可能非常低效。只有八个可能的邻居，但每次调用此方法时，您都会检查每个单元格，以查看它是否是这八个之一。如果有一百万个单元格怎么办？您真的想问所有一百万个单元格它们是否属于这八个之一吗？ - Eric Lippert

生成一个包含八个可能邻居的列表，然后检查它们是否有效——在棋盘上，不切角等。这样你就只需要过滤八个事物，而不是一百万个事物。 - Eric Lippert

Answer 1

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

- KnowsNothing