#c #algorithm #shortest-path #path-finding #a-star
#c #алгоритм #кратчайший путь #поиск пути #a-star
Вопрос:
Ищу некоторые разъяснения, поскольку я, похоже, не могу получить ответ. При написании алгоритма astar для сеток мне было интересно, предназначен ли он для работы с прямоугольниками любого размера или просто идеально квадратными сетками? Если существует конкретный метод обработки эвристики для прямоугольников, что это такое?
Если людям нужно знать, я пишу это на C для использования в UE4.
Спасибо всем!
Комментарии:
1. Вы должны настроить стоимость и эвристику для вашего узла (прямоугольника).
2. A * должен работать с любым типом макета, если вы используете точную эвристику
3. Спасибо всем за ваши ответы! Это дает мне некоторую ясность в проблеме! Спасибо
Ответ №1:
Нет, A * вообще не нуждается в сетке. Вы можете использовать любое размещение узлов, и пока ваша эвристика допустима, A * должен работать.
На самом деле, если вы можете гарантировать, что ваша эвристика допустима (т. Е. Гарантируется, Что она никогда не переоценивает расстояние), вашим узлам вообще не нужна позиция. Конечно, многие реальные приложения имеют узлы с определенными местоположениями, и евклидово расстояние является удобной допустимой эвристикой.
Единственное, что вам нужно сделать, чтобы заставить работать прямоугольную сетку, — убедиться, что ваши показатели верны. То есть: ваши межузловые расстояния и вычисление евклидова расстояния должны правильно отражать горизонтальное и вертикальное расстояние вашей сетки.