OrionXL

Волновой алгоритм. Нахождение пути в лабиринте

Роман Иванов @ 13:05 06.12.2009

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

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

Исходные данные, цели и задачи, которые требуются для работы волнового алгоритма можно кратко сформулировать следующим образом:

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

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

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

Как работает волновой алгоритм?

Основная идея волнового алгоритма описывается следующими этапами:

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

wave-algorithm-pic1

Рис. 1 Первый шаг

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

wave-algorithm-pic2

Рис. 2 Последующее распространение волны

2. На втором этапе волнового алгоритма строится сама трасса. Ее построение необходимо осуществлять в соответствии со следующими правилами:

a) Движение при построении трассы необходимо осуществлять в соответствии с выбранными приоритетами.

b) При движении от конечного элемента к начальному номер фронта волны (путевые координаты) должны уменьшатся.

wave-algorithm-pic3

Рис. 3 Результат действия

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

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

Комментариев нет

Комментариев нет.

RSS-лента комментариев к этой записи.

Извините, обсуждение на данный момент закрыто.

алгоритмы, методы, программы - OrionXL