Реализации алгоритмов обхода припятствий

Question

[tac]

Кто в курсе подскажите:

1. какие алгоритмы обхода препятствий сейчас самые лучшие? (интересуют названия)
2. При оценке «лучшести» учитываем скорость расчета, работу в трехмерности, учет объемного тела, которое перемещается (т.е. чтобы обходящий препятствие не надумал бы лезть как вини-пух в дырку в которую не пролезит, и так чтобы не выдумал построить такой путь в принципе, т.е. чтобы пройдя 100 шагов, не оказалось что 101-й оказался узким, и снова надо возвращаться в шаг 1), сложные объемные препятствия. А также важно, чтобы пространство не надо было разбивать на равные кубики, а путь строился бы по минимальному числу опорных точек. Т.е. вариант идти в квадратик 1, а потом в квадратик справа, три квадратика прямо — не годится.
3. Интересуют именно уже готовые реализации. Т.е. без открытого кода не интересно.

Answer 1

[Виталий Желтяков]

Алгоритмы такие же как и много лет назад — waypoint-ы и алгоритмы поиска пути.

Answer 2

[Александр Юдаев]

Найденный Вами алгоритм Navigation Mesh — пожалуй, самый лучший вариант на текущий момент. Его, например, использует движок Unreal Engine.
Еще можно посмотреть на алгоритмы AA*, HPA*, HAA*, они учитывают размер объекта. Недавно как раз была статья.

Answer 3

[tac]

Отвечу сам себе, кто пробовал recast — code.google.com/p/recastnavigation/? Вроде как похоже на то, что надо…