Поиск пути на карте.

#поиск #пути

Понабилось мне, значит, такая штука, как поиск путей на полу-статической карте. 
Ясен пень первым делом пошел в поиск. Много чего интересного, но как-то слишком муторно
всё. Хотя думаю есть и более простые алгоритмы, но я дальше не пошел и решил сам поумничать. 
Нарисовал вот такую карту (кстати, все картинки кликабельны ;-) ):

Как видно, карта ограничена определенными размерами и на ней есть закрашенные многоугольники
- ака "непроходимые места". Также на карту нанесены графы. Графы служат основным путем,
к которому и будет цепляться наш "проходимец". 
Так вот, допустим есть пример:

Как я представляю работу алгоритма:

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

(Проблема 1) Вроде всё легко и просто. Но прикол в том, что точка, на которую мы
перемещаемся, может быть близко, но путь длинее. А чуть дальше будет точка, которая
дальше, но через неё путь короче. 
Как вариант думаю - перебирать все пути до конечной цели и сравнивать их длину, но
чото мне стремно становится от такого дела. 
(Проблема 2) Плюс на карте будет присутствовать такая штука, как "переменная проходимость"
через непроходимые места, т.е.:

Собственно у меня тоже есть некоторые мысли, но они требуют доработки по существующим
проблемам. Добавлю то, что на карте не будет непроходимых мест (т.е. не получится застрять
в каком-нибудь квадрате с внутренним вырезом, из которого нельзя выйти).
Более просто: хотелось бы услышать мнения по улучшению существующего находа пути
+ идеи по решению проблемы 1 и 2.     

Ответы

Ответ 1

Я бы порекомендовал A*. Он должен перекрывать по производительности алгоритм Дейкстры.
Исходя из дискуссии в комментариях, должен подходить.


Ответ 2

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