3D робот в лабиринте - как играть
По условиям данной игры, вы должны бродить роботом по лабиринту в поисках двери выхода и ключа от ее замка. В управлении игра проста, ведь используются всего 5 клавиш. Двигайтесь стрелками клавиатуры и все обязательно получится. В игре несколько интересных уровней, каждый из которых отличается своей сложностью и непредсказуемостью.
Какие все-таки существуют лабиринты
Человечество с самых истоков истории проектировало и создавало лабиринты. С тех времен начато строительство громадных тюрем, в которых создано много разных коридоров, не дающих преступникам убежать. Чтобы с большим достоинством проходить игры в режиме «лабиринты» на нашем официальном сайте, вам не обойтись без таких нужных навыков, как хорошая ориентация в пространстве, зрительная память, интуиция и острый ум.
Сделайте все возможное, чтобы за меньшее время пройти лабиринт до конца и с большим достоинством закончить невыполнимую миссию!
Лабиринт Минотавра
Мифы Древней Греции и стародавние легенды повествуют нам о старинном лабиринте, расположенном на острове Крит. Но история знает его под другим названием - Лабиринт Минотавра. Ужасное человекоподобное чудовище, имеющее голову быка, многие десятки лет берегло неприступное подземелье. Оно за охрану хотело постоянно человеческих жертв, и люди регулярно платили эту дань. Но пришло время, когда воин Тесей без страха в глазах кинулся на это чудовище. Ему удалось не только одолеть чудовище Минотавра, но и найти выход из лабиринта, и в этом ему помог клубок ниток, что накануне ему вручила любимая Ариадна.
Чтобы проходить лабиринт в играх, вам понадобится усидчивость, большое терпение, смелость Тесея и благоразумие Ариадны. Имея все эти качества, вы сможете с легкостью найти выход из любого лабиринта в целости и сохранности.
Классическая категория
Это именно тот лабиринт, который нам известен с самого детства и тот, что много лет назад печатали в газетах с кроссвордами. Здесь всего-навсего одна цель - дойти до конца лабиринта, при этом не надо собирать разные бонусы или переводить свое внимание на других персонажей.
Страшный лабиринт
В этом режиме вас будут пугать монстры, кладбища, страшные подземелья. Данный лабиринт в конце режима удивит вас наличием конечной страшилки.
Математический лабиринт
Это легкий лабиринт, который заинтересует тех, кому нравятся цифры. Здесь вам надо будет проводить математические операции. Вы вспомните школьные годы и узнаете, насколько хорошо обладаете математическими способностями.
Детский режим
В детском лабиринте все немножко по-другому. Здесь предусмотрены легкие задания, яркая графика, а вместо чудовищ - мультипликационные персонажи. Все дети будут от нее без ума.
В статье показано создание робота, которые ездит по линиям и может проходить лабиринты, после изучения лабиринта он может пройти его кратчайшим путём. Автор долго создавал этот проект, удача настигла его с третьего раза.
Демонстрация работы машины:
Материалы и инструменты:
- Arduino RBBB
- Микродвигатели 2 шт
- Кронштейны для двигателей 2 шт
- Колёса 2 шт
- Шариковое колесо
- Датчик отражения аналоговый
- Гайки с болтами по 2 шт
- Драйвер двигателя
- Держатель для батарей 4 шт ААА
- Батарейки (аккумуляторы) ААА 4 шт
- Корпус
- Гайки, болты, шайбы
- Соединительные провода
- Припой
- Плоскогубцы
- Паяльник
- Отвёртка
Шаг первый. Теория.
Автору нужен был робот , который сам будет находить выход из лабиринта, после чего сможет оптимизировать обратный путь. При создании машины для лабиринтов руководствовались методом левой руки. Чтоб было понятнее следует представить что вы оказались в лабиринте и всегда держите левую руку на стене. После прохождения определённого пути это поможет выйти вам из лабиринта если он не замкнут. Робот может работать только с незамкнутыми лабиринтами.
Принципы работы способа левой руки довольно прост:
- Если есть возможность повернуть налево, поверните налево.
- Если есть возможность двигаться прямо, двигайтесь прямо.
- Если есть возможность повернуть направо, поверните направо.
- Если вы зашли в тупик, развернитесь на 180 градусов.
Также роботу нужно принимать решения на перекрёстке, если же на повороте он не свернёт, тогда поедет прямо. Для построения лучшего маршрута обратного пути, каждое решение записывается в память.
L = левый поворот
R= правый поворот
S= пропустить поворот
B= развернутся на 180 градусов
Ниже показан этот метод в действии на примере простого лабиринта. Робот прошёл дистанцию путём команд LBLLBSR.
Путь вышел довольно большой, его требуется превратить в оптимальный SRR. Для этого определяется где робот повернул не туда. Везде где использована команда «В» путь будет неверным, так как робот был в тупике, поэтому «В» следует заменить на что-то другое. Первым неверным движением было LBL, робот свернул и развернулся, в то время когда требовалось просто следовать прямо LBL = S. Таким образом, выстраивается идеальный путь LBL = S, LBS = R. На основе таких замен робот выстраивает для себя идеально короткий путь.
Шаг второй. Шасси робота.
Основой для шасси робота стал акрил толщиной 0.8 мм, резка производилась лазером согласно чертежу. В архиве под статьёй будет файл чертежа из AutoCAD. Использовать такой материал было необязательно, но автор взял то что было в наличии.
В нижней части сделаны отверстия для крепления двигателей, платы, колёс и датчиков. Верхняя часть имеет большое отверстие для проводов.
Шаг третий. Установка колёс.
Оба двигателя автор прикрепил с помощью болтов. Далее, на их ось просто одел колёса, совместив вал с отверстием колеса.
Шаг четвёртый. Arduino.
На этом этапе автор сначала следовал инструкциям по сборке Arduino RBBB. Далее, он отрезал часть платы для уменьшения её размеров. Ножницами по металлу был отрезан разъём питания и стабилизатор. После чего, к левой стороне платы на контакты от 5В до А0 припаяли 9-контактный разъем, для подключения к нему датчика. К правой стороне платы на контакты от D5 до D8 был припаян 4-контактный разъём, к нему подключат контроллер двигателя. Для подачи питания 2-контактный разъем припаяли к 5В и GND.
Шаг пятый. Контроллер двигателя.
Автор сам разработал печатную плату для этого шага, схема в формате Eagle прикреплена в архиве под статьёй. Первый двигатель подключили к контактам M1-A и M1-B, второй к M2 и M2-B. Первый вход первого двигателя In 1A подключили к 7 выводу Arduino. In 1B был подключён к выводу 6 Arduino. К первому входу второго двигателя In 2A подключён к 5 выводу Arduino. Контакт In 2B подключается к 8 выводу Arduino. Питание и земля подключили к питанию и земле Arduino.
Шаг шестой. Датчики.
Данный элемент продается в виде платы из датчиков, изначально их восемь штук, два крайних были удалены автором. На плату припаяли разъем из 9 контактов, к ним подключат провод ведущий к Arduino. Датчик обнаруживает белый и чёрный участок лабиринта с помощью отражения от поверхности.
Шаг седьмой. Верхняя часть.
Шасси с верхней частью робота соединили болтами и стойками. Аккумулятор был закреплён на верхней части липучкой. Провода от него проложили через подготовленное отверстие. При креплении автор решил не использовать винты, а оставить аккумулятор на липучке, чтоб можно было проще заменять батарейки. С помощью выключателя на корпусе для батарей была произведена проверка работоспособности.
Шаг девятый. Питание.
К Arduino просто припаяли провода от аккумулятора. Включение и выключение робота будет происходить выключателем на аккумуляторе, поэтому было решено использовать пайку. На этом сборка робота завершена.
Шаг десятый. Программная часть.
Программа имеет несколько функций отвечающих за алгоритм работы. Функция «левой руки» получает показания от датчиков и управляет роботом по этим правилам. Функция поворотов включается до того как робот заметит чёрную линию, заметив, её он едет прямо. Также встроена функция оптимизации пути. Программу можно скачать под статьёй в архиве.
Видео робота:
Для средней категории World Robot Olympiad 2011, но так и не было рассмотрено, как написать самую простую программу. Настало время наверстать этот момент. Итак, сперва следует напомнить, какие же основные блоки определяют поведение робота в лабиринте:
- Движение прямо с опросом датчиков, обнаруживающих проход справа, и датчиков, обнаруживающих столкновение с преградой
- Поворот направо, в случае обнаружения прохода
- Поворот налево, в случае обнаружения препятствия
Здесь следует ненадолго остановиться и опять вернуться к рассмотрению конструкции робота.
Первый случай - поворот направо. Подразумевается, что он происходит после срабатывания датчика смотрящего в сторону.
После такой остановки, робот может выполнить два возможных поворота: либо поворот одним колесом, либо поворот вокруг своей оси.
 |  |
Видно, что после такого поворота, дальнейшее движение робота прямо приведет к столкновению со стеной. Эту проблему можно решить двумя способами:
Для того, чтобы закончить поворот до конца, роботу будет необходимо сдвинуться вперед, так чтобы датчик оказался вновь направлен на то место, где должна быть стена. Не имеет большого смысла делать этот действие с условием выхода "пока не увижу стену", потому что в общем случае, стены может и не быть - перегородка, отделяющая две секции лабиринта, может оказаться слишком тонкой для определения датчиком. Остановка должна произойти примерно на таком же расстоянии, на котором бы робот сам остановился, обнаружив проход.
Теперь следует рассмотреть с таких же позиций разворот налево.
Очевидно, что для выполнения поворота роботу нужно достаточно места. И тут опять несколько способов обеспечения этого:
Из схемы становиться понятно, почему при таком способе расположения колес надо стараться минимизировать проекцию робота на пол: здесь следует рассматривать вертикальное расположение и блока и колес. Иначе после разворота датчик, отслеживающий проход будет располагаться слишком далеко от стены, что может приводить к ложным срабатываниям - он будет думать, что увидел проход.
Идеальной будет комбинация обеих вариантов - это позволит роботу двигаться достаточно близко к стене и иметь возможность заранее выполнять повороты в случае обнаружения препятствия.
Что ж, с конструкцией более-менее стало понятно, с тем как выполнять развороты тоже. В идеале, после таких экспериментов должны остаться два готовых набора блоков, которые можно будет впоследствии вставлять в основную программу. Имеет смысл занести эти куски программы в собственные блоки.
Структура основной программы однозначно диктуется правилом правой руки:
Алгоритм начинает свое выполнение с движение вперед. Как уже говорилось, в общем случае, это может быть обычное движение.
Затем, друг за другом идет проверка на обнаружение прохода в правой стене, либо на обнаружение столкновения с препятствием. И, в зависимости от того, какая проверка сработала, вызываются блоки поворотов. Если никакая проверка не сработала в этот момент времени, то в следующий момент времени нужно сделать еще одну проверку, а потом еще и еще.
Очевидно, что после выполнения поворотов нужно опять продолжить движение вперед, и опять перейти к проверкам на проход или препятствие.
Такой алгоритм обладает недостатком: его сложно реализовывать на языке NXT-G (да и на других языках тоже), поскольку он имеет две точки возврата после выполнения одних и тех же повторяющихся действий. К тому же, единожды включив двигатели на движение вперед после старта или после поворотов, этот алгоритм не подразумевает попытку подправить свое движение, если возникнет необходимость для . Логично было бы все время выполнять периодическую корректировку или просто добиться упрощения алгоритма, принимая во внимание, что команды "включить мотор" не блокируют дальнейшую работу алгоритма, а передают управление следующим инструкциям.
В итоге, программа на языке NXT-G будет похожа на подобную конструкцию:
Как уже говорилось, блок движение вперед может быть замещено специальным блоком, который бы обеспечивал перемещение вдоль стены. Хотя во многих случаях эта проблема может быть решена чисто механически: у робота с нужно стороны устанавливаются ролики или направляющие, которые не позволяют ему слишком приблизиться к стене.
Примеры такого решения можно подсмотреть в роликах ниже:
При этом, чтобы не отъезжать далеко от стены, нужно двигаться чуть-чуть с заворотом (распределение нагрузки между моторами) в сторону стены.
Для того, чтобы понять, как запрограммировать робота, для перемещения его по лабиринту, рекомендуется поставить себя на место робота и думать, а как бы вы начали действовать...
Итак, вы оказались в лабиринте...
Нет. На самом деле, если вы робот, собранный на базе Lego Mindstorms, как только вы попали в лабиринт, он будет для вас выглядеть вот так.
Да. Вы ничего не видите. У вас нет глаз. У вас нет стереозрения. Для вас расположение стен лабиринта и уж тем более наличие ответвлений и проходов – загадка. Единственное, что вы, скорее всего, знаете наверняка, что прямо под вами твердая поверхность.
Что вы будете делать в таком случае? Идти вперед выставив руки перед собой? Не плохая идея. А потом что? И вообще, что значит "вперед"? А если это очень большой зал? В таком случае, есть вероятность, что, поскольку вы не видите ориентира, на который могли бы равняться, то вы будете шагать чуть-чуть в сторону. В итоге, прошагав окружность вы вернетесь на тоже место с какого начали, но так и не узнаете, что вернулись в него – так вы будете ходить очень долго.
Наиболее разумной идеей было бы попытаться найти опору в виде стены для какой-либо руки. Допустим, правой. Как только стена обнаружена, вы в вправе двигаться вперед или назад. Стена в таком случае будет являться вашим путеводителем, опорой в этом "темном" мире.
У робота такой рукой могут быть сенсоры расстояния, касания или даже освещенности. Если робот использует сенсор касания, то во время движения в момент, когда стена потеряется, он выдаст сигнал, который будет служить для робота поводом изменить свое поведение. Если используется сенсоры расстояния, то для того, чтобы двигаться вдоль стены, не обязательно приближаться к ней вплотную – достаточно приблизится на какое-нибудь удобное расстояние и во время движения стараться находиться все время на том же расстоянии от стены. В таком случае, резкое изменение расстояния, сигнализирует о том, что роботу нужно совершить существенную корректировку своего курса, например поворот за угол.
Сенсор освещенности может также использоваться роботом в контексте определения расстояния – чем ближе сенсор к стене, тем больше света возвращается (от светлой стены), чем дальше от стены, тем меньше света возвращается.
Итак,как будет выглядеть наше движение?
Когда мы рукой чувствуем стену – мы спокойно движемся. Когда стена обрывается
, значит, лабиринт в этом месте делает поворот. Мы тоже сделаем тогда поворот.
Если все время держать руку на стене и двигаться вперед, в конце концов, произойдет такая ситуация, когда лбом вы стукнитесь об стену – в том месте, где стена справа заканчивается
, соединяясь с другой стеной.
Поэтому, чтобы уберечь свой лоб, рекомендуется вторую руку держать перед собой. Для робота второй рукой будет еще один сенсор. Причем, можно использовать как один из тех трех сенсоров, что перечислялись выше – сенсор расстояния, сенсор касания, сенсор освещенности, так и счетчики поворота оси двигателей. Если до столкновения счетчик поворота оси двигателя увеличивался на одну постоянную величину за единицу времени, то после столкновения характер изменений будет другим – за ту же единицу времени прирост будет значительно меньше - при столкновении со стеной-препятствием, двигатели начнут вращаться медленнее.
Ответной реакцией на столкновение со стеной будет поворот к ней боком, после чего уже эта стена будет использована как "опорная" вашей правой рукой. Движение продолжится вдоль нее.
В итоге на текущий момент, получается следующее правило обхода лабиринта: двигаемся прямо, пока под нашей рукой чувствуется стена, как только стена обрывается
поворачиваемся направо
, чтобы найти ее и двигаемся снова вдоль стены, если же другой рукой мы ощутили стену спереди
, то поворачиваемся налево
и используем уже эту стену для движения вдоль нее.
Если продолжить наблюдать за роботом, выполняющим данный алгоритм, то в итоге можно увидеть, что он достигает выхода из лабиринта:
Приведенный выше алгоритм называется "Правилом правой руки" и может быть успешно использован для выхода из всех лабиринтов, которые имеют выход.
В статье описано создание робота, который ездит по линиям и может проехать через лабиринт, а потом кратчайшим путем вернутся в начало. Этот робот получился у меня с 3-ей попытки.
Для начала, видео работы робота:
Список деталей:
2 микродвигателя.
Пара кронштейнов для двигателя.
Пара колес.
Шарик и корпус.
Аналоговые датчики отражения.
Болты и гайки #2.
Arduino RBBB
Драйвер для моторов.
Держатель 4х AAA батарей.
4 аккумулятора AAA.
Болты, гайки, шайбы и стойки.
Провода.
Припой.
Инструменты:
Паяльник.
Отвертка.
Плоскогубцы.
Теория
Есть две задачи которые надо решить: найти выход и оптимизировать обратный путь.
Для обнаружения выхода я руководствовался методом левой руки. Представьте, что вы находитесь в лабиринте и постоянно держите левую руку на стене. В конце концов, это позволит вам выйти из незамкнутого лабиринта. Робот работает только с незамкнутыми лабиринтами.
Способ левой руки описывается простыми условиями:
- Если вы можете повернуть налево, поверните налево.
- Если вы можете двигаться прямо, то двигайтесь прямо.
- Если вы можете повернуть направо, поверните направо.
- Если вы в тупике, развернитесь.
Робот должен принимать решение на перекрестке. Если робот на повороте не поворачивает, то он движется прямо. Каждое решение принятое роботом записывается в его памяти для построения оптимального обратного маршрута
L = Левый поворот
R = Правый поворот
S = Пропуск поворота
B = Разворот.
На картинке выше показан этот метод в действии. Путь к выходу - это LBLLBSR.
Мы должны превратить путь LBLLBSR в оптимальный путь SRR. Для этого необходимо найти место где робот повернул не туда. "B" это разворот, который может произойти в тупике, т.е. на неверном пути.Чтобы
оптимизировать путь мы должны заменить "B" на что то другое.
Давайте рассмотрим первые 3 действия LBLLBSR - LBL. Вместо того, чтобы повернуть налево, развернуться и опять повернуть налево, робот должен был пойти прямо. Таким образом, мы можем сказать, что LBL = S.
Вот полный список подобных замен:
LBR = B
LBS = R
RBL = B
SBL = R
SBS = B
LBL = S
В лабиринте могут быть не все эти повороты, но они необходимы. Некоторые из них даже возвращают B обратно. Это необходимо для дальнейшей правильной оптимизации пути.
LBL = S, новый путь SLBSR. LBS = R, новый путь SRR. Как вы видите, мы получили оптимальный путь. Мой робот оптимизирует путь во время движения. Путь хранится в массиве, и каждый раз перед сохранением хода он проверяет, что предыдущий ход не B, а если В, то оптимизирует путь. Роботу необходимо знать по крайней мере 3 последних хода, для оптимизации алгоритма прохождения пути.
Рассмотрим другой пример.
Если использовать правило левой руки для вышеприведенного лабиринта, то получим следующий алгоритм: LLLBLLLRBLLBSRSRS
Начинаем сокращать:
LL (LBL = S) LL (RBL = B) (LBS = R) RSRS = LLSLLBRRSRS
Продолжаем:
LLSL(LBR = B)RSRS = LLSLBRSRS
Продолжаем:
LLSBSRS
Продолжаем:
LL (SBS = B)RS = LLBRS
Продолжаем:
L (LBR = B)S = LBS
Итого:
LBS = R
Шасси
Шасси робота сделано из акрила толщиной 0.8 и вырезано лазером. К статье прилагается файл AutoCAD с чертежом. Если у вас нет возможности точно повторить его, можете сделать его как вам удобно. На функционал это не повлияет, возможно придётся немного поправить код.
Нижняя часть имеет отверстия для крепежа двигателей, Arduino, металлического шарика, датчика и верхней части. В верхней части есть одно больше отверстие для проводов от аккумулятора, который крепится на липучки и отверстия для прикрепления низа.
Установка привода колес
Я просто прикрепил каждый двигатель при помощи двух болтов. После этого, я одел на ось колёса простым надавливанием. Совместите D образный вал с отверстием в центре колеса.
Arduino
Следуйте инструкциям по сборке Arduino RBBB. Вам нужно будет отрезать часть платы для уменьшения размеров. Если вы не нуждаетесь в разъеме питания и стабилизаторе просто отрежьте их. Для этого можно использовать ножницы по металлу, пилу по металлу или любой подобный инструмент. Не паяйте на плату разъёмы кроме тех, которые необходимы для программирования по порту FTDI. Потом припаяйте 9-контактный разъем на левой стороне платы на контакты от "5В" до "А0". Позже к ним будет подключен датчик. Припаяйте 4-контактный разъем на правую сторону платы на контакты от "D5" до"D8". К ним будет присоединён контроллер двигателя. Припаяйте 2-контактный разъем к GND и 5V. На них будет подаваться питание.
Контроллер двигателя
Я разработал и приложил печатную плату в формате Eagle для контроллера двигателя.
Если вы не используете плату, вы можете сделать это навесным монтажом.
Первый двигатель подключается к контактам, которые я назвал "М1-А" и "M1-B". Второй двигатель подключается к "М2" и "М2-B". 7 вывод Arduino подключается к первому входу первого двигателя "В 1А". 6 вывод Arduino подключается к "В1B". 5 вывод Arduino подключается к первому входу второго двигателя "В2А". 8 вывод подключается к "В 2В". Питание и GND подключается к +5В и GND контактам Arduino.
Датчики
Изначально датчик продается в виде платы из 8 датчиков. Два датчик по краям могут быть удалены. 9-контактный разъем должен быть припаян к датчику от "GND" до "6". Потом к ним подключается ответная часть провода, от которой идут к Arduino.
Эти датчики уменьшают напряжение в зависимость от того, как сильно ИК-лучи отражаются от поверхности. Мы можем использовать их для обнаружения белых и черных участков лабиринта. Датчик выдает напряжение около 0В при обнаружении белой поверхности и напряжение около Vin при обнаружении тёмной поверхности.
Сборка верхней части
Прикрепите верхнюю часть к нижней, при помощи болтов и стоек. Аккумулятор прикрепите к ней при помощи липучки. Закрепите верхнюю палубу. Используйте липучку для крепления аккумулятора. Пропустите провода от него через большее отверстие в верхней части. Мой аккумулятор имеет встроенный выключатель питания. Я обнаружил, что проще не ставить винт на крышке аккумулятора. Она и так неплохо держится, а отсутствие винта позволяет быстро вынуть один из аккумуляторов.
Подключение и установка датчиков
Датчик крепится при помощи болтов к нижней части. Вывод GND на дальней левой части датчика подключается к GND Arduino. Следующий вывод это Vcc, который подключается к 5В Arduino. Контакты 6 - 1 аналоговых датчиков подключены к контактам АЦП 5 – 0 Arduino. Т.е. контакт 6 датчика подключен к контакту АЦП 5 Arduino, контакт 5 датчика подключен к 4 Arduino, и т.д
