Оптимизация: пространственная сетка

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

Пространственная сетка — это разбиение игрового мира на одинаковые квадратные ячейки, в каждую из которых мы складываем объекты по их координатам, чтобы проверять коллизию только между соседями, а не между всеми подряд.

Зачем это нужно: цыплёнок и нашествие монеток

Представь: ты доделал свою аркаду про цыплёнка, накидал на уровень сотню монеток, два десятка врагов, частицы, бонусы — и игра, которая летала на трёх объектах, вдруг начала задыхаться. FPS просел с честных 60 до дёрганых 20, цыплёнок дрожит, прыжок ощущается как ходьба по болоту. Что случилось?

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

К концу урока у тебя будет сетка, которая режет мир на квадраты, раскладывает по ним всех монеток и врагов, и проверяет столкновения только внутри соседних клеток. Те же двести объектов — и снова честные 60 FPS. Поехали разбираться, почему «все со всеми» — это так дорого.

Почему «каждый с каждым» — это ловушка

Считаем проверки на пальцах

Когда у тебя на экране N объектов и каждый должен проверить столкновение с каждым другим, число проверок растёт не линейно, а почти как квадрат от N. Формула простая: N × (N − 1) / 2. Это значит, что если объектов стало в 10 раз больше, проверок становится примерно в 100 раз больше. Посмотри на табличку — она пугает честно:

Объектов (N)	Проверок пар
10	45
50	1 225
100	4 950
500	124 750
1000	499 500

Полмиллиона проверок каждый кадр, а кадров у нас 60 в секунду. Это тридцать миллионов проверок в секунду только ради того, чтобы понять, кто кого касается. Браузер сдаётся, и цыплёнок начинает заикаться.

Самое обидное — что почти все эти проверки бессмысленны. Если на уровне 1000 объектов и они раскиданы по большой карте, то в каждом конкретном кадре реально касается друг друга от силы пара десятков пар. Остальные сотни тысяч проверок дают честное «нет, не пересекаются» — мы жжём процессор впустую, спрашивая монетку в левом углу, не задела ли она врага в правом. Это как звонить по очереди всем людям в городе, чтобы узнать, не наступил ли кто-то тебе на ногу: ответ ты и так знаешь — наступить может только тот, кто стоит вплотную.

Учёные называют такой рост сложностью O(n²) — «о большое от эн в квадрате». Тебе не нужно зубрить этот значок, достаточно запомнить смысл: удвой число объектов — и работа учетверится. Любой алгоритм с таким поведением рано или поздно упрётся в потолок. Наша задача — сбить эту сложность почти до линейной, чтобы удвоение объектов лишь удваивало работу, а не возводило её в квадрат.

Метафора: вечеринка и рукопожатия

Подумай об этом как о вечеринке. Если в комнату зашло 10 человек и каждый должен пожать руку каждому, выйдет 45 рукопожатий — за пару минут управитесь. А теперь представь стадион на тысячу человек, где каждый жмёт руку каждому: это полмиллиона рукопожатий, вы там до пенсии простоите. Очевидно же, что на стадионе ты здороваешься только с теми, кто стоит рядом с тобой, а не бежишь через весь сектор к незнакомцу на другой трибуне.

Вот это «здороваться только с соседями» — и есть вся идея пространственной сетки. Цыплёнку нет смысла проверять столкновение с монеткой, которая на другом конце уровня. Если он в левом нижнем углу, а монетка в правом верхнем — они физически не могут пересечься в этом кадре. Так зачем тратить на них проверку?

Есть и другая метафора, поближе к твоему телефону. Открой карту в любом приложении: когда ты ищешь кафе рядом, приложение не перебирает все кафе планеты, отсеивая Токио и Буэнос-Айрес. Оно знает, в каком районе ты сейчас, и смотрит заведения только в этом районе и в паре соседних. Город заранее нарезан на квадраты-районы, и поиск идёт по району, а не по всему глобусу. Пространственная сетка делает с игровым миром ровно то же самое: нарезает его на районы и спрашивает только тех, кто живёт по соседству.

Идея сетки: режем мир на клетки

Накрываем весь игровой мир воображаемой клетчатой решёткой — как тетрадный лист в клетку, только клетки большие, размером с несколько цыплят. У каждой клетки есть адрес: колонка и ряд. Дальше делаем две вещи каждый кадр:

Раскладываем объекты по клеткам. Берём координаты объекта, делим их на размер клетки — и сразу знаем, в какой клетке он лежит. Никакого перебора, просто арифметика.
Проверяем только внутри своей клетки и соседних. Цыплёнок смотрит на свою клетку и 8 клеток вокруг (потому что он может задевать объект на самой границе). Все остальные сотни объектов он гордо игнорирует.

Магия в том, как быстро объект попадает в свою клетку. Если размер клетки 100 пикселей, а монетка стоит на координатах x = 350, y = 120, то её клетка — это колонка Math.floor(350 / 100) = 3 и ряд Math.floor(120 / 100) = 1. Одно деление, одно округление вниз — и адрес готов. Не нужно сравнивать монетку ни с кем, чтобы понять, где она живёт.

Пример 1. Складываем объекты в сетку

Начнём с самого сердца — структуры, которая хранит, кто в какой клетке. Используем обычный объект-словарь, где ключ — это адрес клетки в виде строки "колонка,ряд", а значение — массив объектов в этой клетке.

const CELL_SIZE = 100; // размер одной клетки в пикселях

// собираем сетку заново каждый кадр
function buildGrid(entities) {
  const grid = {};
  for (const e of entities) {
    const col = Math.floor(e.x / CELL_SIZE);
    const row = Math.floor(e.y / CELL_SIZE);
    const key = col + ',' + row;
    if (!grid[key]) grid[key] = [];
    grid[key].push(e);
  }
  return grid;
}

// пример: цыплёнок и три монетки
const chicken = { x: 150, y: 150, w: 32, h: 32 };
const coins = [
  { x: 160, y: 140, w: 16, h: 16 },
  { x: 800, y: 600, w: 16, h: 16 },
  { x: 130, y: 170, w: 16, h: 16 },
];
const grid = buildGrid([chicken, ...coins]);

Результат: на экране ничего не рисуется — это пока чистая логика. В grid образовалось две клетки. В ключе "1,1" лежат цыплёнок и две ближние монетки (их координаты после деления на 100 дают колонку 1 и ряд 1), а в ключе "8,6" — одинокая дальняя монетка. Цыплёнку даже смотреть в её сторону не придётся.

Разбираем по шагам

Math.floor(e.x / CELL_SIZE) — превращаем пиксельную координату в номер колонки. Деление масштабирует, floor отрезает дробную часть, чтобы получить целый адрес.
const key = col + ',' + row — склеиваем колонку и ряд в строку-адрес. Объект в JavaScript умеет хранить значения по строковым ключам, так что это удобный способ адресовать клетку без отдельного двумерного массива.
if (!grid[key]) grid[key] = [] — если клетка ещё пустая, заводим в ней пустой массив, а потом кладём туда объект через push.

Важная деталь: сетку мы пересобираем каждый кадр в начале игрового цикла, до проверки столкновений. Объекты двигаются, и их клетки меняются, поэтому вчерашняя раскладка нам не нужна.

Может закрасться мысль: «А не дорого ли строить сетку заново шестьдесят раз в секунду?» Нет, и вот почему. Чтобы разложить N объектов по клеткам, мы проходим по ним один раз: для каждого делаем пару делений и кладём в массив. Это линейная работа — N шагов. А наивная проверка «все со всеми» — это N², то есть несравнимо больше. Мы платим маленькую цену за постройку сетки, чтобы потом сэкономить гигантскую цену на проверках. Бухгалтерия сходится с огромным плюсом.

Пример 2. Проверяем только соседей

Теперь самое вкусное. Цыплёнок хочет узнать, с кем он столкнулся. Вместо того чтобы пробежать по всем монеткам мира, он спросит сетку: «Кто лежит в моей клетке и в восьми клетках вокруг?» — и проверит AABB только с этим коротким списком.

// простая AABB-проверка из прошлых уроков
function hit(a, b) {
  return a.x < b.x + b.w &&
         a.x + a.w > b.x &&
         a.y < b.y + b.h &&
         a.y + a.h > b.y;
}

// собрать кандидатов из клетки объекта и 8 соседних
function getNearby(grid, e) {
  const col = Math.floor(e.x / CELL_SIZE);
  const row = Math.floor(e.y / CELL_SIZE);
  const nearby = [];
  for (let dc = -1; dc <= 1; dc++) {
    for (let dr = -1; dr <= 1; dr++) {
      const key = (col + dc) + ',' + (row + dr);
      if (grid[key]) nearby.push(...grid[key]);
    }
  }
  return nearby;
}

// цыплёнок проверяет только ближних
const nearby = getNearby(grid, chicken);
for (const other of nearby) {
  if (other === chicken) continue; // сам с собой не сталкиваемся
  if (hit(chicken, other)) {
    console.log('Цыплёнок задел монетку!');
  }
}

Результат: цыплёнок проверит столкновение всего с двумя ближними монетками из клетки "1,1" и поймает обе, что окажутся в радиусе. Дальняя монетка в клетке "8,6" в список nearby вообще не попадёт — на неё не уйдёт ни одной проверки. Если эти прямоугольники пересекаются, в консоль улетит «Цыплёнок задел монетку!».

Почему именно 9 клеток

Два вложенных цикла с dc и dr от −1 до 1 дают 9 комбинаций: центральная клетка плюс 8 вокруг. Зачем соседи, если объект и так лежит в своей клетке? Потому что объект может стоять у самого края клетки, а его половина — торчать в соседнюю. Если бы цыплёнок смотрел только в свою клетку, он бы прозевал монетку, которая зацепилась за границу. Девять клеток гарантируют, что мы не пропустим столкновение на стыке — при условии, что объект не больше клетки.

Обрати внимание на спред-оператор ...grid[key] внутри push. Он разворачивает массив объектов из соседней клетки и добавляет их по одному в общий список nearby. Без трёх точек ты бы запихнул в nearby вложенный массив целиком, и цикл for...of споткнулся бы об него. Ещё важна проверка if (grid[key]): если соседняя клетка пустая, в словаре её просто нет, и обращение вернёт undefined — мы аккуратно пропускаем такую клетку, а не падаем с ошибкой.

И последний штрих — строчка if (other === chicken) continue. Цыплёнок ведь тоже лежит в своей клетке, и без этой проверки он сравнил бы себя с самим собой. Прямоугольник всегда пересекается сам с собой, так что мы бы получили ложное «столкновение» каждый кадр. Сравнение по === сверяет, что это буквально один и тот же объект в памяти, и честно его пропускает.

Пример 3. Сетка внутри игрового цикла

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

function update(entities) {
  // 1. пересобираем сетку под новые позиции
  const grid = buildGrid(entities);

  // 2. для каждого объекта проверяем только соседей
  for (const e of entities) {
    const nearby = getNearby(grid, e);
    for (const other of nearby) {
      if (other === e) continue;
      if (hit(e, other)) {
        resolveCollision(e, other);
      }
    }
  }
}

function loop() {
  update(world); // world — массив всех монеток, врагов и цыплёнка
  draw();
  requestAnimationFrame(loop);
}
requestAnimationFrame(loop);

Результат: на экране цыплёнок бегает среди сотни монеток, собирает их при касании, врезается во врагов — и всё это плавно, на стабильных 60 FPS. Внешне игра выглядит ровно так же, как при наивной проверке «все со всеми», но под капотом она делает в десятки раз меньше работы, потому что каждый объект общается лишь с горсткой соседей.

Сколько мы сэкономили

При 1000 объектов наивный способ давал почти 500 000 проверок за кадр. Если объекты распределены по сетке более-менее равномерно и в каждой клетке сидит, скажем, по 4 объекта, то каждый проверяется примерно с парой десятков соседей — это около 20 000 проверок вместо полумиллиона. В 25 раз меньше. Цыплёнок выдыхает.

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

Где сетка не панацея

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

Частые ошибки и подводные камни

Слишком маленькая клетка. Если клетка меньше объекта, цыплёнок займёт сразу несколько клеток, и проверки 9 соседей перестанет хватать — столкновения начнут проскакивать. Правило: размер клетки делай не меньше самого крупного объекта в игре. Обычно берут размер примерно с самого большого героя или чуть больше.
Слишком большая клетка. Перегнёшь в другую сторону — и в одну гигантскую клетку набьются все объекты сразу. Тогда сетка превращается обратно в «все со всеми» и не ускоряет ничего. Ищи золотую середину экспериментом: меняй CELL_SIZE и смотри на FPS.
Забыл пересобрать сетку. Если построить сетку один раз при старте и больше не трогать, объекты разъедутся, а их адреса в сетке останутся старыми. Цыплёнок будет «сталкиваться» с пустотой и пролетать сквозь монетки. Сетка должна перестраиваться каждый кадр в начале update.
Двойная обработка пары. Когда цыплёнок проверяет монетку и находит столкновение, а потом монетка в свою очередь проверяет цыплёнка — пара обрабатывается дважды. Для сбора монеток это часто безвредно, но для физического отскока может глючить. Чтобы избежать, обрабатывай пару только если id одного объекта меньше id другого.
Отрицательные координаты. Если у тебя есть камера и мир уходит в минус, Math.floor для отрицательных чисел работает правильно (округляет к меньшему), но строки-ключи вроде "-1,2" легко перепутать при отладке. Проверь, что у тебя нигде не parseInt теряет минус.

Мини-практика: счётчик проверок

Лучший способ почувствовать выигрыш — увидеть его в цифрах. Сделай так:

Заведи переменную checks = 0 и увеличивай её на единицу при каждом вызове hit().
Сначала посчитай проверки наивным способом: два вложенных цикла по всем объектам, без сетки. Выведи число в консоль.
Теперь посчитай проверки через сетку из примера 3. Снова выведи число.
Накидай в world 200 монеток со случайными координатами и сравни два числа. Разница тебя порадует.

Бонус для самых дерзких: добавь на canvas рисование самой сетки — полупрозрачные линии через каждые CELL_SIZE пикселей и подсветку клетки, в которой сейчас находится цыплёнок. Так ты буквально увидишь, как герой переезжает из клетки в клетку, и поймёшь алгоритм нутром, а не по формулам.

Итоги

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

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

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