Структуры данных сцены

НЕ ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику

Графическая модель — коллекция записей в оперативной памяти. От структуры зависят скорость update, коллизий и render.

Старт — массив. При росте проекта добавляют дерево сцены и пространственные индексы.

---

Массив объектов

const entities = [
  { type: 'enemy', x: 100, y: 200, hp: 3, alive: true },
  { type: 'coin', x: 300, y: 150, value: 10 },
];

В update:

for (const e of entities) {
  if (e.type === 'enemy') e.x += e.vx * dt;
}

В render:

for (const e of entities) {
  if (!e.alive) continue;
  drawEntity(ctx, e);
}

Плюсы	Минусы
простой код	поиск по id за O(n)
последовательный обход в кэше	splice при удалении — O(n)
легко сохранить в JSON	нет иерархии "рука на теле"

Удаление без паузы кадра

Mark-and-sweep — пометить, потом вычистить:

bullet.alive = false;
for (let i = entities.length - 1; i >= 0; i--) {
  if (!entities[i].alive) entities.splice(i, 1);
}

Swap-remove за O(1):

function removeAt(arr, index) {
  arr[index] = arr[arr.length - 1];
  arr.pop();
}

Порядок в массиве меняется — для пуль и частиц обычно допустимо.

Код ITЗагрузка примера кода…

---

Дерево сцены (Scene Graph)

Иерархия нужна, когда части объекта двигаются вместе — персонаж с оружием, машина с колёсами.

World
├── Player
│   ├── BodySprite
│   └── WeaponSprite
├── Enemies
│   ├── Enemy_01
│   └── Enemy_02
└── UI_HUD

Каждый узел хранит локальную трансформацию. Мировая позиция — произведение матриц всех предков.

Задача	Роль дерева
Скелетная анимация	кисть следует за предплечьем
Группа врагов	сдвиг родителя двигает детей
Скрытие ветки	visible = false отключает поддерево

Реализации: Unity Transform, Three.js Object3D, DOM, WPF VisualTree.

Компромисс: плоский массив с полем parentId и кэшем мировых координат.

---

Пространственное индексирование (2D)

При 50 объектах хватает двойного цикла коллизий. При 5 000 без индекса сложность O(n²) перегружает CPU.

Структура	Идея	Когда
Uniform grid	экран на ячейки 64×64 px	равномерные пули
Spatial hash	ключ из координат ячейки	частицы, быстрый insert
Quadtree	деление переполненных квадрантов	кластеры врагов

Алгоритм grid:

1. Очистить ячейки в начале кадра
2. Положить объект в ячейку по центру AABB
3. Проверять коллизии внутри ячейки и в 8 соседях

---

Culling — отсечение невидимого

Culling — пропуск отрисовки объектов, которые пользователь не увидит.

Viewport culling (2D)

Перед drawImage проверьте попадание в окно с учётом камеры:

function isOnScreen(obj, cameraX, viewW) {
  const sx = obj.x - cameraX;
  return sx + obj.width >= 0 && sx <= viewW;
}

Frustum culling (3D)

View frustum — усечённая пирамида поля зрения камеры (угол обзора, ближняя и дальняя плоскости). Если bounding box объекта целиком снаружи — draw call не отправляют.

Техника	Что отсекает
Frustum culling	вне поля зрения
Occlusion culling	за стеной
LOD	дальние объекты — упрощённая модель

---

Слои и z-order

2D без Z-buffer — явные слои или сортировка по z:

const ORDER = ['bg', 'terrain', 'actors', 'fx', 'ui'];
for (const layer of ORDER) {
  for (const e of entities) if (e.layer === layer) draw(e);
}

3D — depth buffer; прозрачные объекты часто рисуют после непрозрачных.

---

Экземпляры и ресурсы

	Экземпляр (модель)	Ресурс (VRAM)
Количество	тысячи	десятки–сотни
Данные	x, y, hp, state	текстура, mesh, звук
Пример	enemy_42 на карте	sprites/enemy.png один раз

Sprite batching — один draw call на атлас текстур.

Object pool — заранее созданные пули вместо new и пауз от сборщика мусора.

---

Выбор структуры

Масштаб	Рекомендация
Небольшой проект, до 100 объектов	массив и простой culling
Платформер, сотни пуль	массив, spatial hash, pool
3D уровень	scene graph, frustum, LOD
UI-heavy	retained tree (DOM, WPF)

---

Связи

• Архитектура
• Математика
• GPU и draw calls
• Структуры данных