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. 您的代码中没有计算到目前为止的路径距离的函数(六)
2. 只有当邻居不包含时，您才将邻居添加到 openlist已经，这是错误的，你必须比较当前的单元格总数cost 并与 openlist 中的旧版本进行比较，如果cost 少了你必须更新列表中的 cell cost...

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

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

另一种选择是将 LinkedList 用于您的封闭列表以从目标单元格回溯到当前单元格。

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