Алгоритм воронки
Извлекает настоящий кратчайший путь из коридора треугольников навмеша, когда поиск уже определил, какие треугольники пересекает маршрут.
A* по навмешу выдаёт список треугольников, а не путь. Если просто соединить их центры, получится лишний зигзаг. Алгоритм воронки (funnel algorithm) считает общие рёбра соседних треугольников последовательностью порталов и натягивает между левой и правой сторонами воронку. Он сужает её ребро за ребром; как только левая и правая стороны пересекаются, в самом внутреннем углу ставится путевая точка и начинается новая воронка. Выходит, будто верёвку протянули через коридор и натянули.
Основа — работа Хершбергера и Снойинка (1994); в играх алгоритм знают главным образом по компактной версии Микко Мононена — «simple stupid funnel algorithm». Это очевидный шаг постобработки между поиском по треугольникам и линией, по которой агент действительно идёт.