Комментарии 5
Можно сказать, что у вас тут упрощенный вариант задачи 16 в этом году на AOC: https://adventofcode.com/2024/day/16
Только там еще требуется учитывать стоимость смены направления, что гораздо ближе к реальности в случае нахождения именно более быстрого пути, а не короткого.
Кстати, почему решаете задачу не рекурсией?
Да, я старался сделать акцент на то, что мы тут пытаемся найти именно кратчайший путь, и совершенно верно, он не всегда будет самым быстырм с точки зрения прохождения роботом
По решению задачи -- я верю она имеет очень большое множество решений, ведь лабиринт это по факту граф, поэтому мы можем применять все соответсвующие алгоритмы по обходу и поиску пути, в этой статье я очень старался применить самый простой на мой взгляд подход без введения лишних понятий. Мотивация следующая: в этих соревованиях сейчас активно учавствтуют школьники и хочется чтобы этот материал был доступен и им, поэтому тут я бы хотел дать некую "основу", насколько это возможно
Очень упрощено. Физика робота сильно влияет на алгоритм - к примеру, инерция и возможность движения по диагонали совсем не учитывается.
это уже относится к реализации движения робота, на мой взгялд это самая сложная часть этого всего. Однако сам алгоритм обхода лабиринта никак не зависит от того как мы реализуем движения робота, всё равно нужно будет научить робота "считать" сколько он проехал, чтобы понимать когда он из одной ячейки перешёл в другую.
Про диагонали -- это отдельный процесс, который не относится к исследованию лабиринта, чтобы корректно проезжать диагонали у нас уже должна быть построена карта, и данный материал именно о построении карты, а не о быстрых и оптимальных проездах
Про это я и пишу - обход дейкстрой (flood fill это немного про другое) сделать несложно, а вот весь интерес в разработке алгоритма, учитывающий физику процесса движения. Помню фурор, когда впервые отошли от тупого прохождения лабиринта по кратчайшему пути к более длинному маршруту, но учитывающими ограничения робота.
Готовимся к Micromouse: как роботу найти короткий путь к цели