Понабилось мне, значит, такая штука, как поиск путей на полу-статической карте. Ясен пень первым делом пошел в поиск. Много чего интересного, но как-то слишком муторно всё. Хотя думаю есть и более простые алгоритмы, но я дальше не пошел и решил сам поумничать.
Нарисовал вот такую карту (кстати, все картинки кликабельны ;-) ):
(источник: upyourpic.org)
Как видно, карта ограничена определенными размерами и на ней есть закрашенные многоугольники - ака "непроходимые места". Также на карту нанесены графы. Графы служат основным путем, к которому и будет цепляться наш "проходимец".
Так вот, допустим есть пример:
(источник: upyourpic.org)
Как я представляю работу алгоритма:
- строим прямую от начальной точки до конечной точки (через всю карту, поверх непроходимых мест, коричневая линия)
- ищем точку, которая находится на прямой (коричневой), до пересечения объекта. Переходим на неё.
- От полученной точки рисуем прямую по принципу первого пункта. Ищем точку по принципу второго пункта.
- Зацикливаем.
- Если мы стоим на точке, от которой до финиша нет препятствий, то проводим прямую линию.
(Проблема 1) Вроде всё легко и просто. Но прикол в том, что точка, на которую мы перемещаемся, может быть близко, но путь длинее. А чуть дальше будет точка, которая дальше, но через неё путь короче.
Как вариант думаю - перебирать все пути до конечной цели и сравнивать их длину, но чото мне стремно становится от такого дела.
(Проблема 2) Плюс на карте будет присутствовать такая штука, как "переменная проходимость" через непроходимые места, т.е.:
(источник: upyourpic.org)
Собственно у меня тоже есть некоторые мысли, но они требуют доработки по существующим проблемам. Добавлю то, что на карте не будет непроходимых мест (т.е. не получится застрять в каком-нибудь квадрате с внутренним вырезом, из которого нельзя выйти).
Более просто: хотелось бы услышать мнения по улучшению существующего находа пути + идеи по решению проблемы 1 и 2.