А че вдруг ударились в игровые алгоритмы? Кстати, алгоритм А* применим только для 2.5 мерных игр. В шутерах, например, задача поиска оптимального пути нормально не решена. Те решения, которые имеются в наличии настолько дырявы и требуют такого количества костылей, что говорить о том что есть эффективный алго для трехмерных пространств - это не понимать сути проблемы. Можете подумать на досуге.

Задача вобчем проста. Есть произвольное 3Д пространство, на нем присутсвуют средства передвижения, телепорты, лифты, джамп-пады, горизонтальные передвижные платформы. Есть препятсвия, в виде столбов, по которым надо прыгать, в виде лавы, в виде воды, в виде радиоктивной жидкости. На уровене есть лестницы, ледовые поверхности, то есть места, где скорость объекта отлична от обычной. Есть места "продуваемые" ветром.

Вот. Это не надуманные условия. С этим приходится иметь дело в шутерах. Я причем назвал не все условия. Есть еще триксы. Но о них умолчим.

Lelikk
С задачкой этой я столкнулся когда работал с движком Quake3. Карты там представлены в формате BSP-графа. Нахождение оптимального пути - это написание функции BotMoveToRoute( Bot, goal ) . Сейчас ситуация такая, что критейри всегда один - время. Хотя это неверно. Потому что если бот(робот) "отступает", то ему надо искать безопасный путь, а не короткий. А в понятия безопасности уже входят "закрытость" пути от глаз врага,и "шумность". Когда идешь по воде - издаются звуки, когда по леснице тоже, когда через телепорт - звук телепорта. И т.д.

Стандартно все пашет так, после сборки карты и построения BSP дерева, происходит формирование "путей". Формируются они просто, карта бъется на прямоугольные участки именуемые областями. Вернее бъется сначала на группы областейнаходящиеся на одном "уровне" (разброс Z координаты - высота прыжка игрока). Считается "время" перехода между ними, для этого сначала нужно определить места перехода. Это кстати очень узкое место этого алго, потому что ищет он не больше 4 точек соединения групп областей. Соединения ищутся от BSP объектов карты - порталы, двери, лифты, лестницы, джамппады, кнопки. Время перехода сохраняется.

Далее группа областей делится на прямоугльные участки, это как разбиение траингуляция, только прямоугольниками как в NV1. Далее исключаются прямоугольники недоступные боту (космос, лава и т.д., стены). Дальше мне совсем было не понятно, но почему-то для каждого прямоугоьлника определятся только ТРИ соседа - по минимальному расстоянию между центрами скорее всего(наверное чтобы исключить зациклинность). Далее делается допущение, что из любой прямоугльной области он может идти в соседнюю ПРЯМО, взяв направление на центр. Там есть еще вариант оптимизации вектора направления, но я не буду его описывать - это все усложнит.

Время внутри области считается как обычная задачка равномерного движения. Потом отрезки кидаются в список, а время суммируется по списку - достигаешь виршины - удаляешь елемент списка - минус время. И т.д.

Алго ужасен. Например самый первый недостаток, который можно увидеть - то что края области прямоугольной могут лежать в "плохом" месте, например в лаве или стене. И очень часто можно видеть, как боты сами заходят в лаву или прижимаются к стене и скользят по ней. Есть и другие фишки в виде застревания, в виде мертвых областей - зайти может а выйти нет. Даже пределывание костылей ввиде невидимыйх поверхностей, по которым может ходить только бот, не сильно спасает ситуацию, потому что перепрыгивать длинные ямы они до сих пор не научились.

Это я все говорил о стандартном алго. Канеш кое что удалось сделать некоторым отдельным личностям, в том числе и нам с другом. Но все равно, как не крути, решение требуется ПРИНЦИПИАЛЬНО ДРУГОЕ.

Это была не работа, а скорее увлечение. Ищи в гугле слово spiterbot.