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