← Модуль 1/Коллизии
EN
Модуль 1 · Аркады и основы

Коллизии: AABB и тайловые

Почему самый дешёвый примитив столкновений — выровненная по осям коробка — до сих пор держит каждый 2D-движок, и как сетка тайлов превращает проверку столкновения в O(1).
~15 мин
Суть за 20 секунд
AABB (axis-aligned bounding box) — прямоугольник, стороны которого параллельны осям. Два таких пересекаются ⇔ они перекрываются по обеим осям одновременно — это 4 сравнения, без корней и тригонометрии. Для статичного мира из плиток ещё дешевле: позицию объекта делишь на размер тайла, смотришь 2–4 соседние клетки, и разрешаешь столкновение по осям раздельно (сначала X, потом Y) — это убирает зацеп за углы. Слабое место — туннелирование: быстрый объект перепрыгивает тонкую стену за один шаг; лечится фиксированным шагом или «заметанием» (swept AABB). Та же математика — IoU в детекции объектов: пересечение коробок дословно.

Механизм

Перекрытие двух AABB — теорема о разделяющей оси в миниатюре

Коробка задана краями [minX,maxX]×[minY,maxY]. Две коробки не пересекаются, если есть ось, по которой их проекции расходятся. Для выровненных по осям коробок осей-кандидатов всего две (X и Y), поэтому пересечение — это отрицание «разошлись хоть по одной»:

overlap⇔ (aminX<bmaxX) ∧ (amaxX>bminX) ∧ (aminY<bmaxY) ∧ (amaxY>bminY)

Четыре сравнения, ноль умножений — потому это и есть базовый broad-phase-тест во всех движках. Если все четыре истинны, коробки перекрываются; глубину проникновения по каждой оси даёт минимум из перекрытий, а вытолкнуть объект дешевле всего по оси наименьшего перекрытия (minimum translation vector).

A B ось X ось Y проекции перекрылись по X и по Y → столкновение
Перекрытие по обеим осям = пересечение коробок. Расходятся хоть по одной — пути нет, столкновения нет.

Тайловые коллизии — O(1) вместо «каждый с каждым»

Проверять объект против всех стен — это O(n). Но если мир выложен плитками размера T, координаты объекта прямо адресуют клетки: достаточно глянуть те 2–4 тайла, которые накрывает его коробка.

col = floor(x / T); row = floor(y / T); // клетка под точкой // коробка накрывает клетки [floor(minX/T)..floor(maxX/T)] × [...Y...]

Это сводит «найти ближайшую стену» к чтению по индексу — то же преимущество, что у тайловой карты для рендера. Ключевой приём разрешения — двигать и разрешать оси по очереди: сдвинул по X → проверил/выдавил из стен по X; затем сдвинул по Y → проверил/выдавил по Y. Раздельность критична: при одновременном разрешении объект цепляется за угол плитки и застревает на ровном полу из стыков тайлов.

Туннелирование и «заметание» (swept AABB)

Дискретная проверка смотрит позицию после шага. Если за шаг объект сдвинулся дальше толщины стены, на прошлом кадре он был перед стеной, на этом — уже за ней, а контакт между кадрами никто не проверил → пролетел сквозь (tunneling). Два лечения: маленький фиксированный шаг (ограничивает сдвиг за тик — см. урок про игровой цикл) и swept AABB — считаем не «пересеклись ли сейчас», а когда на отрезке движения происходит первый контакт. Для движения вдоль оси время входа по каждой оси:

tentry= dnear vaxis , thit= max(tentryX,tentryY)

где d_near — расстояние до ближней грани препятствия по оси, v_axis — скорость по ней. Контакт реален, если t_hit ∈ [0,1] и по другой оси в этот момент проекции уже перекрыты. Объект ставим в позицию момента t_hit, гасим нормальную компоненту скорости и «скользим» по касательной.

Числовой пример. Пуля летит вправо со скоростью 50 px/тик, стена толщиной 8 px на её пути в 30 px впереди. Дискретно: за тик сдвиг 50 > (30+8) → следующая позиция уже за стеной, перекрытия в момент проверки нет → туннель. Swept: t_entry = 30/50 = 0.6 ∈ [0,1] → контакт на 60% шага, пуля честно останавливается в стене. Фикс-шаг поменьше (скажем, 4 подшага по 12.5 px) тоже ловит стену — но дороже.

🕹 В какие игры поиграть — и что заметить

От «коллизия в одну строку» до пиксельно-точной интеджерной физики платформеров. По каждому кейсу: как сделано и что спровоцировать, чтобы увидеть модель столкновений руками.

Pong 1972 · столкновение почти 1D

Мяч и ракетка — фактически AABB, но интересно поведение после контакта: угол отскока часто зависит от того, куда по ракетке попал мяч (край даёт круче угол) — это уже не чистая физика, а дизайнерский слой поверх простого теста перекрытия.

🎮 Сыграй: в Pong бей мяч краем ракетки против центра — сравни углы отскока. Проверь, ракетка — это отрезок или прямоугольник: лови мяч у самого торца.

Space Invaders 1978 · сетка AABB + разрушаемые щиты

Пуля против пришельца — перекрытие коробок; пришельцы стоят сеткой, так что проверка идёт по адресуемым ячейкам, а не «каждая пуля против каждого». Щиты — битмап, который выгрызается попиксельно: контакт пули со щитом стирает пиксели. Два разных режима столкновений в одной игре: грубый (AABB по сетке) и точный (битмаска по щиту).

🎮 Сыграй: постреляй в щит под углом — он деградирует попиксельно, дырами неправильной формы. Это пиксельная маска, а не AABB. А попадание по пришельцу — мгновенное «коробка в коробку».

Super Mario Bros 1985 · тайловые коллизии, разрешение по осям

Марио — AABB против тайловой сетки. Классика жанра: раздельное разрешение X и Y (иначе зацеп за стыки плиток), проверка «головой снизу вверх» для удара по блоку и «ногами» для приземления. На больших скоростях вылезает туннелирование — спидранеры протискиваются сквозь тонкие стены, разогнавшись.

🎮 Сыграй: в SMB разгонись на спуске и влетай в угол блока — почувствуешь, как игра «доводит» тебя по одной оси за раз. Глянь спидран-трюки с проходом сквозь стену — это туннелирование на высокой скорости.

Celeste / TowerFall пиксельная интеджерная физика

Мэдди Торсон строит коллизии на целых пикселях: объект двигают по одному пикселю за раз с накоплением дробного остатка, на каждом шаге — простой AABB-тест против тайлов. Это анти-туннелирование «в лоб» (сдвиг ограничен пикселем) + детерминизм (целые координаты), на котором держатся фрейм-перфектные трюки и TAS.

🎮 Сыграй: в Celeste обрати внимание на «прощающие» коллизии у краёв (corner-correction подталкивает тебя мимо угла). Это поверх честного попиксельного AABB — дизайнерский слой, как угол отскока в Pong.

Sonic the Hedgehog контраст: сенсоры и высотные карты

Где AABB не хватает — наклоны и петли. Sonic не коробка: у него сенсоры (лучи вниз/в стороны), которые читают высотные массивы тайлов (для каждого тайла — профиль высоты). Это уже не «перекрытие коробок», а «зондирование поверхности» — цена за скорость и рельеф, которых плоский AABB не даёт.

🎮 Сыграй: прокатись по петле/склону в Sonic — заметь, как он прилипает к поверхности под любым углом. Коробка так не умеет; это сенсоры по высотным картам тайлов.

Хардкор · теория: SAT, сумма Минковского и время контактаможно пропустить

AABB-тест — частный случай теоремы о разделяющей оси (SAT): два выпуклых тела не пересекаются ⇔ существует ось, на которую их проекции не перекрываются. Для произвольных выпуклых многоугольников осей-кандидатов — нормали всех граней обоих тел; для AABB нормали вырождаются в X и Y, поэтому осей всего две и тест так дёшев.

Сумма Минковского — почему «коробка против коробки» = «точка против коробки»

Пересечение A и B эквивалентно тому, что начало координат лежит внутри разности Минковского A ⊖ B. Для двух AABB эта разность — снова AABB (со сложенными полуразмерами). Отсюда трюк: задачу «движущаяся коробка против стены» сворачивают в «движущаяся точка (центр) против раздутой стены», и swept-тест становится пересечением луча с AABB — классический slab-метод.

Slab-метод и время входа/выхода

Луч p + t·v против AABB: по каждой оси считаем интервал [t₁,t₂], на котором луч внутри «плиты» (slab) этой оси, и берём пересечение интервалов по всем осям:

tenter= max(t1x,t1y), texit= min(t2x,t2y)

Пересечение есть ⇔ t_enter ≤ t_exit и интервал задевает [0,1]. Ось, давшая максимум на входе, задаёт нормаль контакта — по ней гасят скорость, по другой скользят. Это и есть continuous collision detection (CCD) для AABB в чистом виде.

Хардкор · инженерия: broad-phase, пространственные индексы, детерминизмможно пропустить
  • Broad-phase → narrow-phase. Сначала дешёвый консервативный отсев пар-кандидатов (AABB-перекрытие), потом дорогой точный тест только для выживших. Антипаттерн джуна — гонять точный тест на всех парах: это O(n²).
  • Пространственный хэш / равномерная сетка. Раскладываешь объекты по клеткам; проверяешь только внутри клетки и соседних. Для объектов схожего размера это близко к O(n) и проще дерева. Тайловые коллизии — вырожденный случай, где сетка уже есть.
  • Sweep-and-prune. Держишь объекты отсортированными по проекции на ось; пары-кандидаты — те, чьи интервалы перекрываются. Хорошо работает при «временной когерентности» (кадр к кадру мало что меняется).
  • Иерархии для разнокалиберного. Когда размеры объектов сильно разные (сетка плоха), берут BVH из AABB — тот же примитив, но в дереве. Прямой мост к рендеру (frustum/occlusion culling) и трассировке лучей.
  • Детерминизм. Интеджерная/fixed-point коллизия + фиксированный порядок разрешения пар = воспроизводимый результат для лок-степа и реплеев. Float и недетерминированный порядок ломают сетевую синхронизацию.
Аналогия
AABB — это почтовые коробки на складе: чтобы понять, мешают ли друг другу две посылки, ты не разворачиваешь содержимое — смотришь, перекрываются ли коробки. Грубо, но мгновенно. Точную форму (плюшевого мишку внутри) проверяешь только если коробки уже задели друг друга. Это broad-phase → narrow-phase: дешёвый консервативный тест отсекает 99% пар, дорогой — добивает оставшийся 1%.
Почему это важно
Коллизии — это место, где «работает» и «тормозит» расходятся. Наивная проверка всех пар убивает FPS на сотне объектов; AABB + пространственная сетка держат тысячи. А выбор «по осям раздельно» против «сразу» — разница между платформером, который ощущается твёрдым, и тем, где игрок цепляется за невидимые углы. Это первый урок про иерархию точности: дешёвый консервативный фильтр впереди дорогого точного — паттерн, который вернётся и в рендере, и в поиске, и в ретривале.
🔁 За пределами игр — куда это переносится
Урок даёт два переносимых приёма: дешёвый консервативный тест перед дорогим точным (broad→narrow) и пространственный индекс вместо перебора всех пар.

ML / AI (твой домен): перекрытие AABB — это дословно IoU (intersection-over-union) в детекции объектов; NMS (non-max suppression) гасит рамки по тому же тесту пересечения. Пространственный хэш ⇄ ANN / LSH: бакетируешь векторы и сравниваешь только внутри бакета. Broad→narrow ⇄ coarse-to-fine retrieval: дешёвый ANN-кандидатогенератор, затем точный реранк — та же двухфазность, что broad/narrow-phase.

Системы / БД: пространственные индексы (R-tree, geohash, quadtree) для гео-запросов; «проверь только соседние клетки» = bucketing/sharding по ключу диапазона.

Графика / геометрия: BVH и frustum-culling в рендере и трассировке лучей — те же AABB в дереве; collision и visibility решают одной структурой.

Принцип: никогда не считай дорогой точный тест на всех парах. Сначала дешёвый консервативный фильтр (он может ошибаться только в сторону «возможно»), потом точный — на выживших.

🔧 Запусти и поковыряй — на домашнем компе
Во что играть — выше (🕹). Здесь — увидеть коллизии вживую в движке:
🔧 Поковырять (debug) ~40 мин, Godot
В Godot собери платформер из TileMap + CharacterBody2D. Включи Debug → Visible Collision Shapes — увидишь AABB-формы поверх спрайтов. Разнеси движение на move_and_slide по осям и понаблюдай за разрешением. Затем сломай: задери скорость объекта и убери CCD/малый шаг — поймаешь туннелирование сквозь тонкую плитку. Верни маленький фиксированный шаг — туннель исчезнет.
🧪 Потестить (глазами QA) ~15 мин
Лови классику багов столкновений: зацеп за стыки тайлов (значит, оси разрешаются вместе), дрожание на границе стены, проход сквозь стену на разгоне (туннель), застревание в углу при одновременном касании двух стен, «прилипание» к потолку. Каждый баг — диагноз конкретного упрощения в коллизии.
Чеклист: увидел AABB-формы через debug-отрисовку; спровоцировал туннелирование и убрал его фикс-шагом; поймал зацеп за угол при не-раздельном разрешении осей.
Связи
основа
Железо-ограничения — спрайты и тайлы из прошлого урока и есть «коробки» и «клетки», между которыми считается столкновение.
основа
Игровой цикл — фиксированный шаг ограничивает сдвиг за тик и тем самым предотвращает туннелирование; переменный dt на просадке его провоцирует.
дальше
Аркадный ИИ — призраки и автоматы двигаются по той же тайловой сетке, что и коллизии; топология клеток связывает оба урока.
Вопросы пытливого ума
Почему X и Y разрешают раздельно, а не сразу обе?
При одновременном разрешении вектор выталкивания смотрит «по диагонали», и объект, едущий по полу из плиток, цепляется за вертикальные стыки между ними: микро-перекрытие по Y на границе тайла трактуется как стена сбоку → рывки и застревание. Раздельный проход (сдвинул по X, выдавил по X; затем по Y, выдавил по Y) делает горизонтальное движение «не видящим» горизонтальные швы пола. Цена — порядок осей чуть влияет на краевые случаи (углы), поэтому его фиксируют.
AABB-перекрытие и IoU в детекции объектов — это правда одна формула?
Площадь пересечения двух AABB — это произведение перекрытий по осям: max(0, minMaxX−maxMinX) · max(0, …Y…). IoU = это пересечение, делённое на объединение. То есть тест «перекрылись?» из коллизий — это числитель IoU. NMS в детекторах выкидывает рамки с высоким IoU к уже принятой — буквально тот же геометрический примитив, что выталкивание в физике. Разные домены, одна геометрия выровненных коробок.
Туннелирование — это про коллизию или про игровой цикл?
Про оба, и в этом суть. Дискретная проверка видит только концы шага; если за шаг сдвиг больше препятствия, контакт между кадрами теряется. Лечится с двух сторон: со стороны цикла — маленький фиксированный шаг (ограничивает максимальный сдвиг за тик), со стороны коллизии — swept/CCD (ищем момент контакта на отрезке движения). На просадке с переменным dt шаг разбухает и туннель возвращается — поэтому фикс-шаг и коллизии — один разговор.
Объект повернули на 30° — почему AABB вдруг врёт?
AABB по определению выровнена по осям: у повёрнутого объекта она охватывает «габарит», включая пустые углы → ложные срабатывания у углов и неверная нормаль. Варианты: пересчитывать AABB как охватывающую коробку (быстро, грубо, годится для broad-phase) либо переходить на OBB/полный SAT с нормалями граней (точно, дороже). Типичная схема: AABB как broad-phase даже для повёрнутых тел, SAT — как narrow-phase. Это ровно «дешёвый фильтр → точный тест».
Когда тайловая сетка хуже дерева (BVH/quadtree)?
Когда объекты сильно разного размера или распределены неравномерно. Равномерная сетка хороша, пока тела примерно одного калибра и плотность ровная: тогда в клетке — единицы объектов, проверок мало. Гигант, накрывающий сотни клеток, или «всё в одном углу» убивают сетку (либо клетка переполнена, либо большинство пустует). Тогда берут иерархию (quadtree/BVH), которая адаптирует разрешение под плотность. Аркадные игры брали сетку, потому что мир и так был тайловым и однородным.
Что почитать