Программируем… выход из лабиринта

Программируем… выход из лабиринта

Что это?

Перед вами симулятор лабиринтов на базе Excel. Вы можете создавать лабиринты любой сложности и оттачивать на них свои алгоритмы поиска выхода. Я сделал его в качестве развлечения. Получилось довольно забавно.

Правила

Стены легко рисуются при помощи единичек. Остальное сделает условное форматирование.

Точку старта вы определяете сами через активную ячейку.

Кнопка “Старт” запускает ваш алгоритм поиска выхода

Те ячейки, на которых вы побывали в процессе поиска, помечаются зеленым цветом.

Кнопка “Очистка” подготавливает лабиринт к новому забегу.

Если текущая позиция игрока и выход из лабиринта находятся на одной линии, между ними нет преград, а игрок исследует это направление на возможность сделать туда ход, то в этом случае фиксируется нахождение выхода из лабиринта. Вообще же в коде определена константа ExitCondition =100. Если стандартная подпрограмма Can_I_Move(Direction) определяет, что в направлении Direction между текущей позицией игрока и ближайшей преградой (любая константа на листе или его граница) более 100 ячеек, то фиксируется факт выхода за пределы лабиринта, а алгоритм останавливается.

В распоряжении игрока, который хочет написать алгоритм поиска из лабиринта следующие инструменты:

Процедура MyFindExit , которую вы можете использовать в качестве контейнера для своего алгоритма.

Константы направлений движения (direction): dRight = 1, dDown = 2, dLeft = 3 и dUp = 4

Функция Can_I_Move(Direction) , которая возвращает ноль, если в направлении Direction находтся стена, либо количество ходов, которое вы можете сделать до ближайшей стены, но не более границы видимости (константа VisibilityLimit = 4)

Функция Was_I_Here(Direction) , которая возвращает -1 , если вы не ходили раньше на смежную клетку в указанном направлении, 1 – если вы там уже были (сколько раз вы там были узнать возможности нет), 0 – если в этом направлении есть препятствие.

Разрешается создать для нужд алгоритма 2-4 целочисленных переменных и 1-2 логических переменных.

Количество ходов в алгоритме желательно подсчитывать. Алгоритм прекращает работу, если сделано ходов больше, чем в константе IterationsLimit , а выход ещё не найден.

Вы можете прервать работу алгоритма через Ctrl + Break

Пауза между ходами регулируется константой WaitAfterMove , которая по умолчанию равна 50 милисек.

Чего хотелось бы?

Хотелось бы взглянуть на ваши универсальные алгоритмы поиска выхода из лабиринтов. Любых лабиринтов, в которых есть выход. Я написал свой алгоритм, но он получился довольно громоздким. Я оставил его в файле, но рекомендую попытаться написать свой алгоритм. Я знаю, что у вас получится гораздо лучше! Тем более, что наблюдать за процессом поиска выхода довольно занятно. Жду ваших замечательных идей!

Программируем… выход из лабиринта

Наверное, некоторые из вас смотрели фильм «Бегущий в лабиринте», где группа подростков живет в ущелье в центре лабиринта, населенного чудовищами? Они находят выход, умело используя подсказки. Но существуют алгоритмы и даже программы, способные на поиск выхода из лабиринта. О них мы и поговорим.

Как пройти лабиринт?

Зачем нам какой-то лабиринт лабиринт, спросит читатель? И как мы можем его найти с помощью программы? Ведь она ходов-выходов не видит? И, потом, есть ведь правило «левой» и «правой» руки, которое, наверное, дает возможность отыскать выход в любом лабиринте.

Действительно, программа выхода не видит. А вот правило «левой или правой» руки запросто может не сработать, если лабиринт имеет независимые элементы, несвязанные непрерывными стенами с остальной частью системы ходов. Тогда остается лишь… общий для всего лабиринта пол, который никак не поможет нам определить верное направление.

Кроме того, существуют крайне запутанные лабиринты чрезвычайной сложности, проследить которые непросто, а для нахождения пути через них может потребоваться длительное время. Есть извилистые тропы со множеством ответвлений, которые можно преодолеть по кратчайшему пути, сэкономив припасы, силы или горючее для автомобиля (смотря что вам подскажет воображение). И они же окажутся очень длинными, если двигаться по случайному пути.

Лабиринт может быть и не лабиринтом, а картой метро или схемой дорог, которую нужно проскочить с наименьшими затратами либо серпантином горных ущелий, среди крутых склонов которых надо выбрать наиболее доступные. Словом, вариантов много. Так как же нам поступить?

Вездесущая матрица

Мы, конечно, люди современные и понимаем, что для составления маршрута нам необходима карта местности, хотя бы приблизительная. А если её нет — придется её составить. Включим воображение и представим, что мы у порога лабиринта, а в руке у нас пульт от квадрокоптера с видеокамерой. Раз, два, три — дрон уже в воздухе и снимает наш лабиринт сверху. Возможны варианты. Если это пещера — мы отправляем туда самодвижущийся механизм на гусеницах, если подводный «Аравийский тоннель», как в книге про капитана Немо (там предполагалось, что на месте нынешнего Суэцкого канала существует сквозная пещера, соединяющая Средиземное и Красное моря) — то подлодку-дрон. Их нестрашно потерять и карту своего пути они передадут нам с помощью современных технических средств.

Но путь — это только полдела. В современной реальности важнее всего иметь под рукой самый короткий, удобный и дешевый путь, чтобы ускорить перевозку и обойти конкурентов. А составление кратчайшего пути — это уже задача, вполне решаемая для компьютера.

Весь пройденный одной или другой (в зависимости от условий задания) машиной маршрут представляем себе в виде двумерной (в некоторых, особо сложных случаях — трехмерной матрицы. Помните фантастический фильм «Матрица»? Там фигурировала плоская конструкция из множества сот, заполненных человеческими телами. Наша матрица будет содержать ячейки с данными, расположенные на одинаковом удалении друг от друга — по примеру обычной географической карты в Google или Yandex.

В простейшем варианте матрица будет горизонтальным полем. Представьте себе шахматную доску. Каждый квадрат получит аналогичные шахматным координаты. Допустим, третья ячейка сверху будет четвертой по счету в своем ряду. Если это ущелье, то значением самой ячейки может быть высота или крутизна склона. Если вокруг дороги отвесные стены, то ячейка либо проходима либо нет.

Конечно, если наш лабиринт имеет несколько уровней, да ещё и с пересечением высот, потребуется трехмерная матрица, но её мы рассматривать не будем. Если вы заметили, даже в современных играх уровни выполнены независимыми, то есть, их тоже можно представить как двумерные матрицы с дополнительными параметрами.

Проходим лабиринт «волной»

К сожалению, компьютер сам по себе путей не увидит, даже если у него будет под рукой цифровая карта. Ему нужно предложить алгоритм, который обеспечит эффективный поиск пути в матрице, заполненной условными цифровыми обозначениями. Итак, используем для прохождения лабиринта самый простой алгоритм — волновой. И двигаться будем только вправо, влево, вверх и вниз (можно ходить ещё и по диагонали но мы пока этот рассматривать не будем).

Движение «волны» напоминает расходящиеся круги на воде или обвал, когда вниз с горы падает множество камешков. Вокруг стартовой точки, если она расположена не на краю матрицы-карты, всегда находятся ещё четыре точки. Нам необходимо проверить, свободны ли они для прохождения? Инструкция компьютеру будет звучать так: «пройди прямо и проверь, свободна ли клетка впереди? Если да, то перейди туда и измени её единичкой. Если нет, то пройди назад и проверь, свободна ли клетка позади? Если да — перейди туда и пометь её единичкой. Если нет, проверь, свободна ли клетка справа? Если да, то перейди туда и пометь её единичкой. Если нет, проверь клетку слева.

Если вокруг точки или, в данном случае, старта нашего путешествия есть свободные клетки, они будут помечены «единичкой». В следующем шаге мы должны будем пометить «двойкой» все свободные клетки, вокруг клеток с «единичкой», разумеется, кроме уже помеченных. Клетки с «двойкой» обретут собственную задачу — пометят свободное пространство «тройкой» и т.д. Таким образом, волна «разбегается» от центра, огибая препятствия и мгновенно достигает финиша — выхода из лабиринта.

Ну а как же нам найти кратчайший путь? Очень просто. Нужно на каждом шаге, начав отсчет от финиша, искать клетки, помеченные все меньшим и меньшим числом. От «девятки» ищем «восьмерку», от неё — «семерку» и т.д. В 95% случаев таким образом находится кратчайший путь. Но, к сожалению, не всегда. Если набор препятствий имеет сложную форму, то «волна» может «зациклиться». Поэтому, программе нужно установить какой-то эмпирический предел для количества итераций. Чтобы она могла вам сообщить, к примеру: «всё, хозяин, пути нет».

«Реализация волны»

На программном уровне волновой алгоритм строится достаточно просто. Лабиринт мы, или сканируем или, соответствующим образом обрабатываем, получая матрицу, значения ячеек которой отражают проходимость или непроходимость её узлов. Затем эту матрицу мы вносим в программу или подаем на вход в виде файла.

Далее мы создаем три цикла (обязательно три), которые обходят всю матрицу, генерируя волну. Внешний цикл должен иметь границу, не меньшую чем размер длинной стороны матрицы. Внутренние циклы строятся как обычно: один — по количеству строк, а второй — по числу столбцов. В принципе, можно и наоборот.

Затем нам понадобится несколько условий. Точнее, много условий, каждое из которых программа должна проверить. Необходимо уточнить, что представляет из себя каждая из клеток, расположенных вокруг точки старта — это тупик или это свободная клетка? А может быть это клетка — финишная. А может быть стартовая? Для простоты «волной» мы будем помечать только свободные клетки. Конечно, необходимо проверять, не является ли клетка финишной. Ну и, конечно, стоит завершить работу всех трех циклов при прохождении финиша.

Есть ещё один немаловажный момент — для того, чтобы каждая волна была помечена числами по возрастанию, нам потребуется коэффициент, который надо увеличивать перед завершением внешнего цикла, который и является «генератором» волны. Этот коэффициент мы назовем Ni. Определителем максимального количества итераций будет коэфициент Nk. Матрицу мы смделали квадратной и количество ячеек в ней обозначим переменной n. Массив наш назовем lab — от слова «лабиринт». Переменными, работающими во внутренних циклах будут обычные i, j, во внешнем — l. Переменные z и k получат значения точки выхода из лабиринта, когда цикл закончится.

Завершим работу циклов с помощью оператора break и метки label. Как мы знаем, break останавливает только свой цикл. Поэтому метку вынесем за внешний.

Для прокладки пути у нас есть массив, аналогичный первому. Для удобства он заполнен однородными цифрами. Соответственно, после окончания той части программы, которая прокладывает волну, сработает вторая — помечающая кратчайший маршрут. Циклов нам здесь понадобится всего два, так как вокруг любой точки, в нашем случае, будет только одна точка, ближайшая ко входу и все проверять уже не потребуется. Как только мы найдем эту точку, мы присвоим её координаты нашим переменным z и k, тем самым, продвинувшись к выходу на один шаг. Саму клетку мы будем обозначать коэффициентом Ni, снижая его на одну единицу за каждую итерацию внешнего цикла.

Очень важное добавление: нам потребуется начинать просмотр матрицы не с первого элемента, а со второго. И заканчивать мы будем предпоследним элементом последней строки. Иначе первые числа первой строки и столбца и последняя цифра массива обязательно сделают запрос к несуществующим точкам по адресам 0, 0-1 и 0-1, 0. Так мы выйдем за границы цикла и будет ошибка.

Вот как выглядит эта программка на языке Java в максимально упрощенном для восприятия виде, без функций и методов. Добавлю, что для удобства и понимания я свел её в один листинг, а вывод маршрута сделал в отдельном массиве, заполненном однородными числами.

Код работает на любом компиляторе Java. Его можно скопировать и запустить. Можно исследовать волновой алгоритм на предмет прохождения различных препятствий сложной формы. При необходимости его можно переписать на языке C, использовать в лабораторной работе, создать соответствующий метод или функцию или даже написать небольшую игру. Код снабжен краткими пояснениями на английском языке.

Программа для прохождения лабиринта Ev3

На данном уроке мы рассмотрим, как пользоваться собственными блоками Ev3 при программировании Ev3.

Напишем программу для Ev3 для прохождения лабиринта. Когда в программе много раз повторяется одна и также последовательность команд, то удобно использовать собственные блоки. Это делает программу очень наглядной и удобной для изменения. Каждый блок отвечает за свой смысловой набор действий,, который можно обособить и выделить. А далее из этих собственных блоков конструируется программа, согласно логике задания. Рассмотрим, как написать программу для Ev3 для прохождения лабиринта с помощью собственных блоков.Напишем блокидвижение вперед до стены.

Поворот направо на Ev3

Поворот налево на Ev3

Выделяя эти части программы и выбирая в меню Инструменты раздел Конструктор моего блока, создадим три блока: vpered, parvo, levo. Подробно как создавать свои блоки в Ev3.Составим программу из собственных блоков Ev3 для прохождения такого лабиринта.Робот должен двигаться со старта вперед до левой стенки, потом повернуться направо и двигаться до стенки, потом повернуться направо и двигаться до стенки, налево и до стенки, и налево и до стенки до финиша.

Реализуем этот лагоритм с помощью собственных блоков Ev3 , которые мы создали.

Как видим программа достаточно лаконичная. Представьте, какая была бы большая программа без использования собственных блоков.Аналогично мы можем составить программу для прохождения лабиринта любой сложности.

Вернуться к содержанию Перейти к следующей теме Математика в ev3

Полезно почитать по теме прохождение лабиринта ev3
Собственные блоки ev3
Циклические алгоритмы ev3