Пространственное хеширование: столкновения сотен объектов без проверки «каждый с каждым»

Коротко

Проверка «каждый с каждым» требует n·(n − 1)/2 сравнений: для 2000 объектов это 1 999 000 проверок и около 10 мс в нашем замере — больше половины кадра при 60 FPS. Пространственный хеш раскладывает объекты по клеткам фиксированного размера и сравнивает только соседей по клетке: те же 3569 пар нашлись за 22 636 проверок и 0,8 мс. Главная настройка — размер клетки: в нашем прогоне с объектами 8–32 px лучшие клетки 32–64 px, а при 200 объектах хеш уже не быстрее простого перебора.

Содержание

  1. Почему «каждый с каждым» не масштабируется
  2. Как работает пространственный хеш
  3. Ключ клетки: упаковка или хеш-функция
  4. Код на JavaScript и проверка в Node.js
  5. Сколько это экономит: замер
  6. Размер клетки решает больше всего
  7. Хешируйте меньшую группу
  8. Практический сценарий: аркада с 1500 пулями
  9. Когда вам это не подойдёт

Почему «каждый с каждым» не масштабируется

Перебор всех пар растёт квадратично: при n объектах нужно n·(n − 1)/2 проверок, поэтому вдвое больше объектов — вчетверо больше работы. Для 200 объектов это 19 900 проверок, для 2000 — 1 999 000, для 5000 — 12 497 500.

При 60 кадрах в секунду на весь кадр есть 1000 / 60 ≈ 16,7 мс, и в них должны поместиться логика, отрисовка и работа браузера. В нашем замере перебор 2000 объектов занял около 10 мс, 5000 — около 68 мс: игра с такими столкновениями не удержит и 15 кадров в секунду. Сама проверка пересечения прямоугольников (AABB) при этом дешёвая — дорого их количество. Как устроена проверка AABB и игровой цикл, разобрано в статье про игровой цикл и физику столкновений; здесь мы ускоряем то, что идёт до неё.

Как работает пространственный хеш

Пространственный хеш делит поиск столкновений на две фазы: широкая быстро отбирает пары, которые могут пересекаться, а узкая проверяет только их. Мир делят на квадратные клетки размера s, и объект попадает в клетку с координатами:

cx = floor(x / s)
cy = floor(y / s)

Объект записывают во все клетки, которые задевает его прямоугольник: от floor(x / s) до floor((x + w) / s) по горизонтали и так же по вертикали. Маленький объект попадает в 1 клетку, объект на границе — в 2 или 4. Потом для каждого объекта берут соседей по его клеткам и проверяют только их.

Две детали делают хеш правильным:

  • Каждая пара — один раз. Объекты A и B могут лежать вместе в нескольких клетках. Поэтому пару проверяют, только если индекс B больше индекса A, а массив-отметка stamp[B] = A не даёт проверить её повторно из соседней клетки.
  • Пересборка каждый кадр. Объекты двигаются, поэтому таблицу очищают и заполняют заново. Время пересборки входит во все наши замеры ниже.

В статье Teschner и соавторов (ETH Zurich, конференция VMV 2003) хеш-таблицу не очищают каждый шаг, а помечают записи номером шага симуляции: старая запись считается пустой. Для браузерной игры с сотнями объектов хватает Map.clear(), но если пересборка видна в профайлере, это следующий шаг оптимизации.

Ключ клетки: упаковка или хеш-функция

Ключ клетки — одно число из двух координат, чтобы Map искала клетку быстро и без склейки строк. Если мир не больше 32 768 клеток в каждую сторону от нуля, два 16-битных числа упаковываются в одно 32-битное без совпадений:

key = ((cx & 0xffff) << 16) | (cy & 0xffff)

При клетке 64 px это мир около 2 млн пикселей в каждую сторону — для 2D-игры с запасом. В статье Teschner и соавторов для бесконечного мира и таблицы фиксированного размера n использована хеш-функция с тремя большими простыми числами (для 3D):

hash(x, y, z) = (x · 73856093  xor  y · 19349663  xor  z · 83492791)  mod  n

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

Код на JavaScript и проверка в Node.js

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

// spatial-hash.js — пространственное хеширование для широкой фазы столкновений
export class SpatialHash {
  constructor(cellSize) {
    this.size = cellSize;
    this.cells = new Map();                    // ключ клетки -> индексы объектов
  }
  key(cx, cy) {                                // уникален, пока |cx| и |cy| < 32768
    return ((cx & 0xffff) << 16) | (cy & 0xffff);
  }
  range(o) {                                   // клетки, которые задевает AABB
    const s = this.size;
    return [Math.floor(o.x / s), Math.floor((o.x + o.w) / s),
            Math.floor(o.y / s), Math.floor((o.y + o.h) / s)];
  }
  rebuild(objs) {
    this.cells.clear();
    objs.forEach((o, i) => {
      const [x0, x1, y0, y1] = this.range(o);
      for (let cx = x0; cx <= x1; cx++)
        for (let cy = y0; cy <= y1; cy++) {
          const k = this.key(cx, cy);
          const list = this.cells.get(k);
          if (list) list.push(i); else this.cells.set(k, [i]);
        }
    });
  }
}

export function overlap(a, b) {                // узкая фаза: пересечение AABB
  return a.x < b.x + b.w && b.x < a.x + a.w && a.y < b.y + b.h && b.y < a.y + a.h;
}

export function pairsHashed(objs, grid, stats) {
  grid.rebuild(objs);
  const stamp = new Int32Array(objs.length).fill(-1); // stamp[j] === i: пару (i, j) уже смотрели
  const pairs = [];
  objs.forEach((a, i) => {
    const [x0, x1, y0, y1] = grid.range(a);
    for (let cx = x0; cx <= x1; cx++)
      for (let cy = y0; cy <= y1; cy++) {
        const list = grid.cells.get(grid.key(cx, cy));
        for (const j of list) {
          if (j <= i || stamp[j] === i) continue; // каждую пару — один раз
          stamp[j] = i;
          stats.checks++;
          if (overlap(a, objs[j])) pairs.push([i, j]);
        }
      }
  });
  return pairs;
}

export function pairsBrute(objs, stats) {      // «каждый с каждым»: n·(n−1)/2 проверок
  const pairs = [];
  for (let i = 0; i < objs.length; i++)
    for (let j = i + 1; j < objs.length; j++) {
      stats.checks++;
      if (overlap(objs[i], objs[j])) pairs.push([i, j]);
    }
  return pairs;
}


// ---- проверка в Node.js: те же пары, меньше проверок ----
function mulberry32(seed) {                    // генератор с зерном — мир одинаков при каждом запуске
  return () => {
    seed |= 0; seed = (seed + 0x6D2B79F5) | 0;
    let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
function makeWorld(n, seed) {                  // n объектов 8–32 px на поле 1280×720
  const rnd = mulberry32(seed);
  return Array.from({ length: n }, () => {
    const w = 8 + Math.floor(rnd() * 25), h = 8 + Math.floor(rnd() * 25);
    return { x: rnd() * (1280 - w), y: rnd() * (720 - h), w, h };
  });
}
const same = (a, b) => a.length === b.length && a.every(([i, j], k) => i === b[k][0] && j === b[k][1]);
const byPair = (p, q) => p[0] - q[0] || p[1] - q[1];
for (const n of [200, 1000, 2000, 5000]) {
  const objs = makeWorld(n, 2026), sb = { checks: 0 }, sh = { checks: 0 };
  const pb = pairsBrute(objs, sb).sort(byPair);
  const ph = pairsHashed(objs, new SpatialHash(64), sh).sort(byPair);
  console.log(`n=${n}: пар ${pb.length}, перебор ${sb.checks}, хеш ${sh.checks}, совпадают: ${same(pb, ph)}`);
}

Ожидаемый вывод (проверено в Node.js 24.22.1, 11.11.2026):

n=200: пар 40, перебор 19900, хеш 220, совпадают: true
n=1000: пар 882, перебор 499500, хеш 5663, совпадают: true
n=2000: пар 3569, перебор 1999000, хеш 22636, совпадают: true
n=5000: пар 21993, перебор 12497500, хеш 139892, совпадают: true

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

Сколько это экономит: замер

Числа проверок не зависят от машины, а время — зависит, поэтому время ниже — медиана 31 прогона на нашей машине (Node.js 24.22.1, сервер с процессором Intel Xeon, 11.11.2026), между запусками разброс до 20%:

ОбъектовПарПеребор: проверокПеребор, мсХеш 64 px: проверокХеш, мс
2004019 9000,12200,1
1000882499 5002,456630,26
200035691 999 00010,322 6360,8
500021 99312 497 50068139 8924,1

При 200 объектах проверок в 90 раз меньше, а времени столько же: работа с Map и массивами клеток съедает выигрыш. Хеш окупается, когда объектов становится несколько сотен; при 2000 он быстрее примерно в 13 раз, при 5000 — примерно в 16.

Размер клетки решает больше всего

Размер клетки определяет, сколько объектов попадёт в одну клетку и в сколько клеток попадёт один объект. Слишком мелкие клетки — объект записан в 4–9 клеток, таблица раздувается; слишком крупные — в клетке десятки объектов, и внутри неё снова перебор. Teschner и соавторы пришли к тому же: размер клетки влияет на скорость сильнее, чем размер таблицы и хеш-функция, и в их задаче лучшим оказался размер, равный средней длине ребра объекта.

Наш прогон: 2000 объектов размером 8–32 px (в среднем 20 px) на поле 1280 × 720 px.

Клетка, pxНепустых клетокЗаписей объектовПроверокВремя, мс
811 50224 48351212,8
16332810 09969641,2
32911525211 2620,8
64240340522 6360,8
12860260056 0151,1
256152244168 5262,6
1024220321 384 76913

Меньше всего проверок у клетки 8 px, но она медленнее всех разумных вариантов: на 2000 объектов приходится 24 483 записи. Лучшее время — у клеток 32–64 px, то есть в 1,5–3 раза больше среднего объекта. Рецепт: начать с размера, вдвое большего типичного объекта, и подвинуть его на шаг в обе стороны, глядя на время, а не на число проверок.

Хешируйте меньшую группу

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

Наш прогон: 1500 пуль 8 × 8 px и 300 врагов 32 × 32 px на поле 1280 × 720 px. Перебор «каждая пуля с каждым врагом» — 450 000 проверок. Хеш из 300 врагов с клеткой 64 px и запросы от каждой пули — 5095 проверок, попаданий в обоих случаях 821. Запрос пули устроен так же, как цикл в pairsHashed: взять клетки её прямоугольника и проверить врагов из них, отмечая уже проверенных в stamp.

Практический сценарий: аркада с 1500 пулями

Задача: в браузерной аркаде на поздней волне 1500 пуль игрока, 300 врагов и 200 вражеских пуль, и частота падает до 40 кадров в секунду; в профайлере самая широкая функция — столкновения. Цель — вернуть 60 FPS на том же ноутбуке. Шаги:

  1. Разделить группы. Пули игрока проверяются только с врагами, вражеские пули — только с героем. Пули между собой не сталкиваются.
  2. Вражеские пули — без хеша. 200 проверок с одним героем — это перебор, который дешевле любой таблицы.
  3. Пули игрока — через хеш врагов. Клетка 64 px (враги 32 px), хеш пересобирается раз в кадр; 450 000 проверок превращаются примерно в 5000.
  4. Отдельно — крупные объекты. Босс 400 × 300 px попал бы в 35–48 клеток по 64 px; его проверяют напрямую с пулями, не кладя в хеш.
  5. Проверка. Записать профиль той же волны до и после и сравнить время функции столкновений и частоту кадров. Как снимать профиль и читать дорожку Main, разобрано в статье про просадки FPS.

Проверяемый результат — время функции столкновений в профиле до и после и устойчивые 60 FPS на поздней волне; если частота не выросла, узкое место было не в столкновениях.

Когда вам это не подойдёт

Пространственный хеш нужен не всегда:

  • Объектов меньше пары сотен. В нашем замере при 200 объектах хеш не быстрее перебора, а кода и мест для ошибок больше.
  • Все в одной куче. 2000 объектов в квадрате 200 × 200 px с клеткой 64 px дали 320 210 проверок — 16% от перебора вместо 1%: когда все рядом, хеш вырождается в перебор внутри нескольких клеток.
  • Очень разные размеры. Один огромный объект в десятках клеток и сотни мелких — крупные проверяют отдельно, а не подбирают клетку под всех.
  • Неподвижная карта уровня. Стены и платформы из тайлов уже лежат в сетке: клетку героя находят делением координат, хеш для них не нужен.
  • Готовый физический движок. Если столкновения считает сторонняя библиотека, сначала проверьте, есть ли в ней своя широкая фаза: дублировать её своим хешем — двойная работа.

Мы разрабатываем J2DRU — браузерный 2D игровой движок, где 2D-физика и столкновения входят в проверенные внутри разработки основы. Движок в разработке и публично пока не открыт, заявку можно оставить на странице раннего доступа (подача заявки не гарантирует приглашение).

Источники (проверено: 11.11.2026): M. Teschner, B. Heidelberger, M. Müller, D. Pomeranets, M. Gross — «Optimized Spatial Hashing for Collision Detection of Deformable Objects», VMV 2003, ETH Zurich (хеш-функция с простыми числами 73856093, 19349663, 83492791 и mod n; размер клетки влияет сильнее размера таблицы и хеш-функции, лучший — средняя длина ребра; пометка шагом симуляции вместо очистки таблицы). Все числа проверок и времени, размеры объектов, сценарий и рецепт выбора клетки — наш прогон в Node.js 24.22.1 и наш ориентир.

Читайте также:

Частые вопросы

Что такое пространственное хеширование?

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

С какого числа объектов хеш начинает помогать?

В нашем замере при 200 объектах хеш и перебор заняли примерно по 0,1 мс, при 1000 — 0,26 мс против 2,4 мс, при 2000 — 0,8 мс против 10,3 мс. Если объектов меньше пары сотен, перебор проще и не медленнее.

Какой размер клетки выбрать?

Начните с 1–3 средних размеров объекта и проверьте замером. В нашем прогоне с объектами 8–32 px клетки 32 и 64 px дали лучшее время, 8 px — в 3,5 раза хуже, 1024 px — в 17 раз хуже.

Чем пространственный хеш отличается от тайловой сетки?

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