Путь в двумерном лабиринте волновой алгоритм


Содержание

Как найти кратчайший путь в лабиринте?

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

В конечной ячейке:
map[finishX][finishY] = 19;

После прохода волнового алгоритма лабиринт выглядит так:
0 0 0 0 0 0 0 0 0 0 0 0 0
0 7 8 9 10 11 12 13 14 15 16 17 0
0 6 7 8 9 10 11 12 13 14 15 16 0
0 5 6 7 8 9 10 11 12 13 14 15 0
0 4 5 6 7 8 9 10 11 12 13 14 0
2 3 4 5 6 7 8 9 10 11 12 0 15
1 0 4 5 6 7 8 9 10 11 0 13 14
2 0 5 5 6 7 8 9 10 11 0 14 14
0 0 6 6 6 7 8 9 10 11 0 15 0
0 0 7 7 7 7 8 9 10 11 0 15 0
0 0 8 8 8 8 8 9 10 11 0 14 0
0 0 9 9 9 9 9 9 10 11 12 13 0
0 0 0 0 0 0 0 0 0 0 0 0 0

Suvitruf’s Blog :: Gamedev suffering

Блог о разработке игр и серверных технологиях

Обход препятствий: волновой алгоритм (Алгоритм Ли)

Волновой алгоритм (Алгоритм Ли)

Тема нахождения пути на карте волнует многих программистов (в основном занимающихся разработкой игр). Заинтересовался этими алгоритмами. Решил для начала самый простой рассмотреть — волновой алгоритм (алгоритм Ли) .

Волновой алгоритм (Алгоритм Ли)

Волновой алгоритм один из самых уникальных алгоритмов трассировки. Он позволяет построить путь между двумя элементами в любом лабиринте. Сам процесс можно разделить на 2 этапа.

1. Из начального элемента распространяется в 4-х направлениях волна (см. рисунок сверху). Элемент в который пришла волна образует фронт волны. На рисунках цифрами обозначены номера фронтов волны.

Каждый элемент первого фронта волны является источником вторичной волны. Элементы второго фронта волны генерируют волну третьего фронта и т.д. Процесс продолжается до тех пор пока не будет достигнут конечный элемент. Ну, или пока не станет ясно, что его не достигнуть.

2. Строится сама трасса. Её построение осуществляется от конечного элемента к начальному.

Плюс алгоритма в том, что он позволяет найти путь в любом лабиринте (при условии, что путь существует). Но главный недостаток этого алгоритма в том, что при построении трассы требуется большой объем памяти.

Существует два способа определения количества соседних клеток: считать соседними клетки, доступные через обще грани (их 4) и считать соседними клетки, доступные через общие грани и общие углы (таких клеток будет 8). Я реализовал пока более простой вариант, используя 4 клетки. Ну, сразу видны минусы. Вместо того, чтобы идти по диагонали, алгоритм идёт по прямой. Известно, что сторона треугольника меньше суммы двух других сторон. Так что, для более лучшего поиска, лучше использовать 8 клеток.

Посмотреть как это работает можно ниже.

Видно сразу — не все клетки алгоритм обошёл, что говорит о его эффективности. Если увеличить количество просматриваемых клеток до 8, то ещё более эффективно станет.

HTML5, Canvas и Web Workers

Реализовано это дело на HTML5, просто ради фана, да и для наглядности. Решил заодно потестить и потоки (Web Workers) в js. У потока на входе точка, окружение которой необходимо просмотреть, и массив.

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

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

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

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

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

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

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

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

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

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

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

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

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

Илон Маск рекомендует:  Что такое код swfdisplayitem >scaleto

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

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

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

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

Ну а как же нам найти кратчайший путь? Очень просто. Нужно на каждом шаге, начав отсчет от финиша, искать клетки, помеченные все меньшим и меньшим числом. От «девятки» ищем «восьмерку», от неё — «семерку» и т.д. В 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, использовать в лабораторной работе, создать соответствующий метод или функцию или даже написать небольшую игру. Код снабжен краткими пояснениями на английском языке.

Путь в двумерном лабиринте волновой алгоритм

Найти наикратчайший путь для выхода из лабиринта, либо указать, что пути нет.

Входные данные

Текстовый файл с закодированным лабиринтом. Обозначения: 0 — пусто, 1 — стена, 2 — герой, 3 — выход. Пример:

Задача

Найти наикратчайший путь от позиции героя до точки выхода из лабиринта используя волновой алгоритм.


Выходные данные

Файл аналогичный исходному, в котором символами * обозначен путь от позиции героя до точки выхода. Например:

Допускается также визуализация пути псевдографикой в консоли. Можно, также, реализовать анимацию «побега».

Тестирование

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

Действия

  • К списку задач
  • Другие задачи того же блока

© Олег Дашевский со товарищи, 2010–2020. Сайт работает на платформе Coursette

Реализации алгоритмов/Алгоритм Ли

Алгори́тм волново́й трассиро́вки (волновой алгоритм, алгоритм Ли) — алгоритм поиска пути, алгоритм поиска кратчайшего пути на планарном графе. Принадлежит к алгоритмам, основанным на методах поиска в ширину.

C++ [ править ]

В приведённом примере производится поиск ортогонального пути (считаются 4 соседа клетки). Перед вызовом функции lee() массив grid должен быть заполнен значениями WALL (непроходимая ячейка) и BLANK (проходимая непомеченная ячейка). Если функция lee() возвращает результат true, то в массивах px и py остаются координаты ячеек пути в порядке от стартовой (px[0], py[0]) до финишной (px[len], py[len]).

Илон Маск рекомендует:  Как убрать кнопку с taskbar'а

Pascal [ править ]

Данные приводятся в виде (c новой строки)
Размера массива «n m»
Двумерного массива из «@» и » «
Стартовой ячейки «x y»
Финальной ячейки «x y»
На выходе мы получим последовательные координаты в виде « .. »

H Алгоритм поиска пути в лабиринте и его реализация на Python 3.4 в черновиках Из песочницы

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

Итак, будем пытаться написать его самостоятельно, а для этого нужно продумать, как он должен работать. Для этого возьмём достаточно легкую задачу:

  1. Для начала разберемся с входными данными: у нас есть матрица элементов, где 0 — пустые клетки, а 1 — стенки.
  2. При вводе меняем «1» на «-1» (этого требует алгоритм)
  3. Далее нужно выбрать ячейку, с которой начнется обход
  4. Рекурсивно обойти лабиринт от выбранной ячейки, вставляя в ячейку текущий «уровень волны»

Ввод данных будет выглядеть следующим образом:

Теперь у нас есть двумерная матрица, представляющая наш лабиринт.
Далее нам нужно написать функцию, которая будет обходить наш лабиринт:

Где x, y — координаты текущей ячейки; cur — «уровень волны»; n, m — размеры лабиринта; lab — сам лабиринт.
Для начало нужно заполнить текущую ячейку уровнем воды:

Далее проверим, есть ли у нас возможность «пойти» влево:

Если есть такая возможность, то проверяем, нет ли там стенки или текущий «уровень воды» меньше, чем в ячейке справа :

И в случае «успеха» рекурсивно идем вправо:

Теперь нужно точно также проверить возможность пройти вниз, влево и вверх:

Все, осталось в конце вернуть текущий лабиринт:

Спасибо за прочтение, надеюсь, кому-то будет полезно.

Волновой алгоритм.Задача про лабиринт.

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

numWave-номер волны,flag-отвечает за проходимость,flagend-отвечает за факт достижения выхода,pend==-3;-точка конца,т.е. которую нужно достичь.

При while ((flagend!=1) || (flag!=-1)); бесконечный цикл,а при while ((flagend!=1) && (flag!=-1)); заполняется ВСЯ матрица номерами волн,хотя мне нужно,чтобы он заполнял только до клетки выхода,которая находится где -то около середины лабиринта.Лабиринт один и тот же пока (10×10) если нужно ,могу написать его.

мне нужно,чтобы он заполнял только до клетки выхода

Используй goto вместо break.

Хотя мне просто не нравится этот стиль, даже в рамках стиля код ужасен. Часть отступов потеряна, часть пробелами, часть табами. Какие-то мусорные комментарии. Не понятно, что значит flag.

И ещё. Чем этот алгоритм отличается от алгоритма Дейкстры?

перебирать каждый раз все поле не хорошо. лучше уж хранилище координат i-той волны.

Алгоритмы генерации лабиринтов

Лабиринты — это не только самостоятельный класс игр, но и основа для создания локаций в играх других жанров: например, систем пещер, которые, в свою очередь, могут быть использованы в очень широком классе игр-бродилок и т.д. Однако если игроку придется постоянно «изучать» одни и те же локации, ему это может скоро надоесть, а потому перед разработчиками игр встает вопрос о процедурной генерации лабиринтов, т.е. чтобы каждое очередное прохождение игры проходило на заново сгенерированной территории.

Таких алгоритмов существует уже очень много, поэтому представленная нами подборка не претендует на полноту — в комментариях вы можете поделиться ссылками на известные вам способы генерации лабиринтов.

Лабиринты мы будем строить на прямоугольном клеточном поле (+ одна из статей о генерации в трехмерном пространстве), поэтому все их можно разделить на две группы: лабиринты с «тонкими» стенками и с «толстыми». Первые — это те, у которых стены расположены на границах клеток, вторые — это те, в которых некоторые клетки сами являются непроходимыми, т.е. стенами. Их отличает, например, способ хранения данных о карте.

Также существуют уже готовые решения для генерации лабиринтов: генератор Oblige, который используется в DOOM, DOOM II и Heretic, и др.

Алгоритм Эллера

На тему генерации лабиринтов, где стенки расположены на границах клеток, на Хабре есть хороший перевод статьи «Eller’s Algorithm» (именно Эллера, а не Эйлера — «Eller’s», а не «Euler’s») о том, как создать идеальный (perfect) лабиринт — такой, что между любыми двумя его клетками существует путь, и притом единственный.

23 ноября в 10:30, Санкт-Петербург, беcплатно

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

Хранить карту лабиринта можно, например, в двух двумерных массивах: для вертикальных стенок и горизонтальных, соответственно.

Как хранить лабиринты с «толстыми» стенками?

Ответ на вопрос о хранении карт таких лабиринтов очевиден: в виде двумерного boolean массива, где, например, 1 — это непроходимая клетка (стена), — свободная.

Подробнее о картах на клеточных полях написано в статье «Tilebased games». Теперь перейдем к самим лабиринтам генерации.

Наивный алгоритм

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


Естественно, возникают два вопроса: не будут ли комнаты пересекаться и как проложить между ними переходы? Ответ на первый вопрос зависит от ваших требований к лабиринту: если вы не хотите, чтобы комнаты пересекались, напишите функцию, которая проверяет пару комнат на пересечение и при появлении на карте очередной комнаты делайте проверку.

Чтобы проложить коридоры между помещениями, автор предлагает сначала прокладывать переход от уровня одной комнаты до уровня другой по оси Oy, а затем так же по оси Ox — смотрите поясняющий рисунок.

Подробнее об этом алгоритме (с примерами реализации) читайте в статье «Сreate a Procedurally Generated Dungeon Cave System».

Лабиринт на таблице

У описанного выше алгоритма есть один явный недостаток: проверять, пересекаются ли комнаты, приходится отдельной функцией. Возникает вопрос, можно ли не делать это лишнее действие. Оказывается, можно— и алгоритм описан ниже.

Идея заключается в том, что поле изначально разбивается на прямоугольные «большие» клетки (т.е. не элементарные клетки игрового поля, а прямоугольники, состоящие из нескольких клеток), образуя таким образом таблицу. Далее в каждой такой ячейке случайным образом появляется комната случайного размера, не превосходящая размеров ячейки — тем самым возможность появления пересекающихся помещений пропадает. Затем комнаты объединяются коридорами, например, тем же способом, что описано в предыдущем пункте.

Подробно этот алгоритм генерации описан в статье «Grid Based Dungeon Generator».

BSP деревья

BSP — это аббревиатура от Binary Space Partitioning — двоичное разделение пространства. Этот алгоритм также позволяет избежать пересечения комнат еще в процессе помещения их на карту, т.к. также предварительно делит игровое поле на части — «листья», внутри которых затем генерирует комнаты. Это деление площади идейно сложнее, т.к. разделяет все , чем предыдущий алгоритм, но и позволяет создать более интересные конфигурации расположения помещений.

Илон Маск рекомендует:  Организация списков и их обработка

Почитать подробнее о нем можно в статье «How to Use BSP Trees to Generate Game Maps».

Генерация лабиринтов с использованием клеточного автомата

Каждый программист хотя бы раз писал «Жизнь» — клеточный автомат, придуманный математиком Конвэем. Так почему бы не использовать схожую идею для генерации лабиринтов? Суть предложенного алгоритма состоит в реализации всего двух шагов: сначала все поле заполняется случайным образом стенами — т.е. для каждой клетки случайным образом определяется, будет ли она свободной или непроходимой — а затем несколько раз происходит обновление состояния карты в соответствии с условиями, похожими на условия рождения/смерти в «Жизни».

В источнике — на странице статьи «Generate Random Cave Levels Using Cellular Automata» — вы можете поэкспериментировать с интерактивной демкой, устанавливая различные значения для генерации: количество итераций обновления, граничные значения для жизни/смерти клетки и т.п. — и увидеть результат. Там же рассказывается о подводных камнях реализации.

Генерация в трехмерном пространстве

Также мы не можем оставить без внимания статью о генерации 3D-лабиринтов: «Bake Your Own 3D Dungeons With Procedural Recipes» — основная сложность которого заключается в правильной ориентации элементарных частей лабиринта: коридоров, комнат и лестниц.

Каждый из модулей хранит информацию о своих входах и выходах, а также их ориентации: прежде чем соединить очередную пару элементарных частей, их нужно правильно ориентировать. В частности, автор предлагает хранить x-, y- и z- ориентацию модулей, чтобы затем соединять их по таким правилам: их y-оси должны совпадать, а x и z — иметь противоположное направление. Это, естественно, ставит вопрос о хранении информации о сгенерированной карте. Кроме того, не решена проблема с пересечением помещений — поэтому эта статья может являться лишь отправной точкой для исследования вопросов генерации трехмерных алгоритмов.

Что дальше?

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

Реализация Волнового алгоритма (Алгоритма Ли) на Java

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

Алгоритмов поиска минимального пути большое множество. Но, наиболее простым и эффективным является Алгоритм волновой трассировки (Алгоритм Ли) , который основан на методах поиска в ширину.

В работе данного алгоритма не сложно разобраться. Он будет понятен даже новичку в программировании.

Я буду приводить пример своей работы. У меня имеется подобие клеточного автомата (граф, состоящий из узлов и ребер между ними). На нем будем реализовывать Алгоритм Ли .

Реализация алгоритма состоит из 3-х этапов:

  1. Инициализация начальных данных;
  2. Распространение волны;
  3. Восстановление пути.

Первый этап — Инициализация начальных данных

Вам нужно иметь массив объектов (узлов, ячеек). У меня это класс Node .

Каждый объект, кроме иных, имеет поле near типа, например, ArrayList. В данное поле вы записываете всех «соседей» ( соседние узлы данного узла ).

Каждый узел получает отметку «проходимый / непроходимый».

Записываются стартовый и финишный узлы.

Второй этап — Распространение волны

Вы должны иметь численный массив (по количеству ячеек), куда будут записываться числа (отметки) для каждой ячейки. По умолчанию все значения ячеек равны нулю.

Стартовый узел получает значение 1.

Проверяете все «соседние» узлы данного узла на «проходимость», и проверяете нет ли на них уже отметки. Так как отметка должна ставиться только один раз.

Если все удовлетворительно ставите отметку на 1 больше , чем у предыдущего узла. Далее проверка его «соседних узлов».

Так до тех пор, пока не дойдете до финишной ячейки .

Пример кода:

Третий этап — Восстановление пути

В массив пути заносите финишный узел .

Просматриваете отметки всех узлов, «соседних» к финишному узлу. Заносите в массив пути тот узел, отметка которого на 1 меньше , чем у финишного узла.

Повторяете это действие, пока не будет достигнут стартовый узел .

Пример кода:
Результат работы программы:

Таким образом, я думаю, вы убедились, что Алгоритм Волновой трассировки (Алгоритм Ли) совсем не сложен для реализации. Он выполняет поиск минимального пути, делая небольшое количество вычислений. При желании, данный универсальный алгоритм можно усложнить.

Рекомендуем хостинг TIMEWEB

Рекомендуемые статьи по этой тематике

Путь в двумерном лабиринте волновой алгоритм

Всем хай! Сходу к делу!
Постановка задачи: дан лабиринт прямоугольной/квадратной формы. Человека кидают в произвольный участок лабиринта. Его задача — выбраться кратчайшим путем из лабиринта. Если прямой путь проложить нельзя, то некоторые стены можно прошибать с разбегу лбом! Если приходится пробивать стены, то за кратчайший принимается такой путь, который затребовал минимального количества таких пробитий, несмотря на общую длину траектории. Кол-во прошибаний стенок неограниченно!

Схематика лабиринта и возможные пути показаны на картинке, а также краткий комментарий к ним.
Зеленая ячейка — место высадки чела в лабиринт. Может находиться в любой точке/ячейке/узле лабиринта.
Красная ячейка — место выхода из лабиринта. Может находиться лишь в приграничной зоне, т е на границе периметра лабиринта.
Серые ячейки — стены, через которые проход невозможен. Но их допустимо пробивать лбом с разбега!
Координаты зеленой НЕ РАВНЫ координатам красной.

ВАЖНО! движение по лабиринту соот-ет окрестности фон Неймана, а не Мура, т е двигаться можно строго влево, вверх, вправо или вниз.

====================================================================================================================
Ну, короче, как я понял, да, это задача на классический волновой алгоритм. Структуры данных у меня — простые массивы, очереди, стеки и НИКАКИХ планарных графов. Все шикарно закодировалось с граф.интерфейсом, если нет необходимости прошибать стены, т е можно проложить ПРЯМОЙ путь от начала к выходу. Но не до конца понятно, шо делать, когда нужно прошибать стены лбом!

Например, нет прямого пути. Я запускаю волновой алгоритм и он заканчивается тупиком, т е не достигает выхода. Получается, нужно начинать перебор ВСЕХ пронумерованных ячеек, и, если есть граничащая стенка, то пробивать ее и запускать повторно волновой алгоритм из только что выбитой стенки. Если получилось достичь выхода, то запомнить кол-во выбитых стен. Потом нужно ВОССТАНОВИЬ стенку, чтобы не образовалось необоснованного прохода для др.возможных кратчайших путей + нужно где-то запомнить сам путь. Мороки немерено! Если выхода достичь не получилось, то нужно опять перебирать все ячейки этого хвоста и искать граничащие стенки. Ппц какой-то!

В итоге, такое чувство, что возникает NP-полная задача или почти NP-полная, т е приходится перебирать почти все возможные пути + рекурсия по любому подключается какая-нибудь.

Как это реализуется оптимально?

P.S. нужно считать, что координаты выходной ячейки неизвестны, но выход точно есть! Если есть алгоритм, который очень прост и понятен, но требует знания координат выходной ячейки, то тогда сниму это ограничение

I originate
You must appreciate, all the others imitate
SCOOTER «GUEST LIST»

‘Pon the mic I’m the teacher!
Spread my words like a preacher!
Yiiihhaaaa.
SCOOTER «WEEKEND»

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL