Граф сцены: как игры устраивают миры

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

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

Что такое граф сцены на самом деле#

Граф сцены — это структура данных, которая хранит содержимое сцены как набор узлов, выстроенных в иерархию «родитель — дочерний объект». Каждый узел представляет что-то в мире: спрайт, модель, источник света, камеру, группу. Узлы, способные содержать другие узлы, называют группирующими. Всё это читается как генеалогическое древо: один корень наверху, ветви под ним, листья внизу.

Важны два технических момента, и их легко спутать.

• На практике это дерево. Почти в каждом игровом движке у узла ровно один родитель. Это упрощает математику: чтобы понять, где находится объект, достаточно пройти по одному пути от корня вниз до него.
• В общем случае — граф. Более широкое определение, пришедшее из графических библиотек, — это направленный ациклический граф. Он допускает повторное использование: один подграф может встречаться в сцене несколько раз, поскольку у узла может быть больше одного родителя, если при этом не образуется цикл. Графические библиотеки вроде Open Inventor и OpenSceneGraph этим пользуются. Игры ради простоты обычно от этого отказываются.

Название прижилось, потому что структура старше большинства игровых движков: граф сцены обрёл популярность благодаря набору инструментов Open Inventor от компании SGI в конце 1980-х, и с тех пор эту модель переиспользуют повсеместно.

Единственное правило, которое заставляет всё работать: наследование трансформаций#

Всё полезное в графе сцены проистекает из одного правила: трансформация дочернего объекта задана относительно родительской.

Каждый узел хранит локальную трансформацию — собственное положение, поворот и масштаб. Мировая трансформация узла — это произведение его локальной трансформации и локальных трансформаций всех узлов над ним вплоть до корня. Движок вычисляет её каждый кадр, проходя дерево сверху вниз.

Конкретный пример. Корабль стоит в мировой позиции (20, 0). Внутри него турель имеет локальную позицию (5, 0) — то есть на пять единиц правее центра корабля. Поэтому мировая позиция турели — (25, 0). Теперь переместите корабль в (40, 0). Вы изменили одно число у корабля, а турель, без всяких правок, оказалась в (45, 0). Поверните корабль на 90 градусов — и турель опишет дугу вокруг центра корабля, снова без изменений в её собственных данных.

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

Что даёт граф#

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

• Композиция. Сложный объект — персонажа, машину, экран интерфейса — собирают из меньших узлов и обращаются с ним как с единым целым. Переместите, скопируйте или удалите группу, и её части последуют за ней.
• Распространение видимости. Скрытие родителя делает невидимыми и все его дочерние объекты. Отключите корневой узел меню паузы — и исчезнут все кнопки внутри.
• Повторное использование. Определите сцену «гоблин» один раз и расставьте в уровне множество её копий; каждый экземпляр хранит свою позицию, но использует общее определение.
• Отсечение и сортировка. Чтобы отрисовать кадр, движок обходит дерево, отбрасывает ветви, оказавшиеся вне поля зрения камеры (отсечение по пирамиде видимости), и сортирует оставшееся по материалу или глубине для скорости.

Как граф сцены выглядит в крупных движках#

Идея у всех общая, но каждый движок называет и оформляет её по-своему.

Движок	Как называет	Как передаются трансформации
Godot	Дерево сцен («всё есть узел»)	Дочерние узлы наследуют трансформацию родителя; сами сцены — деревья узлов, вложенные друг в друга
Unity	Иерархия трансформаций	У каждого компонента-трансформации может быть родитель; мировая трансформация равна родительской, умноженной на локальную
Unreal	Присоединяемые сценовые компоненты	Сценовый компонент крепится к родительскому и наследует его трансформацию
Open Inventor, OpenSceneGraph, OGRE	Граф сцены (группирующие узлы)	Исходная модель направленного ациклического графа: состояние и трансформации каскадом спускаются по группам

Godot опирается на эту структуру сильнее большинства: в документации сцена описывается как дерево узлов, а весь проект — дерево таких деревьев. Сцена игрока объединяет спрайт, форму столкновения и камеру; затем сама сцена игрока помещается в сцену уровня. Композиция через вложенность — это и есть весь рабочий процесс.

В Unity эта иерархия устроена проще, но работает так же. У каждого объекта есть компонент трансформации, и любой такой компонент может объявить другой своим родителем. Укажите родителя — и объект начинает двигаться вместе с ним. Отдельного типа «дерево сцены» нет: иерархия живёт в самих трансформациях.

Unreal использует компоненты. Актёр содержит компоненты, а сценовый компонент, у которого есть трансформация, может быть присоединён к другому сценовому компоненту как к родителю. Модель та же: присоединённый компонент движется вместе с родителем.

Линия преемственности проходит через графические библиотеки из последней строки таблицы. OGRE и OpenSceneGraph — библиотеки графа сцены, прямые наследники Open Inventor, и большинство современных движков переняли ту же структуру.

Во что он обходится#

Граф сцены не бесплатен, и честная часть любого объяснения — назвать его цену.

Главная цена — обход дерева. Чтобы вычислить мировые трансформации, движок каждый кадр обходит дерево, идя по ссылкам от родителя к дочернему объекту. Обход глубокого дерева, связанного указателями, тяжёл для кэша процессора: каждый шаг может оказаться в другой области памяти, и процессор, способный мгновенно проглотить плоский массив, простаивает в ожидании данных. Для нескольких сотен объектов это не имеет значения. Для десятков тысяч частиц или снарядов обход способен занять весь кадр.

Именно поэтому последнее десятилетие принесло альтернативу: ориентированный на данные подход и паттерн «сущность — компонент — система» (ECS). ECS хранит данные каждого типа компонентов — все позиции, все скорости — в плоском сплошном массиве, так что движок обновляет их все, последовательно перебирая память. Движки и фреймворки, построенные так, — Bevy, Unity DOTS, Flecs — минимизируют или вовсе обходят глубокие иерархии для массового моделирования.

Практический вывод: граф сцены и ECS — не соперники, а инструменты для разных задач. Используйте иерархию там, где нужны связи, — рука держит кисть, меню содержит кнопки, родитель группирует дочерние объекты. Используйте плоские массивы там, где нужно быстро обрабатывать множество похожих объектов. Многие движки держат и то и другое. Глубокие иерархии становятся проблемой лишь тогда, когда вы вкладываете друг в друга то, что вовсе не требовало вложенности.

Частые ошибки#

Ошибка	Что идёт не так	Что делать вместо этого
Вложенность всего ради аккуратности	Глубокое дерево обходится дорого и провоцирует промахи кэша без всякой пользы	Вкладывайте объекты, только когда нужна связь по трансформации или видимости; иначе держите дерево мелким
Путаница графа сцены и ECS	Ждёте, что одна структура справится с обеими задачами, и разочаровываетесь	Граф сцены — иерархия связей; ECS — плоские массивы для массового перебора; используйте оба
Игровая логика в самой иерархии	Логика путается между родительскими и дочерними узлами, её трудно отследить	Держите иерархию для композиции и трансформаций; поведение выносите в компоненты или скрипты
Забыли, что дочерние объекты движутся с родителем	Элемент интерфейса или объект в мировых координатах уплывает, потому что сдвинулся его родитель	Отсоедините его или поместите независимые элементы в корень сцены
Граф воспринимают как свободно связываемый	Цикл или два родителя у одного узла ломают математику трансформаций	Держите одного родителя на узел; свободу повторно использовать подграфы оставьте библиотекам, а не геймплею

Роль Egmatic#

Egmatic — это 2D-редактор и движок поверх рантайма MonoGame. Его редактор сцен собирает объекты в иерархию, которую вы правите в реальном времени, поэтому правило наследования трансформаций — турель, следующая за кораблём, конечности персонажа, движущиеся вместе с телом, — видно сразу, без абстрактных рассуждений. Рядом с редактором сцен расположена узловая логика, так что структура, на которой строится мир, и логика, которая им управляет, живут бок о бок.

Такое сочетание важно именно для тех игр, где граф раскрывается лучше всего: 2D-сцены из многослойных, сгруппированных объектов, связи между которыми хочется видеть с первого взгляда. Более широко о композиции сцен рассказывают руководство по основам композиции сцены и руководство по дизайну 2D-сцен, а сравнение событийно-ориентированных движков продолжает там, где структура встречается с логикой.

Заключение#

Граф сцены — это иерархия узлов, в которой трансформация каждого дочернего объекта отсчитывается от родительской, поэтому изменения спускаются вниз автоматически. Это единственное правило позволяет игре удерживать связанные объекты вместе, распространять видимость, создавать повторно используемые экземпляры и отсекать либо сортировать сцену для отрисовки. Крупные движки реализуют одну и ту же идею под разными именами — дерево сцен Godot, иерархия трансформаций Unity, присоединяемые компоненты Unreal, — а линия преемственности уходит к Open Inventor от SGI.

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

---

Источники#

1. Граф сцены — иерархическая структура данных, каскадом передающая трансформации и состояние по иерархии — Википедия: Граф сцены
2. Open Inventor и граф сцены как направленный ациклический граф (группирующие узлы, распространение от родителя к дочернему объекту) — WPI: Introduction to Inventor
3. Трансформации в графе сцены — мировая трансформация узла есть произведение матриц вдоль пути от корня — Cornell CS4620 lecture
4. Дерево сцен и узлы Godot — сцена есть дерево узлов; дочерние узлы наследуют трансформацию, видимость и состояние родителя — Godot docs: Node
5. Сценовые компоненты и присоединение в Unreal — сценовый компонент крепится к родителю и наследует его трансформацию — Unreal Engine docs: Components
6. Ориентированное на данные проектирование и ECS — плоское, кэш-дружественное хранение компонентов как альтернатива глубоким иерархиям — Википедия: Entity component system