Basic A * - это:
While we're not close enough to the / a destination
Take the point that we have now, with the lowest expected total cost (so known cost up to this point plus estimated remaining cost).
Calculate cost for all surrounding locations & add them back to the priority queue with their expected total cost.
return route that we followed to the closest point
В официальной терминологии A * G-оценка - это стоимость, чтобы добраться туда.H-оценка - это оценка того, куда вы хотите попасть.
Крайности, если ваш H-показатель всегда завышен;новый счет (оценка + новая стоимость) всегда будет ниже оценки предыдущего квадрата + стоимость, поэтому вы будете ближе к цели.Если ваш H-показатель всегда недооценивает (или равен 0, или что-то еще), вы всегда будете предпочитать квадраты ближе к вашей точке отправления, поскольку они будут иметь более низкую стоимость, поэтому вы в основном заполняете эту позицию.
Вы можете использовать A * с теоретической точки зрения или с практической точки зрения.Теоретически, вы никогда не можете переоценить стоимость любой ссылки.Это означает, что вы всегда найдете наиболее эффективный маршрут, но он займет больше времени, поскольку вы расширите намного больше узлов.
Использование его с практической точки зрения допускает слегка недопустимую эвристику (те, которыеможно немного переоценить).Маршрут, который вы найдете, скорее всего, будет немного неоптимальным, но не должен быть слишком плохим для использования в игре.Однако вычисления становятся намного быстрее, поскольку вы больше не расширяете все.Одна (медленная) реализация, которую я сделал, заняла 6 минут на карте 1k * 1k с обычной эвристической дистанцией триггера, но всего несколько секунд с увеличенным временем 3. Маршруты не были слишком разными.Эвристическое умножение на 5 сделало маршруты в основном «билайном» и все еще намного быстрее, но это непривычно.
ЗАПРОСИТЕ свой прямой вопрос: это второй квадрат, который вы оцениваете.У вас есть запланированные дороги от O до A, B, C (с заданной стоимостью G для каждого из этих маршрутов).Теперь предположим, что есть трасса от О до А вместо В, а не грунтовая дорога от О до В. Это означает, что проход через А проходит быстрее.При расширении A он просматривает все окружающие квадраты и добавляет стоимость + эвристику в открытый список, если его там еще не было.Если он был там, он видит, быстрее ли новый маршрут (ниже G, чтобы добраться до этого квадрата), и только если это так, он его заменяет.
Итак, в вашем примере он добавляет O-> A-> D к списку и затем проверяет, является ли O-> A-> B быстрее, чем O-> B.
- приложение
Открытый список: 2 / A (через O), 5 / B (через O), 7 / C (через O)
Закрытый список: 0 / O (источник / через ничто)
Возьмите A, поскольку это самая низкая стоимость на данный момент.Затем для каждого соседа A рассчитайте стоимость, чтобы добраться туда.
- Если для него уже есть запись и ее стоимость ниже, чем нам известно, замените эту запись.
- Если нет текущей записи, добавьте ее.
Работа на A, с дорогами стоимостью от 2 до B и от 3 до D. Стоимость проезда от B до A составляет 4где текущая запись 5. Таким образом, мы заменим ее.D там нет, поэтому мы добавляем его.
Открытый список: 4 / B (через A), 5 / D (через A), 7 / C (через O)
Закрытый список: 0 / O (источник / через ничто), 2 / A (через O)
Таким образом, мы сравнили A с B против O с B.