29 ноября 2010

План

В первой части я, возможно, создал два вводящих в заблуждение впечатления. Во-первых, вы могли подумать, что я опытный программист, показывающий вам лучший способ реализации простого мира блоков. Отнюдь не так! У меня большой опыт программирования систем, но мой опыт работы с 3d графикой во многом ограничен тем, что Вы уже видели. А мой опыт программирования игр состоит из личных проектов, сделанных более 30 лет назад. На этом проекте я буду учиться по ходу дела.

Во-вторых, вы могли подумать, что я просто хочу создать Minecraft с некоторыми незначительными вариациями. Это тоже неправда. Как написано на главной странице, я хочу создать "виртуальный мир от равного к равному, поддерживающий реальную среду программирования". Я выбрал кубический мир для реализации в качестве первого прохода, потому что это легко, и потому что Minecraft так популярен. Это также самый простой модифицируемый пользователем мир, который я могу придумать. Как только вы сможете добавлять и удалять блоки, вы сможете создавать всевозможные вещи. Минимальное количество кода, чтобы сделать это с любым другим миром (например, Second Life) было бы огромным.

Мой план состоит в том, чтобы быстро собрать воедино основные компоненты общего мира, с кубическим ландшафтом, своего рода аватарами и простым сервером. Затем я вернусь, пересмотрю и расширю все элементы, возможно, много раз. Я не ожидаю, что это будет короткий проект. Я постараюсь поддерживать баланс между кучей инфраструктуры и стабильностью и привлекательностью демо. Надеюсь, что хотя бы некоторые из вас последуют за мной, попробуют демо и добавят свои комментарии.

Передвижение

В конце первой части вы были бесплотным глазом, плывущим в космосе, способным оценить только великолепный пейзаж кубов... Теперь пришло время исследовать. Вам нужна способность двигаться.

В действительно хорошей игре из списка A мы бы смоделировали руки и ноги аватара, и прикрепили бы все это к физическому движку. Таким образом, мы бы точно знали, где на твоем теле тебя подстрелили. А когда граната взорвется рядом с тобой, мы бросим твое тело по хорошей траектории, вверх тормашками, в стену, и твое тело убедительно рассыплется.

В моем простом мире аватар - это фигура в виде палки и всегда стоит прямо, так что мы ничего подобного не делаем. Вместо этого, у нас просто есть клавиши движения, чтобы контролировать вашу позицию. Мы начинаем отсчет времени, когда вы нажимаете на клавишу. В каждом цикле обновления мы получаем продолжительность с момента нажатия клавиши (или последнего цикла обновления) и умножаем ее на вектор движения в этом направлении. Таким образом, если Вы движетесь вперед по вектору X (1, 0, 0) на 16.6 миллисекунд (время обновления 60 Гц дисплея) со скоростью 5 единиц в секунду, то мы добавляем в вектор (1,0,0)*5*16.6/1000 = (0.083, 0, 0). Мы делаем это для всех клавиш движения, нажатых в то время. Добавляем все векторы движения в старую позицию и получаем новую позицию.

Забавно, но у меня была действительно неприятная ошибка в этом году, когда я впервые делал 3d игру. Я использовал функцию Windows GetTickCount в качестве таймера. Насколько мне известно, разрешение этого таймера составляет всего 15 миллисекунд. Мой дисплей работал на частоте 72hz, что составляет 13.8 миллисекунд на обновление. Движение работало, но было немного грубовато. Это выглядело точно так же, как если бы я не всегда успевал рендерить кадр вовремя. Я потратил часы, пытаясь понять, почему теряется кадр, но проблема была в таймере. Время от времени я получал два кадра между тиками таймера, создавая впечатление, что кадр был потерян (потому что положение аватара не менялось). В этом демо я использую таймер с разрешением 0.1 миллисекунды.

Нам нужна гравитация, чтобы вы могли падать с вещей. Мы реализуем это с помощью вектора импульса, который прикладывается вместе с векторами движения при каждом обновлении экрана. Мы получаем гравитацию, добавляя немного нисходящего импульса при каждом обновлении. Нажатие клавиши пробел, которое заставляет вас прыгать, реализуется простым добавлением некоторого вертикального импульса. Это подбрасывает вас в воздух, а клавиши движения позволяют двигаться вперед. Затем гравитация тянет вас вниз к вершине верхнего куба, давая хороший маленький прыжок вверх (Рис. 2).

Чтобы закончить движение, нужно только обнаружить столкновения с блоками в мире. Учитывая, что Octree хранит все мои кубики, я подумал, что это будет достаточно просто. Просто возьмите ограничивающий блок (bounding box) вокруг старого и нового положения аватара, и проверьте все кубики, которые касаются этого блока. Если любой куб в этом объеме не воздух, аватар попал во что-то твердое. Так как он движется на таком коротком расстоянии при каждом обновлении, я решил, что просто отменю это движение, и все. Оказалось, что это не так просто.

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

Во-вторых, когда я добавил гравитации, аватар застрял сразу же, как только он упал на землю. Я подумал, что это, должно быть, какой-то странный баг, и на минуту зашел в тупик. Что может помешать ему двигаться, когда код так прост? Оказалось, что гравитационный вектор всегда пытается протащить аватар через пол. Так как правило гласило: "если вы попали в блок, остановитесь", он не мог никуда двигаться.

Так что оказалось, что мне все-таки нужно настоящее обнаружение столкновений. Какая досада! Тут есть целая книга на эту тему!

Обнаружение столкновений

Я не уверен, насколько точно игры из списка A в наши дни моделируют аватары и другие движущиеся объекты. Играя с Half-Life 2, Эпизод один, в главе "Прямое вмешательство", я могу бросать мертвых охранников гравитационной пушкой и смотреть, как хорошо это делается.

Тело охранника (в учебниках, которые я читал, его называют "рагдолл") не очень-то проверяется на само себя. Можно просунуть ему руку через кишки или скрутить ноги. Но они действительно проверяют на консоль в комнате, и игровой движок делает действительно хорошую работу по обнаружению столкновений. Хотя довольно легко получить ситуацию, когда охранник парит на пару дюймов выше консоли, сложно заставить игру сделать то, что вы видите на рисунке 3 - просунуть руку прямо через консоль. Интересно, какой алгоритм они используют, который может быть настолько хорош в 99% случаев, но все равно допустить такую грубую ошибку.

Рис. 3: Баг в А-игре

В World of Warcraft, с другой стороны, похоже, что аватар проверяется на простую ограничивающую форму, и легко заставить аватар засунуть руку в стену или встать на растение. См. рис. 4. Конечно, держать вас подальше от растений будет довольно сложно в некоторых частях мира!

Рис. 4: Какой столб? Какое растение?

Рис. 5: Сфера, двигающаяся среди треугольников

После небольшого гуглинга я нашел запись о определении столкновений от Каспера Фауэрби (PDF), которая выглядела не так уж и сложно для реализации. В ней есть все подробности, в том числе школьная математика и примеры кода. Что он делает, так это обертывает движущийся объект в эллипсоид, затем масштабирует пространство координат мира так, чтобы оно стало сферой с радиусом=1. Остальной мир искажен, но это не имеет значения. Он вычисляет точки пересечения в искаженном мире, а затем переносит их обратно в реальный мир, инвертируя масштабирование.

Затем он тестирует сферу против всех треугольников в сцене, как показано на рисунке 5. Все его тесты возвращают расстояние по вектору движения до тех пор, пока сфера не попадёт в треугольник. Он берет самое близкое попадание и использует его как точку остановки. С помощью точки попадания и нормали плоскости, в которую мы попали, он может рассчитать величину скольжения (подробнее об этом ниже).

Реализация этой задачи проста и будет работать, когда мы уйдем от кубических пейзажей. Я начал с этого, как показано на рисунке 6. К сожалению, нельзя просто пересечь движущуюся сферу с гранями куба. Можно получить ситуацию, как на рисунке 7, когда передняя кромка сферы (самая нижняя точка) не касается ни одной из граней куба, а тело сферы касается. Поэтому необходимо протестировать и края кубов. Это остановит сферу в воздухе, как показано на рисунке 8.

Рис. 6: Сфера, соприкасающаяся со стороной куба	Рис. 7: Сфера, промахнувшаяся мимо граней	Рис. 8: Сфера, соприкасающаяся с гранью

Потом я понял, что это бессмысленно в моем нынешнем мире. Если бы у меня был блочный аватар в стиле Minecraft, эллипсоид в виде ограничивающей формы не очень хорош. Ноги будут торчать внизу по бокам. Поэтому здесь я пишу код, чтобы остановить падающую сферу на краю куба, и это будет выглядеть глупо с настоящим аватаром. Она остановится в воздухе, частично по краю куба. Его ноги будут прилипать к краю куба. С точки зрения мира блоков, все это неправильно. Он должен либо стоять на верхнем крае блока, либо падать на следующий блок.

Итак, вернемся к миру блоков. Мы создаем ограничивающий блок вокруг аватара, и, используя ту же самую логику, что и со сферой, находим первую точку на пути движения, которая попадает в куб. (см. Рис. 9) Как и прежде, лицевые грани все еще являются проблемой. На Рис. 10 путь все еще попадает в куб, даже несмотря на то, что центральная точка блока находится за краем грани куба, когда блок попадает в него.

Рис. 9: Нашли первый куб, с которым мы столкнулись	Рис. 10: Осторожнее с этими углами!

Если вы реализуете что-то подобное, есть один тонкий момент, который очень важен. Когда мы проверяем луч движения относительно плоскости, мы часто будем иметь дело с тем, что начальная точка вписывается в плоскость, делая расстояние равным нулю. Это потому, что мы останавливаемся на плоскости, когда попадаем в нее, и движемся вдоль нее, когда скользим. Если мы просто используем расстояние, то не знаем, движемся ли мы в плоскость или нет. Так что, кроме того, мы должны проверить, направлена ли плоскость в том же направлении, что и луч. Если это так, то мы выходим из этой плоскости и не проверяем ее на пересечение.

Если вы пропустите этот тест, вы можете получить все виды странного поведения, например, аватар застрянет в стенах или внезапно ударится о вертикальные плоскости кубов в полу. Я думал, что это всего лишь оптимизация, и что я могу сократить количество проверяемых плоскостей, используя флаги видимости, которые я ставлю на все кубы в первой части. Однако этого недостаточно. Только удаляя плоскости, обращенные в противоположную от луча движения сторону, можно избежать этих поддельных пересечений.

В общем, у вас проблема с точностью с плавающей точкой. Если по какой-то причине аватар наступает на противоположную сторону стены (которая имеет нулевую толщину, так что это легко), то эта стена больше не будет рассматриваться как препятствие для движения. Ваш аватар прорвется сквозь стену и продолжит движение к следующему препятствию. Если эта "стена" на самом деле является полом, то она может пробиться сквозь дно мира. Я видел это в продакшн-играх (таких как World of Warcraft), так что это определенно то, на что вам стоит обратить внимание.

Скольжение вдоль стены

Скольжение по стене, когда ты касаешься ее, кажется (мне, во всяком случае), чем-то сложным. На самом деле, это легко. На Рисунке 11 мы начинаем в точке A, перемещаясь в точку B. По пути мы попадаем в стену, и конечное положение от обнаружения столкновения - H. Чтобы скользить, мы просто берем вектор из H в B (ту точку, в которую мы хотели, но не попали), и проецируем его обратно на плоскость стены, которую мы ударили. Плоскость представлена точкой попадания и нормалью N. В расчетах вам даже не понадобится точка столкновения. Просто умножьте расстояние, которое еще нужно пройти к стене, на нормаль, и вычтите из точки B. В результате вы получите точку S, которая является вашей позицией после скольжения.

Важно отметить, что переход от H к S является новым ходом для аватара, и должен быть проверен на столкновения заново. Например, на рисунке 11 вы перемещаетесь в угол по диагонали от A до B. Первое попадание происходит в H, а прогнозируемое положение скольжения приводит вас в S1. Второе движение из H в S1 приводит к еще одному попаданию и скольжению в S2. Таким образом, обнаружение столкновений продолжается до тех пор, пока вы не перестанете сталкиваться.

Приятным в этом алгоритме скольжения является то, что если вы столкнетесь со стеной под углом 90 градусов, вы вообще не будете скользить. На рисунке 13 показаны те же расчеты при столкновении под углом 90 градусов. Вычисления для скольжения проецируют расстояние от H до B на стену, но эта проекция находится в том месте, куда мы попали, так как вектор проекции находится под прямым углом к плоскости. Это полезно, когда гравитация прижимает аватар к полу. Мы не хотим скользить в этом случае.

Рис. 11: Скольжение вдоль стены	Рис. 12: Столкновение с углом	Рис. 13: Столкновение перпендикулярно плоскости не вызывает скольжения

Камера

В играх есть как минимум два режима работы с мышью. В режиме "шутер", также используемом Minecraft, перемещение мыши поворачивает голову. Нажмите клавишу вперед ("w") и вы будете двигаться в том направлении, в котором вы смотрите. В режиме "MMO", например, в World of Warcraft, на экране находится обычный курсор. Вы можете взаимодействовать с инструментами, кнопками и меню на экране. Чтобы повернуть голову, нужно нажать и перетащить мышь.

Видение мира отображается из положения "глаз" или "камера". Эти два режима также отличаются друг от друга. В режиме "шутер" камера находится в центре вашей головы. В режиме MMO она обычно находится над и за вашим аватаром. Это может вызвать проблемы. Перемещение камеры может привести к удару о стену или пол. Это не только плохо выглядит (см. Рис. 14), но и может блокировать Ваш взгляд на себя или на оппонентов. Чтобы это исправить, мы также должны сделать некоторые обнаружения столкновений. Так как мы просто пытаемся увидеть, а не двигаться, достаточно проверить, есть ли блоки вдоль луча от головы до камеры. Если да, то мы вытягиваем расстояние от камеры до первой точки столкновения (временно).

Рис. 14: Камена не должна попадать в стену

Это немного раздражает, так как если вы отойдете назад к стене, положение камеры будет становиться все ближе и ближе к вашей голове. Но так как альтернативой является блокировка вашего вида стеной, у нас нет особого выбора.

В демо можно нажать F3 для переключения между режимом "шутер" и режимом MMO. В режиме "шутер" на экране появится крестик. Когда вы находитесь в режиме MMO, у вас появится аватар и стрелка. Вы можете видеть свое лицо, нажимая и перетаскивая мышь, чтобы вращать вид вокруг головы. Все клавиши перемещения одинаковы в режиме шутера или MMO.

Наконец, вы заметите границу блока на близлежащих кварталах, на которую смотрите. Это для добавления и удаления блоков. В следующей части...

Демо

Новое демо - The Part 2 Demo. Оно было протестировано на Windows 7, 32-bit и 64-bit, и Windows XP, 32-bit. Мы не делаем здесь ничего амбициозного с графикой, так что если вы можете запустить любую 3D игру, вы сможете его запустить. Если вы получите сообщение об ошибке о необходимости "d3dx9_42.dll", вам нужно обновить вашу версию DirectX.

Во второй части пользовательский интерфейс имеет гораздо больше функций:

• "W" и стрелка вверх - движение вперед.
• "S" и стрелка вниз - движение назад.
• "А" - движение влево.
• "D" - движение вправо.
• пробел - прыжок при ходьбе.
• Стрелка влево - поворот налево.
• Стрелка вправо - поворот направо.
• пробел и клавиша Page Up - движение вверх во время полета.
• "X" и клавиша Page Down - движение вниз во время полета.
• Клавиша Home - переключение в режим полета.
• F1 - запись статистики в журнал ошибок.
• F2 - снимок экрана.
• F3 - переключение между режимом "шутер" и режимом "MMO".
• Нажмите Alt-Enter для переключения между оконным и полноэкранным режимами.
• Нажмите ESC, чтобы выйти из программы.

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

В режиме "MMO" (стрелка) перемещение мыши просто перемещает курсор. При желании можно изменить размер окна. Перетащите мышь, чтобы повернуть голову. Нажмите обе кнопки мыши вместе, чтобы ходить или лететь в направлении курсора. Клавиши перемещения все еще работают в режиме MMO.

Вы начнете в режиме " шутер", в воздухе над пейзажем, и в режиме "полет". Немного полетайте, затем нажмите кнопку " Home ", чтобы остановить полет и начать падать. Нажмите "F3", чтобы увидеть свой аватар.

Заметка программистам: Клавиша F1 записывает графические данные в errrors.txt лог-файл. Тем не менее, версия, которую я выпустил, использует "default presentation interval" в DirectX, что означает, что вы не получите от него более 60 кадров в секунду (или сколько ваш дисплей поддерживает). Чтобы получить реальное время, найдите и раскоментируйте #define GRAPHICS_TIMING в файле Framework/DXFramework.cpp, который переключится на "immediate presentation interval", который должен выводить графику, не дожидаясь обновления экрана.

Исходники

Скачайте архив The Part 2 Source с C++ кодом, дорожную карту к исходникам и каталог сборки. Сюда входит исполняемая демо-версия и необходимые файлы.