Открыть мобильное меню

Алгоритм поиска пути и обхождения препятствий

Очень интересная задача — создание программы на основе алгоритма поиска пути и обхода всевозможных препятствие, как в примере наверху. Если кликнуть в любом месте на пол, шарик покатится объезжая все препятствия. Данный пример реализован на Flash AS3.

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

Рассмотрим суть алгоритма на конкретном примере:

Поиск кратчайшего расстояния до точки

На картинке проверяемая точка зелёная, конечная голубая. По периметру вокруг текущей проверяемой точки создаём область из 8-ми точек, в разных направлениях (для удобства я назвал их сторонами света n,s,w,e,ne...).

Вычисляем какая из 8-ми точек ближе к конечной. В данном случае "ne" (верхняя, правая).

Теперь её необходимо проверить на пересечение каких либо препятствий. Если пересечений нет, то записываем её в массив пути. И она становится следующей проверяемой точкой.

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

ПРимер поиска пути в игре

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

Как видно в примере сверху, около стартовой зелёной точки образовалась большое скопление проверенных и тупиковых точек. Они проверялись до тех пор, пока точка "C" не нашла выход.

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

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

Оптимизация траектории

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

Для этого я решил исходить от обратного. Берём финальную точку и проверяем с предпоследней на пересечение с преградой. Потом следующую с конца, до тех пор пока не возникнет пересечение со стеной. Записываем в массив финальную и точку до пересечения. Таким образом мы получаем чистый путь. В примере "Перелёт" получается именно по этой причине.

Скрипт можно скачать в as или zip

Задайте вопрос или оставьте комментарий:


Вопросы и комментарии: