Dream2D: Двумерная мечта

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

Для чего мне генерация локаций по графу? Всё очень просто. Граф представляет собой готовые вэйпоинты для ботов, чтобы они могли спокойно перемещаться по локации и находить путь в любую точку, а не тупо болтаться в вакууме, как сейчас. :) Да и вообще, он определяет структуру локации, которую я смогу разными способами варьировать. Теперь генерация локации сводится к генерации планарного графа с окружностями в вершинах. Это уже более сложная задача — пожалуй, одна из самых сложных в проекте. 

Сегодня написал генерацию локации по планарному графу. Это первый шаг к автоматической генерации локаций. Поясню.

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

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

Кстати, для связного планарного графа верна любопытная формула Эйлера: число вершин — число рёбер + число граней (контуров) = 2. Ещё один интересный факт о плоских графах — теорема о четырёх цветах: грани графа можно раскрасить четырьмя цветами так, что соседние грани не будут иметь один и тот же цвет (соседние — имеющие общее ребро). Но это так, лирическое отступление в красоту теории. :)

По контурам графа мы и определяем контуры стенок локации. Нам нужно только раздвинуть их, чтобы между ними образовалось пространство для полётов. :) Я склеиваю стенки из общих касательных к вэйпоинтам, соединённым рёбрами. В следующем посте — демка, в которой виден результат.

Этот блог может быть интересен в основном таким же, как я, разработчикам инди-игр, а наиболее ценная информация — это чужие ошибки (с тем, чтобы их не повторять). Сейчас я хочу немного поговорить об общих принципах программирования и о каркасе игрового приложения, к которому я на данный момент пришёл для проекта Dream, пройдя довольно тернистый путь.

Конечно, при написании небольшой простой игры, которую вы не планируете изменять или расширять, строгая организация кода не очень-то и нужна. Во всех остальных случаях это жизненно необходимо. Прежде всего следует правильно выделить сущности, т.е. воспользоваться принципами объектно-ориентированного программирования. Очень полезно отделить друг от друга собственно игровой мир (некоторую модель), его отображение (вывод) и управление им (ввод). В игровом мире целесообразно выделить сущности различных игровых объектов, близких по своему поведению. Здесь можно использовать наследование, но не стоит слишком увлекаться: это запутывает код. В некоторых случаях проще скопировать код объекта и внести туда необходимые изменения. На Python, на мой взгляд, не стоит выделять низкоуровневые объекты, такие как вектор. Во-первых, это невероятно замедляет код, а во-вторых — передача таких объектов по ссылке часто неудобна (в Python все объекты — это ссылки, т.е. присваивание a=b ведёт к тому, что a и b ссылаются на один и тот же объект). Вектор проще всего представлять в виде двух отдельных вещественных чисел.

У меня в процессе игры игровой мир (объект game) переходит из одного состояния в другое, получая на каждом шаге управление для каждого игрока. Текущее состояние игрового мира отображается на экране, например, в зависимости от положения камеры. Камера — это отдельная сущность: она может быть привязана к игроку или перемещаться по каким-то своим законам. Опрос клавиатуры и мышки осуществляет главное приложение (server). Он создаёт объект game и запускает основной цикл, в котором выполняется следующее:

• происходит обработка событий мыши и клавиатуры, проверяется состояние клавиш
• формируется объект control (управление) и вызывается метод game.update(delta_t,control,eventlist), который переводит игровой мир в следующее состояние с шагом времени delta_t, управлением control, списком событий eventlist (о событиях позже)
• вызывается метод camera.update, который обновляет положение камеры (оно тоже может управляться игроком)
• происходит отрисовка в буфер (сейчас это выполняет объект camera, но думаю выделить в отдельную сущность)
• происходит смена буферов OpenGL, при которой новое изображение попадает на экран
• происходит задержка, доводящая общее время такта до 1/60 секунды (типичная частота обновления на ЖК-мониторах)

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

Объект game содержит всю начинку игры. Как правило он состоит из набора объектов игрового мира и должен обрабатывать все взаимодействия между ними. Он вызывает метод update каждого объекта, обрабатывает столкновения, создаёт новые объекты и удаляет отработавшие. Однако, не каждую из этих операций можно выполнять где угодно. Должна быть строго определна последовательность переключения игрового мира в новое корректное состояние (некорректное состояние — это, например, объект, застрявший в стене). Здесь на помощь приходит событийно-ориентированное программирование. Когда в игре что-то происходит (а это что-то может обнаружиться при выполнении метода game.update или метода update одного из игровых объектов), мы просто добавляем событие в очередь. Это событие будет обработано во время текущего или следующего такта именно в том месте, где это необходимо. Схема метода game.update может быть примерно такой:

• обработка событий, в ходе которой могут быть добавлены новые объекты или удалены отработавшие, изменено состояние объектов
• обновление состояния объектов (update)
• обработка столкновений, корректировка состояний

В библиотеку PyGame очередь событий уже встроена. Туда поступают события от мыши и клавиатуры, туда же можно добавлять и пользовательские события. Кстати, недавно я решил написать простенький оконный интерфейс для Dream (когда-нибудь он всё равно понадобится). Это надстройка над всей вышеописанной системой — приложение server превращается из приложения уже в окно, которое может создавать свои дочерние окна. GUI передаёт события мышки и клавиатуры в активное окно, осуществляет переключение между окнами и т.п. GUI вызывает метод update каждого окна; окно, если в нём игра — методы update игры и камеры, игра — методы update своих дочерних объектов. После того, как все объекты обновлены, GUI производит отрисовку по тому же иерархическому принципу.

События — это своего рода канал связи между отдельными объектами всей системы. Если один объект хочет что-то передать другому, он создаёт событие. Каждый объект обрабатывает только те события, которые предназначены для него. Какие-то он может обрабатывать сам, какие-то — направлять дочерним объектам. Главное — чтобы всё было согласовано. :)

Давным-давно, когда мне только пришла идея писать Dream (тогда он назывался 2D Universe), очень остро встал вопрос о выборе платформы. Писать на C++ мне не хотелось, потому что это был тихий ужас для сложного проекта одного разработчика, который к тому же имеет лишь небольшой опыт создания игр и слабо представляет окончательный результат. Мне была необходима возможность творить и пробовать. И я пытался писать Dream в Game Maker и… Matlab, хе хе. О чём я только думал тогда? :)

Наконец, в марте 2007 года я каким-то образом наткнулся на Python. Он мне так понравился, что я изучил его «залпом» и тут же портировал туда свои наработки. Python одновременно предоставил и полную свободу действий, и удивительную простоту и лёгкость разработки. Конечно, это интерпретатор, объектно ориентированный «от корней», и у него слишком низкая производительность для real-time игр, но наиболее узкие места в плане производительности можно переписать на C и подключить в виде скомпилированных библиотек. Есть даже средство, которое призвано максимально упростить эту задачу — Pyrex. В самом крайнем случае Python можно использовать для «quick prototyping», а в дальнейшем переписать весь код на C++: это тоже вариант, но он вряд ли необходим. Надо ли говорить, что любые оптимизации, будь то оптимизации в Python или портирование в C, следует выполнять только для полностью закрепившихся участков кода, которые уже не подлежат изменениям.

Мне также нужно было остановиться на какой-то платформе для ввода/вывода. Для игр на Python стандартом является использование библиотеки PyGame, которая является биндингом С-шной SDL. Но её графические возможности (и производительность) весьма ограничены. К счастью, существует рабочий биндинг OpenGL для Питона, который называется, как нетрудно догадаться, PyOpenGL, и который может работать вместе с PyGame. Всё перечисленное, к тому же, является мультиплатформенным и бесплатным.

Трудно сказать, когда мне впервые пришла в голову идея создания двумерной вселенной, и почему. Главным её вдохновителем, несомненно, является великая Игра Frontier (Elite 2), но не стоит думать, что я поставил себе цель создать ещё одну «Элиту». К тому же, если вы помните, Frontier — трёхмерная игра. Просто её ключевые элементы — свобода действий, реалистичная физика движения, огромные пространства для исследования, автоматическая генерация контента — универсальны и, как мне кажется, характеризуют будущее игростроения. Это то, чего пока добились очень немногие игры и до чего нужно расти и расти.

Другие вдохновители проекта — онлайн-игра Space Ace и старенькая игрушка V-Wing. Это маленькие 2D-игрушки, которые позволяют понять весь кайф летающих треугольников. :) Они также имеют реалистичную (ньютоновскую) физику движения, в которой игрок имеет возможность включать и выключать двигатель (ускорение), тем самым управляя своим «кораблём». Подобное управление поначалу кажется очень непривычным и сложным — игрок чувствует себя как младенец, делающий первые шаги. Но если немного потренироваться, вы убедитесь, что эта модель управления таит в себе поистине безграничные возможности постепенного совершенствования и увеличения своего скилла.

Косвенно к вдохновителям проекта можно отнести и Magic Pen. Это уже совсем другой жанр, но эта игра показывает, каким большим плюсом для многих игрушек может стать реалистичная физика взаимодействий между объектами. Я подумал, что реалистичная модель столкновений прекрасно дополнит реалистичную кинематику движения, и с удовольствием позаимствовал этот принцип для своего проекта.

Наконец, последними косвенными вдохновителями можно назвать Left 4 Dead — мажорный зомбишутер от Valve, и даже в большей степени — его демейк Left 4k Dead, прогремевший по сообществу инди-игр. В первой игре применён принцип автоматической расстановки врагов и планирования их атак по ходу игры — зачатки автоматической генерации контента. Именно это во многом обуславливает коммерческий успех игры. Ну а демейк (как римейк, только как бы в обратную сторону) - просто двумерный и очень прикольный.

Ах да, как я мог забыть про ADOM. Это rogue-like RPG одного разработчика, потрясающая своим масштабом, полноценной моделью игрового мира и свободой действий, при этом целиком выполненная в ASCII графике. Ну не чудо ли?