@6opoDuJIo28 фев 2016 в 22:21

Pathfinding: До одури простая реализация алгоритма воронки (Funnel Algorithm)

3 мин

20K

C++ * Разработка игр * Алгоритмы * Программирование *

Туториал

Перевод

+14

Комментарии 11

@Scf 29 фев 2016 в 05:55

Вот неплохое описание самого алгоритма (на буржуйском): http://ahamnett.blogspot.ru/2012/10/funnel-algorithm.html

@6opoDuJIo 29 фев 2016 в 06:14

Одна из иллюстраций — из моего источника :D

@Sykoku 29 фев 2016 в 16:12

Когда-то делал реализацию досягаемости объекта из определенной точки (военные, где поставить машину связи, чтобы она добивала до всех и не обязательно напрямую, т.е. присутствуют ретрансляторы). Мне было проще реализовать через графы и массив связей.
Например, если 1-й связан с 5-м, а 5 еще и с 9-м, то путь 1-9 существует. Присваиваем каждому отрезку пути свои атрибуты (расстояние, надежность, время доступности, ширина канала, защищенность и т.д.) и получаем итоговую характеристику длины и качества пути.
Решалось за доли секунды еще на 486-х.

@6opoDuJIo 29 фев 2016 в 19:25

Тут задача несколько иного рода — необходимо упростить уже имеющийся путь, который задан в виде дерева нод определённой (возможно, переменной) площади/обьёма. Это отлично сочетается с таким популярными алгоритмами поиска пути как A*/GBVFP, т.к. у вас уже есть готовая полигональная сетка.

@Sykoku 1 мар 2016 в 11:42

Ну и чем Вам «волна» не подошла? Заполнение поверхности сделать гораздо быстрее/проще, чем проверять на вхождение в периметр/объем.

@ozkriff 1 мар 2016 в 11:57

Это сводит на нет изначальные плюсы поиска по полигональной навигационной сетке.

@Sykoku 1 мар 2016 в 14:14

Вы задачу не полностью описали, а только алгоритм. Поэтому и непонятно, зачем использовать алгоритм перемещения по червоточинам куска сыра на плоскости фигуры.

@6opoDuJIo 1 мар 2016 в 20:55

Повторюсь — этот алгоритм не обнаруживает путь, этот алгоритм упрощает тот путь, который нашли любым другим подходящим алгоритмом.

@6opoDuJIo 1 мар 2016 в 21:06

Хотя, скорее всего, применить его конкретно для поиска пути все-таки можно будет с таким-же путём в результате. Но такой вариант, обойдётся дороже по времени, особенно при большом количестве агентов.

@hellman 29 фев 2016 в 19:06

Что за "порталы"?..

@6opoDuJIo 29 фев 2016 в 19:19

Насколько я понял, "портал" это просто кусок пространства, снабженный связями с другими такими-же кусками пространства. Например, квадродерево или навмеш состоят из таких "порталов" — это их листья/полигоны. Практически в любой задаче поиска пути вам придётся столкнуться с задачей дискретизации (разбиения) пространства на некоторые области, чтобы построить граф. В данном контексте, это и будет "порталом".

Зарегистрируйтесь на Хабре, чтобы оставить комментарий