Давайте глобально обсудим эту тему. Возможно, даже, чтобы в статьи в итоге добавить.
Даже не потружусь собрать и систематизировать о поиске пути доку.
Вопрос мой такой:
1. Кто какими поисками пользуется(кроме а*, д*, волнового)?
2. Кто знает о так называемом "ray-tracing" поиске пути (карта должна быть векторная, или приводимая к векторной) ?
И еще один вопрос по поводу ray-tracing поиска.
Но сначала кратко расскажу, что это такое.
допустим, карта у нас 1.0х1.0(х1.0 для 3д, но пока рассмотрим вариант для плоскости) (работаем с числами с плавающей точкой (запятой)), реальный размер карты - не по сути.
местонахождение обьектов определяется как 2(3 для 3д) переменные, значение которых от 0.0 до 1.0 (если не учитывать их ширину).
конкретный пример для 2д:
у нас есть препятствие от (0.2,0.5) до (0.9,0.5). (стена посреди карты, расположенная горизонтально, но не на всю ширину карты, таким образом, что справа просвет до границы - 0.1 карты, а слева 0.2).
обьект наш находится в точке (0.5,0.0). шириной обьекта можно пренебречь.
а путь его лежит к точке (0.5,1.0). шириной цели тоже пренебрегаем.
как ему пройти?.. строится прямая от обьекта до цели, при пересечении с какойто преградой - мы режем на первом пересечении наш путь, и пытаемся повторить снова поиск уже для новых двух ломаных.
когда все полученные линии не пересекают статичных обьектов карты, мы даем эти точки, по которым должен будет пройти наш обьект, и посылаем его по ним.
варианты о встрече с другими обьектами здесь не учитаны, но я так понимаю, что их надо обрабатывать при самой встрече по немного измененному поиску ломаной от текущей позиции до той точки, куда шел обьект до встречи (то есть до ближайшей не достигнутой точки).
что скажете?.. как оптимально можно это просчитать?
p.s. Не могу обойтись без копирайтов, способ этот я узнал от В.Медноногова. http://pmg.org.ru/ai/path.htm, там же есть ссылка на этот способ, но он там не "шлифован".
