Комментарии 11
Вот неплохое описание самого алгоритма (на буржуйском): http://ahamnett.blogspot.ru/2012/10/funnel-algorithm.html
Когда-то делал реализацию досягаемости объекта из определенной точки (военные, где поставить машину связи, чтобы она добивала до всех и не обязательно напрямую, т.е. присутствуют ретрансляторы). Мне было проще реализовать через графы и массив связей.
Например, если 1-й связан с 5-м, а 5 еще и с 9-м, то путь 1-9 существует. Присваиваем каждому отрезку пути свои атрибуты (расстояние, надежность, время доступности, ширина канала, защищенность и т.д.) и получаем итоговую характеристику длины и качества пути.
Решалось за доли секунды еще на 486-х.
Например, если 1-й связан с 5-м, а 5 еще и с 9-м, то путь 1-9 существует. Присваиваем каждому отрезку пути свои атрибуты (расстояние, надежность, время доступности, ширина канала, защищенность и т.д.) и получаем итоговую характеристику длины и качества пути.
Решалось за доли секунды еще на 486-х.
Тут задача несколько иного рода — необходимо упростить уже имеющийся путь, который задан в виде дерева нод определённой (возможно, переменной) площади/обьёма. Это отлично сочетается с таким популярными алгоритмами поиска пути как A*/GBVFP, т.к. у вас уже есть готовая полигональная сетка.
Ну и чем Вам «волна» не подошла? Заполнение поверхности сделать гораздо быстрее/проще, чем проверять на вхождение в периметр/объем.
Что за "порталы"?..
Насколько я понял, "портал" это просто кусок пространства, снабженный связями с другими такими-же кусками пространства. Например, квадродерево или навмеш состоят из таких "порталов" — это их листья/полигоны. Практически в любой задаче поиска пути вам придётся столкнуться с задачей дискретизации (разбиения) пространства на некоторые области, чтобы построить граф. В данном контексте, это и будет "порталом".
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Pathfinding: До одури простая реализация алгоритма воронки (Funnel Algorithm)