В своё время долго и упорно разбирал различные алгоритмы поиска путей для различных задач. Сейчас, во время отпуска, решил сделать доброе дело и поделиться накопленными знаниями.
В видео постарался разжевать всё так, чтобы стало понятно даже юзеру с нулевым знанием темы и программирования.
Надеюсь, что это будет кому то полезным.
В данном случае движение по диагонали = движение по гипотенузе равностороннего треугольника. По теореме Пифагора гипотенуза равностороннего треугольника в 1,414 раза длиннее его стороны. Потому движение по диагонали я и считаю в 1.4 раза дороже ортогонального движения.
По той же причине, почему использую квадратную, а не шестиугольную или какую-либо ещё сетку. Это наиболее наглядный и понятный метод на мой взгляд.
Целью было показать принцип работы алгоритма, а не создать самый накрученный и продвинутый вариант.
Здесь у вас фундаментальная ошибка. Если допускаются передвижения по диагонали, то манхэттенское расстояние не применимо. Эвристическая функция должна быть допустимой (admissible), то есть никогда не переоценивать конечную стоимость пути. Иначе алгоритм будет не оптимален
Откуда взяться переоценке если эвристический шаг равен минимальной цене шага клетки?
С поставленной целью алгоритм справляется (находит кратчайший путь).
А про оптимальность алгоритма в видео не было ни слова. Оптимизировать всегда есть куда... Оптимизация зависит от размеров сетки, от количества препятствий, от наличия движущихся препятствий и от того упираемся мы в оперативную память или процессорные мощности.
Тут же учебная модель была сделана для пояснения основ.
1. Между двумя соседними диагонально расположенными клетками кратчайший путь по диагонали 1.4, а манхеттенское расстояние 2. Вообще изначально неверно, что вы разные расстояния используете для функций g(x) и h(x). Получается, что вы складываете километры с дюймами.
2. А* алгоритм по своему определению оптимален, иначе это другой алгоритм. Оптимальный значит что при любых условиях алгоритм находит кратчайший возможный путь.
3. Я не придираюсь, просто указываю на ошибки. Пожалуйста.
Спасибо за отзыв и попытку указать на ошибки. Просто я не согласен с тем, что алгоритм будет выдавать не оптимальный путь при каких либо условиях. Он тестировался как на сложных лабиринтах, так и на крупных сетках 10000Х10000 и ни разу не давал сбоя всегда находя кратчайший путь.
Эвристический шаг равен минимальной стоимости пути именно для того, чтобы всегда находить кратчайший возможный путь.
Я повторюсь, что оптимизировать эвристическое приближение можно (именно в плане скорости работы алгоритма, а не в плане точности нахождения конечного пути), но оно никогда не будет идеальным. Особенно в случае, когда различные клетки имеют разную стоимость прохождения, как в последних 3 примерах, с дорогой, лесом и водой.
Если же вы знаете способ как идеально оптимизировать эвристическое приближение учитывая, что на карте находятся клетки с разной стоимостью прохождения, то я признаю, что вы правы, а я допустил фундаментальную ошибку.
Теоретически алгоритм не может быть оптимальным, если эвристическая функция не admissible (overestimated). С сугубо академической точки зрения правильнее было бы использовать для обоих функций g(x) и h(x) расстояние Чебышева. С практической точки зрения возможно вы правы, если вас алгоритм устраивает, используйте его. Но это не чистый A*, скорее всего на очень сложных картах он выродится в BFS алгоритм
Лига Разработчиков Видеоигр
6.6K постов22.1K подписчиков
Правила сообщества
ОБЩИЕ ПРАВИЛА:
- Уважайте чужой труд и используйте конструктивную критику
- Не занимайтесь саморекламой, пишите качественные и интересные посты
- Никакой политики
СТОИТ ПУБЛИКОВАТЬ:
- Посты о Вашей игре с историей её разработки и описанием полученного опыта
- Обучающие материалы, туториалы
- Интервью с опытными разработчиками
- Анонсы бесплатных мероприятий для разработчиков и истории их посещения;
- Ваши работы, если Вы художник/композитор и хотите поделиться ими на безвозмездной основе
НЕ СТОИТ ПУБЛИКОВАТЬ:
- Посты, содержащие только вопрос или просьбу помочь
- Посты, содержащие только идею игры
- Посты, единственная цель которых - набор команды для разработки игры
- Посты, не относящиеся к тематике сообщества
Подобные посты по решению администрации могут быть перемещены из сообщества в общую ленту.
ЗАПРЕЩЕНО:
- Публиковать бессодержательные посты с рекламой Вашего проекта (см. следующий пункт), а также все прочие посты, содержащие рекламу/рекламные интеграции
- Выдавать чужой труд за свой
Подобные посты будут перемещены из сообщества в общую ленту, а их авторы по решению администрации могут быть внесены в игнор-лист сообщества.
О РАЗМЕЩЕНИИ ССЫЛОК:
Ссылка на сторонний ресурс, связанный с игрой, допускается только при следующих условиях:
- Пост должен быть содержательным и интересным для пользователей, нести пользу для сообщества
- Ссылка должна размещаться непосредственно в начале или конце поста и только один раз
- Cсылка размещается в формате: "Страница игры в Steam: URL"