Методы определения столкновений в играх

**pokibor** · 03.12.2007, 15:45

Здесь обсудим методики обсчета столкновений.

[CCCP] Monster
Пересоздай. А я пока напомню основную проблему, которая станет перед нами при проектировании гонок: обсчёт столкновений. Проблема в том, что уравнение положения каждой точки при перемещении получается таким вот образом:

И, собственно, тут есть три пути: либо честно брать определённый временной промежуток и рассчитывать, в какое время до него произойдёт столкновение; либо всегда рассчитывать конечное положение системы через конкретное достаточно малое время, а потом смотреть на пересечения и из них делать выводы о столкновениях; либо искать третий путь. Вот первая проблема. Думаем.

Ах, да, есть ещё четвёртый путь - скомбинировать первые два. Например, в рамках одного определёного отрезка времени считать движение равномерным. Тогда все члены, связаные с ускорениями, уберутся, и жить станет чуток проще.

P.S. Ой, извиняюсь, забыл над ускорением в последнем уравнении значок вектора поставить. Но перерисовывать неохота. Просто не забывайте, что ускорение - вектор.

**[CCCP] Monster** · 03.12.2007, 17:07

pokibor

Да, все верно. Единственное, не могу поянть, что тебя пугает. Мы ведь можем применить один интересных финт ушами.

При загрузке модели объекта расчитывать обрамляющий параллелепипед. Bounding Box то бишь. И сравнивать сначала его, а потом уже физическую модель. Что это даст? При обработке тех объектов, которые не столкнулись, нужно обработать всего лишь 8 точек для каждого.

Есть еще один финт. Основан на запоминании длины поливинки диагонали бокса. Эта половинка - тоже, что радиус сферы, описанной вокруг модельки. Теперь отсеем те объекты. что не соприкасаются сферами. Оставшиеся посчитаем. А уж посчитать 3-4 одновременно сталкивающихся объекта из оставшихся можно запросто.

**pokibor** · 03.12.2007, 17:20

Цитата:

Сообщение от [CCCP] Monster

При загрузке модели объекта расчитывать обрамляющий параллелепипед. Bounding Box то бишь. И сравнивать сначала его, а потом уже физическую модель. Что это даст? При обработке тех объектов, которые не столкнулись, нужно обработать всего лишь 8 точек для каждого.

Это ясно, спасибо. Меня интересует само решение вопроса об обработке столкновений. Уравненице там ой-ой-ой получается. И, кстати, кто сказал, что у меня нет собственного решения?

Мне интересно послушать, что скажут остальные. Всё-таки тут у нас практика.

Цитата:

Сообщение от [CCCP] Monster

Есть еще один финт. Основан на запоминании длины поливинки диагонали бокса. Эта половинка - тоже, что радиус сферы, описанной вокруг модельки. Теперь отсеем те объекты. что не соприкасаются сферами. Оставшиеся посчитаем. А уж посчитать 3-4 одновременно сталкивающихся объекта из оставшихся можно запросто.

Это всё ясно! Оптимизировать рассчёты можно кучей способов, меня интересует, как их проводить-то будем, неважно насколько оптимизированные! Пусть у нас хоть останутся те линии, с которыми точно есть столкновение - проблема от этого не исчезнет. Время в компьютере, ясное дело, дискретное - стало быть нужно либо фиксированными порциями и двигать машину, проверяя пересечения; либо же решать сложные нелинейные уравнения, чтобы определить момент пересечения.

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

P.S. Кстати, не забывай, что гонки у нас 2D в принципе, а потому давай лучше говорить не о параллелепипедах и сферах, а о прямоугольниках и окружностях, так правильнее будет.

**[CCCP] Monster** · 03.12.2007, 17:32

pokibor

Ааа... Ну тогда тут вот как. Первый способ, дискретно-порциональный, предполагает простую проверку на пересечение геометриии. Второй способ предлагает обнаружить точку пересечения геометрии аналитически. Второй способ очевидно трудоемок. Первый предпочтителен в том случае, когда объект за время игрового цикла не успевает преодолеть расстояние больше чем его линейные размеры. Однако во многих случаях он не достоверен.

Сосбственно я счтаю, что надо юзать аналитический.

**pokibor** · 03.12.2007, 18:07

Цитата:

Сообщение от [CCCP] Monster

Сосбственно я счтаю, что надо юзать аналитический.

Значит, ты за определение момента пересечения одним отрезком другого... Как можно видеть, в таком случае будет система из двух нелинейных уравнений второго порядка. Так вот, проблема тут состоит в том, что решение таких систем всегда должно быть изолировано при своём поске, т.к. на заданом отрезке не должно быть других решений.
Хотя для метода Ньютона, как я понял, достаточно монотонности, но вот с нею-то у нас как раз проблема. Я не могу гарантировать, что такое вот уравненице будет монотонным, а тогда и метод Ньютона не запашет.

И что скажешь по поводу вокселизации?

P.S. И почему я боюсь, что кол-во желающих участвовать поуменьшится от одного вида уравнений?

**[CCCP] Monster** · 03.12.2007, 18:32

pokibor

Один вопрос тока: мы сейчас рассматриваем двумерную модель или техмерную? Плюс, у нас вроде объемы/площади должны пересекаться-то.

А вокселизация в данном случае - это что? Ты хочешь объем представить кучей вокселей?

**pokibor** · 03.12.2007, 18:37

Цитата:

Сообщение от [CCCP] Monster

Один вопрос тока: мы сейчас рассматриваем двумерную модель или техмерную? Плюс, у нас вроде объемы/площади должны пересекаться-то.

Двухмерную для простоты.
Пересечение объёмов - это как раз случай строгой дескретизации времени, то, что ты первым пунктом поставил.
Аналитический же подразумевает проверку, в какой момент времени движущаяся по определёному закону точка пересечёт также, возможно, движущийся по определёному закону отрезок (т.е. столкновение всегда происходит на одной из вершин многоугольника) в случае их сближения, случаем полной параллельности можно пренебречь.

Цитата:

Сообщение от [CCCP] Monster

А вокселизация в данном случае - это что? Ты хочешь объем представить кучей вокселей?

Ты, видимо, не прочитал дополнение к посту...

Цитата:

Сообщение от pokibor

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

**[CCCP] Monster** · 04.12.2007, 00:32

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

Немного теории для общего развития:

http://www.gamedev.ru/articles/?id=30108
http://www.gamedev.ru/articles/?id=30109
http://www.gamedev.ru/articles/?id=30111
http://www.gamedev.ru/articles/?id=70108