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 回答