4

在我第二次尝试使用 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。

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

提前致谢！

4

1 回答 1

2

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

于 2016-01-20T08:46:03.030 回答