Как проходить лабиринты
Мы подобрали 9 популярных способов прохождения лабиринтов: они основаны на алгоритмах действий.
1. Следование вдоль стен (Wall follower). Один из самых простых способов — таким образом можно быстро пройти лабиринт, не используя дополнительной памяти.
Сначала необходимо начать с проходов, а в момент, когда на пути появляется развилка, всегда поворачивать направо (или налево). Для применения способа в головоломке из реальной жизни следует класть руку на правую или левую стену (в зависимости от того, что вы выбрали) и всегда ее держать на этой стороне.
2. Алгоритм Пледжа. Такой способ — дополненная версия следования вдоль стены. Его преимущество в том, что при прохождении головоломки человек способен перепрыгивать между «островами».
Для начала нужно выбрать направление, по которому вы всегда будете следовать. Если на пути попадается стена, стоит начать идти вдоль, пока не появится возможность продолжить путь по алгоритму. При этом рекомендуется начать с дальней из них.
Проходящий головоломку подсчитывает сделанные повороты по определенному правилу. Поворот налево — -1, поворот направо, в свою очередь, — +1. Когда сумма сделанных поворотов окажется равнозначной, то нужно прекратить следование вдоль стен — далее идет движение в выбранном направлении.
3. Алгоритм цепей (Chain algorithm). Человек, решающий головоломку, воспринимает ее как некие звенья одной цепи — получаются несколько лабиринтов меньшего размера, которые нужно решить по порядку. Нам необходимо обозначить места начала и конца, а с помощью них алгоритм укажет верный путь. Важно учесть, что такое решение не подойдет, если проходящий лабиринт не знает точного расположения конца.
Рисуем прямую линию от начала до конца (можно позволить ей пересекать стены). Далее следуем по линии: в случае тупика идем в обход. Также в этом способе существуют «роботы» — двоих отправляем вдоль стен, на которые наткнулись при решении. Есть два условия:
— в случае, если робот опять пересечется с нашей линией (в точке, которая ближе к выходу), то нужно следовать по этой стене до тех пор, пока не достигнем ее самостоятельно. О пути по линии при этом не забываем: важно повторять процесс, пока не дойдем до конца;
— в случае, если все два робота возвращаются к тем локациям головоломки, которые были изначально, то лабиринт решить невозможно.
4. Алгоритм Тремо (Trémaux's algorithm). Он применяется для прохождения лабиринтов, где человек находится непосредственно внутри. При движении по проходу рисуем линию за собой, помечающую наш путь. Если встретили тупик, — делаем поворот назад и возвращаемся таким же путем, которым пришли. Дойдя до неизвестной нам развилки, выбираем новый проход (можно случайным образом). Есть два варианта развития событий:
Идем по новому проходу и натыкаемся на развилку, встреченную ранее, — определяем ее как тупик и возвращаемся путем, которым пришли.
Идем по проходу, помеченному ранее, и встречаем развилку — выбираем любой новый проход. Если это невозможно сделать, то проход, который пометили раньше.
5. Заполнитель тупиков (Dead end filler). Предварительно просканировав лабиринт, заполняем каждый тупик — то есть делаем заливку прохода в обратном порядке от тупика до появления развилки. Становится очевидным решение: их может быть несколько в зависимости от того, сколько выходов у головоломки. Стоит заметить, что этот алгоритм может не сработать в лабиринтах без тупиков.
6. Cul-de-sac filler. Для прохождения игры по этому алгоритму мы сканируем лабиринт и для каждой петлевой развилки добавляем стену, чтобы превратить всю петлю в длинный тупик. Дальше нужно применить Dead end filler. Важно: здесь могут находиться петли, которые вылезают из других конструкций (они превращаются в петли после удаления первых петель). Из-за этого важно повторять всем процесс до тех пор, пока сканирование не будет давать результатов.
7. Blind alley filler. С помощью такого способа прохождения лабиринта можно найти все возможные пути, заполнив тупиковые развязки.
В каждую развилку лабиринта отправляются роботы, которые будут следовать вдоль стен. Мы наблюдаем за их поведением — нужно отследить, вернулся ли отправленный робот таким же маршрутом. Если да, то этот проход и все, что находится после него, не может стать решением. Именно по этой причине нужно нужно перекрыть наш проход и залить все находящееся за ним. Этот алгоритм заполняет все то же, что и cul-de-sac filler плюс несколько путей.
8. Collision solver. С помощью этого алгоритма можно найти все наиболее короткие решения. «Вода» заливает пространство: получается, что все на одном расстоянии от начала заполняется одновременно. В момент, когда два «столбца воды» становятся ближе к проходу (с обеих сторон), в исходную головоломку надо добавить стену в месте столкновения. Далее все части лабиринта уже «затоплены», а проходящий, в свою очередь, заполняет новые препятствия за исключением находящихся на кратчайшем пути. Далее нужно лишь повторять способ, пока столкновения не исчезнут полностью.
9. Поиск кратчайшего пути (Shortest path finder). Способ похож на Collision solver — «вода» заполняет лабиринт, и все, что находится на одном расстоянии от начала, заливается одновременно. В то же время каждая «капля» способна запомнить, какой именно из них они были заполнены. Далее мы возвращаемся от «капли», попавшей в решение, к началу. Именно так определяется кратчайший путь. Такой алгоритм решения головоломки хорошо подходит для любых входных данных.
#ЗагадочныеСооружения
Нет комментариев