在我第二次尝试使用 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。
我认为这是阻止我完成算法的最后一件事,所以我期待任何帮助或建设性的意见。
提前致谢!