Метод определения столкновений CDNR-1

Георгий Мошкин
tmtlib@narod.ru

Файлы к статье:
cdnr1-10.zip (389kb) - exe с ихсодниками метода Collision Detection and Responce - 1 v1.0.

На начальном этапе создания игр часто возникает вопрос о том, как реализовать передвижение игрока по 3D уровню. В этой статье я покажу простой метод, который я разработал для решения этой проблемы. Частично информация об этом методе излагалась в статье "Тайны разработки клона Silent Hill".

Будем считать, что координаты X,Z - это координаты в плоскости пола. Тогда координата Y - это высота. Взглянем на наш уровень сверху с высоты 345, для чего установим туда OpenGL-евскую камеру:

  gluLookAt(0, 345  , 0,
0, 345-1, 0,
1, 0 , 0);

Здесь всё очень просто: мы установили камеру в точку с координатами (X=0, Y=345, Z=0). Из этой точки мы хотим посмотреть на наш уровень. Так как мы смотрим вниз, то точка, в которую мы смотрим, будет меньше на единицу (345 минус 1). И последние три числа - это вектор направления вверх.

Что будет, если посмотреть теперь на уровень с высоты 550? Так как 550>350, то изображение уменьшится. Если же опуститься пониже, то увеличится. Это происходит из-за того, что мы находимся в режиме перспективной проекции.

Попробуем теперь менять высоту таким образом, чтобы постепенно "пройти сквозь уровень". Всё это при виде сверху. Со временем вы увидите, как перед вашим взором проходят различные комнаты, лестницы и т.п.. Но можно проходить сквозь уровень не постепенно, а с некоторым шагом.

Если ваш уровень представляет собой многоэтажное здание, то мы можем выбрать шаг равным количеству этажей. Тогда для каждого этажа у вас будет "вид сверху", который, например, можно сохранить в файл или в 2D массив. Это своеобразная карта каждого этажа уровня при виде сверху.

Стоит отметить, что если выбрать слишком крупный шаг, то у вас могут исчезнуть 2D-карты для некоторых этажей. Поэтому необходимо выбирать шаг, который будет меньше высоты одного этажа. А теперь перейдём к самому интересному. Переключимся в режим параллельного проецирования:

   glOrtho(-KVADR_MAX_X/2, KVADR_MAX_X/2,
-KVADR_MAX_Z/2, KVADR_MAX_Z/2,
my_NEAR, my_FAR);

Смысл данной функции очень прост. Переменные KVADR_MAX_X и KVADR_MAX_Z - это размеры виртуального (воображаемого) квадрата, на который будет производится проецирование. Деление на два и отрицательный знак были введены с той целью, чтобы совместить центр квадрата с центром OpenGL-евских осей координат.

Наряду с размерами квадрата задаётся расстояние до ближайшей (my_NEAR) и самой далёкой (my_FAR) точки по координате Y, коорая будет видна после проецирования. Таким образом задаётся 3D объём, который будет спроецирован на экран. Это можно представить себе следующим образом: из точки my_FAR в направлении к вам движется квадрат размером KVADR_MAX_X на KVADR_MAX_Z. В итоге при своём движении между my_FAR и my_NEAR квадрат очертит собой некоторый 3D объём. Этот объём и будет спроецирован на экран (разумеется, с учётом теста глубины на основе данных Depth Buffer).

Но встаёт вопрос: если уровень большой, то на экране порою сложно уместить его подробную карту (сриншот вида сверху). Можно, конечно, было бы просто напросто увеличить значения KVADR_MAX_X и KVADR_MAX_Y, но при этом на карте исчезают мелкие детали - карта перестаёт быть подробной.

Решить эту проблему очень просто. Вся прелесть параллельного проецирования состоит в том, что при перемещении положения камеры в плоскости X-Z отсутствуют искажения, присущие перспективному проецированию. А это означает, что мы можем сделать много малнеьких скриншотов и объединить их потом в одну большую карту вида сверху. Теоретически мы можем добиться создания карт любой детальности (даже 1000000 x 1000000 при разрешении экрана 640 x 480).

Далее встаёт вопрос: а как использовать эти слои, которые мы получили при фотографировании каждого этажа при виде сверху? Это обычные цветные картинки, можно различить положение столов, стен, лестниц. Но как это использовать на практике? Ответ состоит в том, что нам нужно от обычных скриншотов перейти к скриншотам содержимого z-buffer-а. О том, что содержится в z-buffer-е, вы можете узнать в статье "Тайны разработки клона Silent Hill".

На практике всё выглядит следующим образом: сначала мы загрузили 3D уровень и узнали его протяжённость вдоль координаты Y (насколько высок этот уровень). Для этого я написал функцию FindMinMax:

 function FindMinMax(coord,minmax:integer;Poligoni:PPoligons):single;

Здесь coord нужно приравнять цифре 1 (т.к. X соответствует нулю, Y соответствует единице, Z соответствует двойке). В переменную minmax записываем 0, если хотим узнать минимальную координату (а цифру 1 - для поиска максимальной координаты).

Итак, мы загрузили уровень:

 LoadModel('.\kafe\','model.txt',TestLevel.Poligoni);

Подали в движок столкновений минимальную и максимальную координату уровня по оси Y:

 SetMinMax(FindMinMax(1,0,@TestLevel.Poligoni)+10,
FindMinMax(1,1,@TestLevel.Poligoni)+10);

Обратите внимание, что к минимальной и максимальной координатам я прибавил число 10. Всё дело в том, что нам не нужно делать скриншот ниже пола "в пустоту". А вот над крышей здания скриншот вполне пригодится: вдруг в уровне будет лестница на крышу.

Далее следует цикл, в котором создаётся много-много скриншотов уровня при виде сверху:

 repeat
glClear(GL_COLOR_BUFFER_BIT or GL_DEPTH_BUFFER_BIT);
glLoadIdentity();
BeforeRender;
RenderModel(@TestLevel.poligoni);
until AfterRender;

Чтобы сделать движок более универсальным, я модульно отделил процесс рендеринга от процесса снятия скриншотов. Таким образом, вместо процедуры RenderModel вы можете подставлять процедуру отрисовки уровня из вашего 3D движка.

Процедура BeforeRender после первого запуска обнуляет внутренние переменные цикла и переводит OpenGL в режим параллельного проецирования и устанавливает камеру в нужное место для вида сверху. Цикл repeat-until работает до тех пор, пока AfterRender не выдаст true. Причём эта функция выполняет важную работу - считывает содержимое z-buffer-а после отработки процедуры RenderModel и записывает эти скриншоты в нужный слой.

Обратите внимание на важную вещь: уровень у нас 3D. А массивы с z-buffer-ом 2D. Но мы делаем многослойный проход сквозь уровень. Поэтому у нас имеется целая серия 2D массивов с содержимым Z-Buffer-а при виде сверху. А серия 2D массивов (одномерный массив из 2D массивов) - это в каком-то смысле и есть 3D массив. У этого массива большая размерность в плоскости X-Z. А вот в направлении Y размерность массива мелнькая (всего лишь несколько слоёв). Это связано с тем, что по данным z-buffer-а, содержащихся в 2D массивах, мы будем восстанавливать в далньейшем координату Y. Поэтому слоёв у нас ровно столько, сколько будет достаточно для создания подробной карты уровня (чтобы не оказалось так, что какой-нибудь этаж будет пропущен из-за того, что при создании скриншота его закроет пол следующего этажа).

Далее вызывается функция MakeCollisionCircle:

   MakeCollisionCircle(TestCircle,(KRUG_W-1));

Эта функция создаёт заполняет маленький 2D массивчик (например, 16 на 16), в котором записаны дискретные данные, описывающие кружок для проверки столкновений. В далнейшем этот маленький массивчик мы будем накладывать на огромный массив карты уровня и делать проверки "наезда" кружка на стены, столы и стулья. В каждом элементе массива присутствует рассчитанный заранее "антивектор". Это такой вектор, который позволяет вытолкнуть кружок из препятствия, если препятствие "наехало" в этот элемент.

Так как же функционирует мой метод определения столкновений? Всё очень просто. Для уровня у нас есть несколько подробных карт при виде сверху. Также у нас есть координаты игрока в пространстве. Зная координаты игрока по оси Y мы можем узнать номер "скриншота при виде сверху", который наиболее близко расположен к голове игрока (но обязательно над головой игрока):

   function FindGoodLayer(y:single):integer;

Итак, эта функция выдаёт номер массива, который был снят с высоты, наиболее близкой к Y.В методе важное значение имеет переход от чисел в Z-Buffer-е к координате Y OpenGL. Этот переход осуществляется по простой формуле:

  GoodLayer:=FindGoodLayer(Player_y+5);
CenterDepth:=zAreas[GoodLayer].ZLayer[PlayerCoordInLayerX,
PlayerCoordInLayerZ];
Player_Y:=zAreas[GoodLayer].HEIGHT-CenterDepth*(MY_FAR-MY_NEAR);

Мы нашли лучший слой с 2D массивом, узнали значение Z-buffer в этом слое на том месте, где находится игрок. И третье - это определение координаты по оси Y. Описание перехода между различными координатами есть в статье "Тайны разработки клона Silent Hill".

Как видите, алгоритм оказался очень прост. На этапе загрузки делается подробная карта местности уровня по всему объёму. А во время работы алгоритма мы просто ищем карту, которая ближе всего к голове персонажа. Поэтому мы всегда имеем карту нужного этажа. Этот алгоритм настолько универсален, что возможна реализация передвижений игрока по весьма сложным сценам: с наличием винтовых лестниц, мостов, перегородок. И особенно приятным является то, что алгоритм работает как на закрытых, так и на открытых пространствах.