|
|
|
|
Канал Игры Мечты: «Поиск пути в 3D» |
|
|
|
DIMOSUS.X
 997 EGP
       
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
   |
|
Есть идеи, как сделать красивый поиск пути, на подобие того как это работает в хоумворлд?
Пока использовал прокладку пути по принципу потенциальных полей (вроде так же работает в Х3), смотрится слегка топорно...
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Варсик
 545 EGP
  
Рейтинг канала: 4(81)
Репутация: 117
Сообщения: 4041
Откуда: Москва
Зарегистрирован: 22.12.2002
|
|
А вариант A* для 3д почему не катит?
_________________
WARNING: By reading this post you accept that this post is genius. |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Нужно разбивать пространство на не малое число кубиков. При чем чем меньше корабль, тем на большее число. Еще нужно переразбивать всякий раз, когда происходит перестановка объектов в мире, а учитывая динами, это значит почти постоянно. Еще путь, проложенный алгоритмами типа А* будет смотреться весьма дискретно.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Kann
64 EGP
Рейтинг канала: 3(45)
Репутация: 7
Сообщения: 232
Откуда: Москва
Зарегистрирован: 11.04.2008
|
|
ммм.... вопрос такой, зачем это в космосе ? если конечно пространство не 2д...
|
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Ну масшта бы весьма условны, так что препятствий для шипа будет предостаточно.
Вот задумался - я кривова-то реализовал этот метод потенциальных полей. Нужно будет попробовать плавно наращивать силу отталкивания, по мере сближения с объектом, начиная с некой, установленной для объекта дистанции.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Kann
64 EGP
Рейтинг канала: 3(45)
Репутация: 7
Сообщения: 232
Откуда: Москва
Зарегистрирован: 11.04.2008
|
|
если просто препятствия, без лабиринтов то советую копать в сторону Steering behaviors, дает по моему отличные результаты для космоса, у меня ИИ мобов именно на нем построен
добавлено спустя 12 минут:
http://www.red3d.com/cwr/steer/Obstacle.html
Последний раз редактировалось: Kann (11:19 18-04-2011), всего редактировалось 1 раз |
|
|
|
AlexYar
 1916 EGP
       
Рейтинг канала: 3(46)
Репутация: 325
Сообщения: 32752
Зарегистрирован: 26.10.2003
|
|
| DIMOSUS.X : |
на подобие того как это работает в хоумворлд?
|
А как работает в хоумворд? И поиск какого пути? Откуда и куда?
| DIMOSUS.X : |
|
Пока использовал прокладку пути по принципу потенциальных полей (вроде так же работает в Х3)
|
В х3 поисков пути в принципе не существует (в пределах одного сектора). Просто вычисляется вектор на цель, корабль разворачивается на неё и полетел. Вот и весь поиск 
|
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
| Kann : |
|
А как работает в хоумворд? И поиск какого пути? Откуда и куда?
|
Если кораблю (истребителю) попадается на пути астероид или другой корабль, то он обогнет его по плавной кривой.
| AlexYar : |
|
В х3 поисков пути в принципе не существует (в пределах одного сектора). Просто вычисляется вектор на цель, корабль разворачивается на неё и полетел. Вот и весь поиск
|
Ну не так выразился — облет препятствий
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
AlexYar
1916 EGP
Рейтинг канала: 3(46)
Репутация: 325
Сообщения: 32752
Зарегистрирован: 26.10.2003
|
|
| DIMOSUS.X : |
|
облет препятствий
|
Ну это другое дело В иксах время от времени проверяется "возможность столкновения", суть которой проста до безобразия (и тормознутости) - идёт перебор всех материальных объектов сектора с последующей проверкой дистанции до них. Если дистанция меньше или равна половины размера объекта плюс "запас" (некоторое расстояние, которое корабль может пролететь по инерции на текущей скорости), то команда на полёт у корабля будет прервана, и будет запущена процедура ухода от столкновения (она просто выводит корабль за пределы "сферы" объекта по ближайшему вектору от центра препятствия к краю его "сферы").
Если корабль не по касательной к объекту летит, а "в лоб", то лихорадить его в попытке ухода от столкновения может долго (так как после вылета за "пределы сферы" он опять ляжет на старый курс и снова влетит в "сферу" препятствия, потом опять будет уклоняться, и опять и снова и т.д. и т.п.).
Чем манёвреннее корабль - тем сильнее будет его лихорадить (острее зигзаги будет нарезать).
Вобщем, всё печально в иксах.. 
|
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
| AlexYar : |
|
идёт перебор всех материальных объектов сектора
|
Что, даже нет оптимизации деревьями? О_о
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
AlexYar
1916 EGP
Рейтинг канала: 3(46)
Репутация: 325
Сообщения: 32752
Зарегистрирован: 26.10.2003
|
|
| DIMOSUS.X : |
|
нет оптимизации деревьями?
|
Есть "оптимизация" сетой  Чем быстрее сета - тем больше циклов проверок выбрасывается. Соот-но - больше шансов на то, что кораблик отвернуть не успеет.
|
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Жесткие парни работают в егософте...
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Kann
64 EGP
Рейтинг канала: 3(45)
Репутация: 7
Сообщения: 232
Откуда: Москва
Зарегистрирован: 11.04.2008
|
|
да ладно, не чего такого страшного, если объекты все в массиве, и скорость измерения дистанции динамически меняется в зависимости от дальности до объекта, то не так уж это и затратно, у себя я так проверяю порядка тысячи объектов, и затраты очень незначительны, менее 1мс, хотя конечно лучше всего использовать физику и триггеры на коллизию, но это не всегда удобно.
|
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Тысяча объектов, проверит тысячу объектов — сколько получится? 
добавлено спустя 52 минуты:
Небольшой тест, 3000 объектов, мир — куб с ребром 2000, попадание объектов в сферу диаметром 10.
- поиска перебором — 0,2 мс
- поиск при помощи восьмеричных деревьев — 0,04 мс
Вот только построение дерева занимает 7 мс.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом.
Последний раз редактировалось: DIMOSUS.X (01:13 20-04-2011), всего редактировалось 1 раз |
|
|
|
Kann
64 EGP
Рейтинг канала: 3(45)
Репутация: 7
Сообщения: 232
Откуда: Москва
Зарегистрирован: 11.04.2008
|
|
| DIMOSUS.X : |
Тысяча объектов, проверит тысячу объектов — сколько получится?
|
ну так то да, но в Х3 нету такого количества объектов в секторе, а у меня проверка идет только на дальность до игрока с целью скалирования размеров, между собой объекты используют проверку на коллизию с невидимой геометрией (сферический триггер) отсюда затраты вообще минимальны, сервер без вопросов держит 1000 мобов
|
|
|
|
Снуч
941 EGP
Рейтинг канала: 1(9)
Репутация: 232
Сообщения: 2696
Откуда: Ракслатенон
Зарегистрирован: 09.08.2005
|
|
| DIMOSUS.X : |
|
метод потенциальных полей.
|
интересно: а в чём суть твоей реализации? Потенциал чего с чем сравнивается и в каком виде?
|
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Ни чего не сравнивается, просто от ветора на цель отнимается сумма векторов препядствий (последние всегда направлены от препчтствий к кораблю).
Нужно будет доработать, что бы вектор поля препятствия нарастал по мере прибближения к нему. Плюс добавить выход из локальных минимумов. Тогда может и начнет у меня облетать по красивой дуге
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Снуч
941 EGP
Рейтинг канала: 1(9)
Репутация: 232
Сообщения: 2696
Откуда: Ракслатенон
Зарегистрирован: 09.08.2005
|
|
а, а я-то подумал, что рассчитывается локальное потенциальное поле, как на карте топологической, соответственно при возрастании локального градиента потенциального поля происходит огибание.
|
|
|
|
|
|
|
|
|
Канал Игры Мечты: «Поиск пути в 3D» |
|
|
