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