Автор — соло‑разработчик экшен‑игры с высоким скилл‑потолком — описывает свой инструмент Scaffold, встроенный в Unreal Level Editor. Цель — уйти от типичных ограничений общих движков (Unreal, Unity) и их динамических систем коллизий/навигации ради трёх целей: продуктивность, индивидуальность и предсказуемая производительность (60+ FPS как «корректность»).
Базовая идея: выпуклая геометрия и разбиение пространства
Ключевое свойство — выпуклая оболочка: для любой пары точек внутри фигуры отрезок между ними полностью лежит внутри. Большинство пространственных алгоритмов в играх (рейкаст, путьfinding) используют разбиение сцены на сеть связанных выпуклых объёмов — convex decomposition. Грани таких объёмов делятся на «стены» (закрывают внешний контур) и «окна» (общие внутренние грани между объёмами).
Рейкаст в выпуклом разбиении:
- Определяем, в каком объёме стартует луч.
- Выполняем пересечение луча с плоскостями граней.
- Если ближайшая грань — «стена», это хит; если «окно» — переходим в соседний объём и повторяем.
Для подвижных объектов вводятся «корзины» (object buckets): каждый объём хранит ограниченный список примитивов. При трассировке сначала проверяются объекты в корзине, затем переход к дальней грани. Фиксированная ёмкость корзин даёт O(1) на локальный шаг и около O(n) суммарно для n акторов, вместо O(n²) при наивной проверке «каждый с каждым». При переменной ёмкости корзины можно рекурсивно делить пространство, получая дерево (O(log n) на запрос и O(n × log n) суммарно).
Навигация на выпуклой сетке
Для pathfinding на выпуклом разбиении в центре «окон» ставятся точки‑узлы. Любой актор внутри объёма может дойти до любой точки этого объёма, а прямые отрезки между точками соседних объёмов гарантированно проходимы. По этим узлам строится граф, по которому алгоритм A* ищет путь без коллизий.
Почему стандартные движки не подходят задачам автора
Unreal и Unity не требуют от дизайнера явного построения выпуклого разбиения. Уровень — это список разрозненных Actors/GameObjects. Для коллизий и рейкаста на устройстве игрока в рантайме строятся динамические структуры:
- Коллизия/рейкаст: невидимая решётка (октодерево/Octree, Quadtree в 2D), где каждая ячейка — выпуклый бокс с корзиной объектов. Это broad-phase, который фильтрует кандидатов для точной проверки. Unreal перешёл с PhysX на Chaos; есть альтернативы Jolt, Havok.
- Навигация: в Unreal — Recast. Дизайнер расставляет объёмы, в фоне запускаются множественные рейкасты, формирующие «земляные» области для навигации. Система сильно параметризуема и требует постоянного твика.
Минусы такого подхода для соло‑разработчика:
- Высокие требования к CPU/RAM из‑за динамического построения.
- Переменная сложность O(n × log n), требующая долгого перф‑тюнинга.
- Вся тяжёлая работа переносится на устройство игрока вместо предрасчёта на машине разработчика.
Вдохновение: DOOM и Descent
Автор ищет альтернативу, которая дополняет стандартные системы, а не заменяет их, и использует общее базовое представление — выпуклое разбиение.
DOOM (1993)
DOOM — классический шутер от id Software, где основная нагрузка — столкновения со стенами, а объектов немного. Уровни редактируются свободно, но затем прогоняются через Binary Space Partitioning (BSP):
- Выбирается стена‑плоскость, остальные делятся на «впереди/позади», пересекающиеся — режутся.
- Рекурсией строится дерево; листья дают выпуклое разбиение.
Оригинальный DOOM ограничивался вертикальными стенами (почти 2D), позже Quake и Unreal Tournament применяли BSP к наклонной геометрии. Автору это интересно как история, но мало полезно для его задач.
Descent (1995) и Overload
Descent — «полный 3D» шутер от Interplay с заполнением объёма, а не плоскими уровнями. Мод‑редактор DLE показывает, что уровни строятся из выпуклых «сегментов» — шестиугольных кубоидов (hexahedrons). На первый взгляд это ограничивает форму комнат, но за счёт креативного связывания по рёбрам и углам можно получить почти любую форму. Все грани — квады, что упрощает текстурирование.
В 2018 создатели Descent выпустили духовного наследника Overload с редактором уровней и обучающими материалами. Там идею «материалов на квад‑грани» развили до системы модульных «кит‑пьес», позволяющих создавать современный, детализированный вид (например, скальные участки с дополнительной геометрией в трещинах).
Работа с этими инструментами стала для автора инсайтом: если строить уровень сразу из выпуклых сегментов, отпадает необходимость в тяжёлой пост‑декомпозиции (BSP и т.п.). Это напрямую ведёт к более предсказуемой производительности и облегчает построение собственных систем коллизий и навигации поверх Unreal.
Выводы
- Scaffold опирается на явное выпуклое разбиение пространства и «корзины» объектов для O(1)/O(log n) рейкаста и коллизий вместо O(n²).
- Явная выпуклая навигационная сетка даёт простую и надёжную основу для A* без тяжёлого рантайм‑строительства навмешей.
- Динамические системы Unreal/Unity (Octree, Recast, Chaos и др.) удобны для больших команд, но плохо бьются с целями соло‑разработчика по перформансу и контролю.
- Исторические подходы DOOM (BSP) и особенно Descent/Overload (выпуклые сегменты by construction) показывают, как редактор может сразу выдавать удобные для рантайма структуры.
- Строя уровни из выпуклых сегментов внутри Unreal, Scaffold позволяет «готовить» данные заранее и получать уникальный геймплей с предсказуемой производительностью.
