Доброго времени суток
предположим, пишу 3д-приложение. Кто-нибудь знает самый-самый хороший алгоритм взаимодействия с окружающим миром (управляемый юзверем чудик должен натыкаться на стены, взбираться по холмам, натыкаться на предметы и т.д.). Заранее прошу прощения у модераторов - хотел было запихнуть в "С++ Мультимдеа", но тут более к месту... наверное.
Пока у меня все примитивно - холмов нет ваообще, а стенки все прямые. Сохранил координаты всех углов и общим уравнением прямой проверяю расстояние игрока до стены(от точки игрока отходит прямая, вторая ее точка расположена на линии взгляда и вот уже вторая прямая). Но это не универсальный алгоритм. Подскажите, а...

Модератор: тема перемещена из раздела "Алгоритмы"

Если у тебя просто ящик, в котором находится игрок - тут всё просто. Но если стенок много (лабиринт, типа), нужно определять в каком коридоре находится игрок и действовать соответственно. Конкретный исходник ты сможешь написать сам, скорее всего никто тебе его не напишет.

З.Ы. для более сложных случаев взаимодействия, есть физические библиотеки. Их много, есть бесплатные: Newton, Tokamak, ODE.

Для начала нужно разбивать уровень на блоки и обрабатывать физические взаимодействия с игроком в том блоке, где он находится. Для простых взаимодействий(например: подобрать предмет или упереться в предмет) лучше использовать алгоритмы с BoundingBox'ом. Вообщем - то все взаимодействия можно так обрабатывать, но если тебе нужно например полигональное попадание, то тут малость сложнее: придётся обрабатывать ещё и полигоны моделей, после того, как зафиксировано их взаимодействие BoundingBox'ами.

есть что то полезное в Директ Х 9 СДК - в примерах , там есть пример проверки выбора треугольника из модели мышкой ... посмотри по моему там всё что нужно ...

А можете поподробнее, насчет BoundingBoxов и если можно с примером на Delphi и OpenGL...

О чёрт , перепутал тему ! извините ... хотя этот пример с выбором полигона в ДХ СДК, всё равно интересен и с точки зрения проверки столкновений ...

ещё читал про отсечение невидимых полигонов методом БСП (бинари спэйс партишнг ) там что то было сказано про то , что этот алгоритм не только отсекает нивидимые полигоны , облегчая жизнь видеокарте но и каким то магическим образом помогает при проверке столкновений , если кто знает объясните может принцип действия ?

Если мир разложен по BSP, получается меньше проверок на столкновение. Сама проверка происходит по тем же алгоритмам.

ааа ! понял !

но как я понял мир один раз разкладывается на дерево , во время инициализации ? если да то мир поменяется и дерево заново строить надо ?

Насколько я знаю дерево строится один раз, при компиляции карты (в редакторе карт). В процессе игры дерево не перестраивается.

ну это если карта не меняется (халф лайф , дум 3 и т.п. хлам ) , сейчас вообще модно всё делать красиво и без вкуса , а если как в Red Faction ? там же карта перестраивается сама ( ну ладно при помощи встроенного редактора - игрока с динамитом ) там же всё меняется - кол-во и положение полигонов относительно друг друга , в таком случае дерево не может быть статичным , или я не прав ?

Никто не засталяет строить дерево для абсолютно всех объектов в сцене.

Цитата(DENNN @ 4.10.2005, 08:45)

Никто не засталяет строить дерево для абсолютно всех объектов в сцене.

Т.е. мы можем разбить свою игровую модель на статичное окружение (карта и т.п.) и на динамические объекты (модельки игроков, снарядов, бочек, кирпичей и т.п.). Сие есть классическая BSP-реализация игровой карты.

т.е если на карте ничего нет статичного то и дерево не построить , как же тогда поступили ребята , Red faction , делавшие ? есть ещё какие то способы ?

можно еще в этой теме вопрос задать - новую не хочется создавать?
тоже не могу понять основ взаимодействия, а хочется.
могу привести для примера игру
Rally pro contest на сайте mophun.com
там машина едет по дороге и может заезжать на обочины, при этой ее, естественно, наклоняет.
вопрос:
как понять что машина движется по трассе а не по обочине?
машина наклоняется в соответствии с наклоном трассы. а как это делается?
в 3d движке нет больших возможностей, в основном, простой обсчет матриц.
может кто-нибудь по простому объяснить?
заранее спасибо!

Цитата(Dubinsky @ 4.10.2005, 17:04)

т.е если на карте ничего нет статичного то и дерево не построить , как же тогда поступили ребята , Red faction , делавшие ? есть ещё какие то способы ?

Сделали BSP-уровень с "выемками", которые заполнили "разрушаемыми" затычками - в виде колонн, отдельных стенок, камней; бОльшая часть уровня - статична.

Цитата(Dmil @ 4.10.2005, 19:10)

как понять что машина движется по трассе а не по обочине? машина наклоняется в соответствии с наклоном трассы. а как это делается?

Делается ray scene query - по двум известным координатам (X;Y) вычисляется координата Z, являющаяся пересечением вертикальной линии с плоскостью трассы. Этим мы получаем положение каждого конкретного колеса, дальше остаётся только наклонить машину по законам физики .

Цитата(mr @ 5.10.2005, 09:22)

дальше остаётся только наклонить машину по законам физики

Если быть педентичным, то нужно еще сделать тест collision-detection с корпусом и предметами, которые могут быть между колесами.

Пардон, а как узнать что этот кусок сетки - трасса, а не обочина?
и как узнать плоскость трассы?
ведь исходно есть:
3d сетка - земля
3d сетка - машина

часть сетки земли является трассой, которая имеет изгибы по вертикали и горизонтали.

просто сам писал подобную вещь, но делал сам и движок отбражения сетки, поэтому знал откуда взять координаты.

а если есть просто сетка и просто команда отобразить, как узнать-то все необходимые данные?
или надо еще к сетке дополнительно таблицу иметь с описанием трассы?

Цитата(Dmil @ 4.10.2005, 19:10)

машина наклоняется в соответствии с наклоном трассы. а как это делается?

На полигоны обочины под колесом в текущий момент времени опускается перпендикуляр и машина наклоняется в соотв. с этим перпендикуляром. Вроде так.

Цитата(Dmil @ 4.10.2005, 19:10)

в 3d движке нет больших возможностей, в основном, простой обсчет матриц.

На досуге зайдите на www.artificialstudios.com и посмотрите список фич. Или на http://www.ogre3d.org - чистый 3D движок.

хммм в Red faction рушится ВСЁ ! нет статичных "стен" ,есть очень мало неломаемых маленьких статичных объектов , необходимых для прохождения типа лифт , лестница и т.п. которые скорее не ломаются потому , что надо как то пройти игру , а так , весь уровень можно взорвать и наделать не выемок а новые проходы где хочешь , как хочешь и в любой конфигурации , как высчитывать коллизии(а также оптимизировать и срезать ненужные полигоны ) в таком случае ? есть какой то метод типа динамических деревьев или т.п. что можно будет изменять по ходу игрового процесса ?

Цитата(Dmil @ 5.10.2005, 13:06)

или надо еще к сетке дополнительно таблицу иметь с описанием трассы?

Естественно

Цитата(Dubinsky @ 5.10.2005, 13:23)

хммм в Red faction рушится ВСЁ ! нет статичных "стен" ,есть очень мало неломаемых маленьких статичных объектов

неправда.
Уровень "офис" практически неразрушаемый, а на всех остальных ур-нях большинство стенок - статичные, чтобы не ломать игроку кайф от перегрузки процессора.

Цитата(Dubinsky @ 5.10.2005, 13:23)

как хочешь и в любой конфигурации , как высчитывать коллизии(а также оптимизировать и срезать ненужные полигоны ) в таком случае ? есть какой то метод типа динамических деревьев или т.п. что можно будет изменять по ходу игрового процесса ?

Есть физические движки, их много, но если хочется ВЕСЬ уровень сделать одним большим физическим телом - придётся много кэшировать, много упрощать, на многое забивать, и в итоге не получится никакого выигрыша по сравнению с подходом а-ля Red Faction. Пока что компы слишком слабые. Сомнения ? Посмотри самые сложные демки для любого физ. движка - какие тормоза при большом кол-ве одновременно обсчитываемых коллизий, не говоря уже о тормозах при наличии разрушаемых объектов.

хорошо , давайте с самого начала ... как БСП дерево помогает при расчёте коллизий ?как его строить ?

Dubinsky
Google не пробовали? http://www.google.com/search?hl=en&q=BSP+%...%B5%D0%B2%D0%BE