Задача о прохождении лабиринта интересна не только бездельникам и детям. Рано или поздно с этой задачей сталкиваются программисты, которым надо написать курсовую или дипломную работу или реализовать алгоритм некоторой компьютерной игры. Общеизвестны правила прохождения лабиринтов, которые и закладываются в основу компьютерных алгоритмов. Но всегда хочется придумать что-то новенькое и оригинальное.
Специалисты лаборатории
studlab.com решили развлечься и придумать общедоступный способ. Для начала мы подобрали пару лабиринтов. Что значит общедоступный? А такой, чтобы для реализации можно было использовать только подручные средства. При этом не должно быть никакокой математики и никаких сложных логических умозаключений. На картинке слева, пример простейшего лабиринта. Попробуйте его пройти. Кстати, если кликнуть по изображению, то оно увеличится. Вы легко справитесь с этим лабиринтом, тем более, что путь от входа к выходу есть. А ели нету? Тогда придется перебрать большое число вариантов, пока удастся в этом убедиться. Между прочим, для того, чтобы доказать что пути нет, надо начинать не со входа а с выхода. Так получается обычно быстрее, потому что все тупики- ловушки обычно смещают к выходу.
Для решения задачи, было решено использовать первый попавшийся под руку графический редактор с функцией заливки. Попытка заливать путь к успеху не привела - заливались все возможные пути перемещения и поэтому весь лабиринт заполнялся цветом заливки. И тут появилась идея: заливать препятствия (стены). Ведь одним из известных методов является метод "левой руки": вы держитесь за стену левой рукой и уверенно идете к выходу. На картинках вы видите исходный одноцветный лабиринт и лабиринт, в котором была выполнена заливка препятствий. Теперь совершенно понятно, что двигаться надо так, чтобы слева была стена одного цвета, а справа другого. Мы не будем считать этот метод новым. Скорее всего, его можно назвать отличной визуализацией алгоритма "левой руки".
Особенно эффективным он будет для тех лабиринтов, где применяются визуальные эффекты симметрии для запутывания игрока. Лабиринт слева - идеальный пример такого симметричного алгоритма. Попробуйте его пройти. Вы сразу поймете, что сделать это будет совсем не просто. Здесь оказалось достаточным использовать заливку только одним цветом. Конечно, можно было заливать несколько раз, пока весь начальный цвет не будет перекрашен в разные цвета. Тогда возможно, возникнет даже несколько вариантов прохождения.
Чтобы заливка сработала, надо убедиться в том, что залиты новым цветом и стены у самого выхода. Поэтому, делаем вывод: в качестве начальной точки для заливки следует выбирать не случайную точку стены лабиринта, а точку на одной из стен, расположенных в воротах выхода. По этому же принципу следует строить и компьютерный алгоритм. Он, в этом случае, будет перекликаться с известным алгоритмом Ли нахождения кратчайшего пути от начальной точки к конечной при наличии препятствий. Понятно, что метод заливки эффективен, когда препятствия представляют собой связные (термин из теории графов) области. Чем многосвязнее область, тем больше потребуется цветов для закраски. Если каждое препятствие отдельный объект, то алгоритм работать не будет.
