Исправление реализации A * в C #

Question

Итак, я реализовал алгоритм A * в Unity C #, чтобы провести несколько тестов для создания 2D-игры. Я знаю, что есть несколько компонентов, которые помогут вам в этом, но я хочу попробовать себя только для испытания.

Я в основном прочитал, как A * должен вести себя, и перевел поведение в код. Это почти работает. Но есть некоторые случаи, когда соседние плитки имеют одинаковый счет (расстояние до Манхэттена + расстояние от источника), и вы в конечном итоге получаете путь, который ведет к месту назначения, но не самый короткий. Как вы можете видеть на изображении, эти две соседние плитки имеют одинаковую оценку, но я выбираю случайную единицу в этой точке ... (На рисунке ниже начальной точкой является кошка, а красным крестиком - точка назначения Зеленые полупрозрачные файлы - это расчетный путь)

Я думал, что, поскольку плиток не так много, я мог бы рассчитать 4 различных пути из 4 начальных соседних плиток, сохранить действительные в массиве, а затем просто использовать самые короткие, но, возможно, это будет слишком много накладных расходов и есть другое решение?

Для расчета расстояния я использую базовый расчет:

private int CalculateManhattanDistance(int x1, int x2, int y1, int y2)
{
        return Mathf.Abs(x1 - x2) + Mathf.Abs(y1 - y2);
}

Answer 1

Может быть, это поможет вам понять, на что указывали @ Zdeněk Jelínek и @Peter Wishart. OpenSet (также называемый frontier), обычно это PriorityQueue . Узлы очереди сортируются в соответствии с их приоритетами. Приоритет узла рассчитывается как сумма стоимости до настоящего времени (количество шагов в вашем случае) и эвристического расстояния (Манхэттен в вашем случае). Поэтому, как только A * достигнет узла с приоритетом 11, он прекратит исследовать этот путь и продолжит работу с остальными (синий круг)

Answer 2

Я рекомендую проверить псевдокод для A * , например. в Википедии против вашего кода.

Основываясь на этом псевдокоде, вы реализуете данные алгоритма следующим образом, я подозреваю, что вы упростили некоторые из них:

        var closedSet = new HashSet<GraphNode>();
        var openSet = new List<GraphNode>{startNode};
        var cameFrom = new Dictionary<GraphNode, GraphNode>();
        var gScore = new Dictionary<GraphNode, double>();
        var fScore = new Dictionary<GraphNode, double>();

Когда алгоритм делает неправильный первый выбор для эвристики, как в этом тестовом примере, он первоначально оценит движение в неправильном направлении. Но это не проблема, как следует:

• Выберите открытый узел с самым низким fScore
• Оцените всех достижимых соседей (например, включая узел слева начального узла в первой итерации вашего примера)
• Обновление gScore с фактическим расстоянием (через cameFrom)
• Обновление fScore с фактическим расстоянием плюс расчетное (например, Манхэттен) расстояние до цели
• Перемещение оцененных узлов с openSet на closedSet

Это означает, что узлы вдоль «неправильного» пути будут вычислять увеличение фактических + ожидаемых расстояний до такой степени, что алгоритм начнет выбирать другие open узлы, например. «правый» узел с 1-й итерации.