В своё время долго и упорно разбирал различные алгоритмы поиска путей для различных задач. Сейчас, во время отпуска, решил сделать доброе дело и поделиться накопленными знаниями.
В видео постарался разжевать всё так, чтобы стало понятно даже юзеру с нулевым знанием темы и программирования.
Надеюсь, что это будет кому то полезным.
Было бы интересно послушать про алгоритм такого плана, или хотя бы узнать его название, если подобное существует)
Берём точку А и точку Б, пытаемся наступить на клетку, которая по прямой в сторону точки Б, если мы не можем пройти вперёд, то считаем клетку влево, если не можем пройти по ней, то считаем клетку вправо от той на которую наступили и так по очереди, прямо, лево, право и пока не достигнем цели.
Вижу сразу несколько слабых сторон такого метода.
- Как "прыгать на клетку влево/вправо" Если точки А и Б находится не на 1 линии сетки, а под углом, например в 30градусов? По диагонали, или двигаться только ортодоксально?
- Как алгоритм решит задачу на скриншете? Убежит вниз и начнёт тыкаться в стенки застряв в нижнем правом углу?
- Даже если методом перебора доберётся до цели, то нашли ли мы при этом кратчайший из возможных путей? Мы же нигде не сохраняем информацию о длине пути и оптимальном маршруте, а просто перебираем клетки пытаясь достигнуть финиша.
Хотя в теории это применимо для просторных карт без сложных преград. Если нужно обходить врагов, или выпуклые препятствия в пару клеток.
- Как "прыгать на клетку влево/вправо" Если точки А и Б находится не на 1 линии сетки, а под углом, например в 30градусов? По диагонали, или двигаться только ортодоксально?
По диагонали тоже можно
- Как алгоритм решит задачу на скриншете? Убежит вниз и начнёт тыкаться в стенки застряв в нижнем правом углу?
Сначала убежит вниз, потом упрётся в заданный лимит по отдалению точки и начнёт просчет вверх
- Даже если методом перебора доберётся до цели, то нашли ли мы при этом кратчайший из возможных путей? Мы же нигде не сохраняем информацию о длине пути и оптимальном маршруте, а просто перебираем клетки пытаясь достигнуть финиша.
Да, в данном случае получается не по кротчайшему, а по первому найденному
Ну да, теперь я и сам вижу унылость метода)
Лига Разработчиков Видеоигр
6.6K постов22.1K подписчиков
Правила сообщества
ОБЩИЕ ПРАВИЛА:
- Уважайте чужой труд и используйте конструктивную критику
- Не занимайтесь саморекламой, пишите качественные и интересные посты
- Никакой политики
СТОИТ ПУБЛИКОВАТЬ:
- Посты о Вашей игре с историей её разработки и описанием полученного опыта
- Обучающие материалы, туториалы
- Интервью с опытными разработчиками
- Анонсы бесплатных мероприятий для разработчиков и истории их посещения;
- Ваши работы, если Вы художник/композитор и хотите поделиться ими на безвозмездной основе
НЕ СТОИТ ПУБЛИКОВАТЬ:
- Посты, содержащие только вопрос или просьбу помочь
- Посты, содержащие только идею игры
- Посты, единственная цель которых - набор команды для разработки игры
- Посты, не относящиеся к тематике сообщества
Подобные посты по решению администрации могут быть перемещены из сообщества в общую ленту.
ЗАПРЕЩЕНО:
- Публиковать бессодержательные посты с рекламой Вашего проекта (см. следующий пункт), а также все прочие посты, содержащие рекламу/рекламные интеграции
- Выдавать чужой труд за свой
Подобные посты будут перемещены из сообщества в общую ленту, а их авторы по решению администрации могут быть внесены в игнор-лист сообщества.
О РАЗМЕЩЕНИИ ССЫЛОК:
Ссылка на сторонний ресурс, связанный с игрой, допускается только при следующих условиях:
- Пост должен быть содержательным и интересным для пользователей, нести пользу для сообщества
- Ссылка должна размещаться непосредственно в начале или конце поста и только один раз
- Cсылка размещается в формате: "Страница игры в Steam: URL"