Получить оптимальный путь от A * - PullRequest
Новая
       6

Получить оптимальный путь от A *

0 голосов
/ 21 мая 2018

Я начал создавать алгоритм A *.Игрок должен идти снизу слева вверху справа.Существует разная стоимость поля на ячейку.Стоимость 0 означает, что клетка не может быть пройдена.

Иногда игрок прыгает, потому что в моем закрытом списке у меня нет оптимального пути, там тоже есть некоторые «неправильные» ячейки.

Вы можете посмотреть здесь

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

У меня есть 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);
}

1 Ответ

0 голосов
/ 21 мая 2018

Во-первых, вы не правильно реализовали A * и пропустили несколько точек,

  1. В вашем коде нет функции, вычисляющей расстояние до пути (G)
  2. Вы добавляете соседей вopenlist, только если он уже не содержит их, что неправильно, и вам нужно сравнить текущую общую стоимость ячейки и сравнить ее со старой в открытом списке, а если стоимость меньше, вам нужно обновить стоимость ячейки в списке...

Для хранения ссылки на предшественника текущей ячейки необходимо изменить структуру данных ячейки, рекомендуется использовать структуру, позволяющую избежать выделения GC, но структура не может иметь поле сструктура того же типа для хранения предшественника, так как он создает цикл.Если размер вашей карты небольшой, и процесс поиска пути не вызывается для каждой ячейки, все в порядке, если он реализован с использованием класса. 

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

Другой вариант - использовать LinkedList для вашего закрытого списка для отслеживания от целевой ячейки.к текущему.

Вы не поделились кодом того, как вы находите путь из закрытого списка, когда ваши вычисления закончены, я думаю, что отсюда возникает проблема с прыжками

...