c# - 获取从A*出发的最优路径

Question

我开始创建 A* 算法。玩家应该从左下角走到右上角。每个单元有不同的现场成本。成本为 0 意味着该单元不适合步行。

有时玩家会跳来跳去，因为在我的封闭列表中我没有最佳路径，其中也有一些“错误”的单元格。

你可以看这里

https://cdn.discordapp.com/attachments/370618181892571136/446345906464358410/zgzugzzu.gif

我有一个 map 对象，它创建 map 并将所有 cell 对象保存在 cell 类型的二维数组中。每个单元格都知道自己的字段成本，但它们不需要知道自己的位置，因为数组通过传入 x 和 y 值来了解它。

一些解释说，我必须存储当前检查节点的前驱，并在使用此路径与其他路径时比较当前的成本值。

我该怎么做？

我当前的代码

private List < Vector2Int > openCells = new List < Vector2Int > ();
private List < Vector2Int > closedCells = new List < Vector2Int > ();

private void CalculatePath() {
 openCells.Clear();
 closedCells.Clear();

 openCells.Add(Settings.startPosition);

 Vector2Int currentCellPosition = Settings.startPosition;

 while (!PositionEquals(currentCellPosition, Settings.targetPosition) && openCells.Count > 0) {
  Vector2Int cheapestCellPosition = openCells
   .OrderBy(x => GetCostToTarget(x, Settings.targetPosition) + GetCell(x).Cost)
   .First();

  AddNeighbourPosition(cheapestCellPosition, Vector2Int.up);
  AddNeighbourPosition(cheapestCellPosition, Vector2Int.left);
  AddNeighbourPosition(cheapestCellPosition, Vector2Int.down);
  AddNeighbourPosition(cheapestCellPosition, Vector2Int.right);

  closedCells.Add(cheapestCellPosition);
  openCells.Remove(cheapestCellPosition);

  currentCellPosition = cheapestCellPosition;
 }
}

private void AddNeighbourPosition(Vector2Int currentPosition, Vector2Int neighbourDirection) {
 Vector2Int targetPosition = currentPosition + neighbourDirection;

 if (CellExistsOnMap(targetPosition)) {
  if (CellIsWalkable(targetPosition)) {
   if (!CellExamined(targetPosition)) {
    openCells.Add(targetPosition);
   }
  }
 }
}

private bool PositionEquals(Vector2Int startPosition, Vector2Int targetPosition) {
 return startPosition.Equals(targetPosition);
}

private bool CellIsWalkable(Vector2Int position) {
 return GetCell(position).Cost != 0;
}

private Cell GetCell(Vector2Int position) {
 return map.Cells[position.x, position.y];
}

private int GetCostToTarget(Vector2Int startPosition, Vector2Int targetPosition) {
 return Mathf.Abs(startPosition.x - targetPosition.x) + Mathf.Abs(startPosition.y - targetPosition.y);
}

private bool CellExistsOnMap(Vector2Int position) {
 int horizontalLength = Settings.fields.GetLength(0);
 int verticalLength = Settings.fields.GetLength(1);
 Rect mapRect = new Rect(0, 0, horizontalLength, verticalLength);

 return mapRect.Contains(position);
}

private bool CellExamined(Vector2Int position) {
 return openCells.Contains(position) || closedCells.Contains(position);
}

Answer 1

首先，你没有正确实现 A* 并且错过了一些要点，

1. 您的代码中没有计算到目前为止路径距离的函数 (G)
2. 仅当 openlist 不包含邻居时，才将它们添加到 openlist 中 已经，这是错误的，你必须比较当前的单元总数 cost 并与 openlist 中的旧值进行比较，如果 成本较低，您必须更新列表中的单元成本...

为了保存对当前单元格前驱的引用，您需要更改单元格数据结构，建议使用结构体来避免GC分配，但结构体不能具有相同类型结构的字段来存储前驱体因为它创建了一个循环。 如果您的 map 尺寸很小并且寻路过程不是按单元提前调用，那么使用类实现它就可以了。

public class Cell
{
public Vector2Int Position { get;set;}
public int Cost {get;set;}
public Cell Parent {get;set;}
}

另一种选择是使用 LinkedList 作为关闭列表来从目标单元格追溯到当前单元格。

你还没有分享当你的计算结束时如何从关闭列表中找到路径的代码，我相信跳跃问题来自那里