PMG

Форумы по созданию игр
Текущее время: 07 дек 2024 09:29

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: О оптимальном поиске пути.
СообщениеДобавлено: 25 сен 2005 10:18 
Не в сети
Любитель
Аватара пользователя

Зарегистрирован: 25 сен 2005 10:14
Сообщения: 18
Откуда: Kemerovo, Russia
Давайте глобально обсудим эту тему. Возможно, даже, чтобы в статьи в итоге добавить.
Даже не потружусь собрать и систематизировать о поиске пути доку.

Вопрос мой такой:
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, там же есть ссылка на этот способ, но он там не "шлифован". ;)

_________________
свет дает мне силу.

С уважением, Алексей.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 26 сен 2005 10:53 
Не в сети
Гуру
Аватара пользователя

Зарегистрирован: 03 авг 2004 10:37
Сообщения: 2694
Обычно используют стандартный A*, но путь делают более сглаженным. Так же интенсивно используют карты влияния. Очень интересны методы управляемого поведения:
http://www.red3d.com/research.html

Много интересного есть в книге:
O'Reilly - AI for Game Developers.chm

ray-tracing - это метод прокладывания пути до ближайшего препятствия. В результате образуется дерево, которое так же можно пройти A*.

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

_________________
С уважением, Сергей


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 26 сен 2005 11:02 
Не в сети
Любитель
Аватара пользователя

Зарегистрирован: 25 сен 2005 10:14
Сообщения: 18
Откуда: Kemerovo, Russia
Дык через А* нужно сначала перевести вертексную карту в 2д. а после уже искать путь. И получается очень много проблем, хотя и мелких. И скорость. Скорость же ниже?..

а O'Reilly - AI for Game Developers.chm есть?..
можно попросить выслать?.. на адрес в личных.

через ray-tracing разве не быстрее, чем через А*?...

А об D* что можно сказать?..

_________________
свет дает мне силу.

С уважением, Алексей.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 26 сен 2005 11:21 
Не в сети
Гуру
Аватара пользователя

Зарегистрирован: 03 авг 2004 10:37
Сообщения: 2694
D* - это только когда часть карты заранее не видна. A* и ray-tracing надо совмещать, т.е. строить дерево лучей и в нем искать путь по A*. Книга, есть могу выложить куда-нибудь.

_________________
С уважением, Сергей


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 26 сен 2005 11:29 
Не в сети
Любитель
Аватара пользователя

Зарегистрирован: 25 сен 2005 10:14
Сообщения: 18
Откуда: Kemerovo, Russia
Буду премного благодарен за книгу.
Есть хостинг?.. или дать фтп?..

_________________
свет дает мне силу.

С уважением, Алексей.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 26 сен 2005 11:46 
Не в сети
Любитель
Аватара пользователя

Зарегистрирован: 25 сен 2005 10:14
Сообщения: 18
Откуда: Kemerovo, Russia
MagicWolf писал(а):
D* - это только когда часть карты заранее не видна. A* и ray-tracing надо совмещать, т.е. строить дерево лучей и в нем искать путь по A*. Книга, есть могу выложить куда-нибудь.

ну а если невидимую часть карты делать непроходимой...?
тоже самое же получится...

_________________
свет дает мне силу.

С уважением, Алексей.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 26 сен 2005 13:51 
Не в сети
Гуру
Аватара пользователя

Зарегистрирован: 03 авг 2004 10:37
Сообщения: 2694
А зачем это надо?! Делать не проходимой? Себе усложняешь задачу. D* используют для роботов, если карты нет. А так даже нынешние роботы вначале проходят, по заданной местности, изучают ее, а потом уже свободно по ней перемещаются.

В играх как раз все проще, достаточно waypoints, так как можно симулировать нужное поведение у отдельных units. Вот забыл, где-то видел, описание алгоритма, там комнаты разделены на участки просматриваемой местности, и между ними проведены пути (например, путь для быстрого перемещения, путь для скрытого подхода). И юниты перемещаются именно рядом с этими "нитями Арианды".

_________________
С уважением, Сергей


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 26 сен 2005 17:36 
Не в сети
Постоянный
Аватара пользователя

Зарегистрирован: 02 сен 2005 22:34
Сообщения: 98
Откуда: Питер
А как посоветуеш мне найти путь в 3д???

У меня есть холм на каторый видет извилистая тропинка остальное естены настолько отвесны что поним нельзя поднятся... как прописать путь???


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 29 сен 2005 15:25 
Не в сети
Гуру
Аватара пользователя

Зарегистрирован: 03 авг 2004 10:37
Сообщения: 2694
Так и пиши, ставь waypoint1(0,0,0) далее wp2(0,2,2) и что-то вроде этого далее, просто набор точек, между которыми в прямой видимости можно пройти. Можно вообще просто пометить нужные полигоны как проходимые.

Вот ключевые слова для поиска подобных систем:
pathfind map node network
pathfind navigation mesh system

_________________
С уважением, Сергей


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 29 сен 2005 16:28 
Не в сети
Гуру
Аватара пользователя

Зарегистрирован: 03 авг 2004 10:37
Сообщения: 2694
navigation mesh описано в AI Wisdom 1, Game Programming Gems 3.

_________________
С уважением, Сергей


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 29 сен 2005 16:42 
Не в сети
Гуру
Аватара пользователя

Зарегистрирован: 03 авг 2004 10:37
Сообщения: 2694
Во готовая либа - http://www.pathengine.com. Там есть что-то вроде описания, можно что-то выудить.

_________________
С уважением, Сергей


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 29 сен 2005 19:23 
Не в сети
Постоянный
Аватара пользователя

Зарегистрирован: 02 сен 2005 22:34
Сообщения: 98
Откуда: Питер
а без вейпоинтов??? так как пространство у меня будит генерится случайным образом (образно)...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 30 сен 2005 17:04 
Не в сети
Гуру
Аватара пользователя

Зарегистрирован: 03 авг 2004 10:37
Сообщения: 2694
Без waypoint довольно сложная задача. Но принцип один - A*, только пременять его надо к графу. Граф образуется из проходимых полигонов. Например, для простоты можно принять, что можно пройти от от одного полигона к смежному полигону, через центр обеих полигонов и центр смежной линии между полигонами.

_________________
С уважением, Сергей


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 30 сен 2005 19:16 
Не в сети
Постоянный
Аватара пользователя

Зарегистрирован: 02 сен 2005 22:34
Сообщения: 98
Откуда: Питер
лано попробую замутит с полигонами =)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 03 окт 2005 13:42 
Не в сети
Гуру
Аватара пользователя

Зарегистрирован: 03 авг 2004 10:37
Сообщения: 2694
AI Wisdom 1 у меня есть ...

_________________
С уважением, Сергей


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 25 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения

Найти:
Перейти:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB