---
title: "Пространственное хеширование: столкновения сотен объектов без проверки «каждый с каждым»"
description: "Как ускорить столкновения в браузерной 2D-игре пространственным хешем: клетки фиксированного размера, ключ клетки в одном числе, объект в нескольких клетках и проверка каждой пары один раз. Замер в Node.js 24: 2000 объектов — 1 999 000 проверок перебором против 22 636 через хеш, 10,3 мс против 0,8 мс; как выбрать размер клетки и когда хеш не нужен."
slug: prostranstvennoe-heshirovanie-stolknoveniya-soten-obektov-bez-perebora
date: 2026-11-12
updated: 2026-11-12
scheduled_at: "2026-11-12T09:00:00+03:00"
rubric: ustrojstvo-2d-igr
tags: ["fizika", "optimizaciya", "algoritmy", "javascript", "profi"]
reading_time: 16
draft: false
summary: "Проверка «каждый с каждым» требует n·(n − 1)/2 сравнений: для 2000 объектов это 1 999 000 проверок и около 10 мс в нашем замере — больше половины кадра при 60 FPS. Пространственный хеш раскладывает объекты по клеткам фиксированного размера и сравнивает только соседей по клетке: те же 3569 пар нашлись за 22 636 проверок и 0,8 мс. Главная настройка — размер клетки: в нашем прогоне с объектами 8–32 px лучшие клетки 32–64 px, а при 200 объектах хеш уже не быстрее простого перебора."
---

## Коротко

Проверка «каждый с каждым» требует `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`, и объект попадает в клетку с координатами:

```text
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-битное без совпадений:

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

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

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

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

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

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

```js
// 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):

```text
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: проверок | Хеш, мс |
|---|---|---|---|---|---|
| 200 | 40 | 19 900 | 0,1 | 220 | 0,1 |
| 1000 | 882 | 499 500 | 2,4 | 5663 | 0,26 |
| 2000 | 3569 | 1 999 000 | 10,3 | 22 636 | 0,8 |
| 5000 | 21 993 | 12 497 500 | 68 | 139 892 | 4,1 |

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

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

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

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

| Клетка, px | Непустых клеток | Записей объектов | Проверок | Время, мс |
|---|---|---|---|---|
| 8 | 11 502 | 24 483 | 5121 | 2,8 |
| 16 | 3328 | 10 099 | 6964 | 1,2 |
| 32 | 911 | 5252 | 11 262 | 0,8 |
| 64 | 240 | 3405 | 22 636 | 0,8 |
| 128 | 60 | 2600 | 56 015 | 1,1 |
| 256 | 15 | 2244 | 168 526 | 2,6 |
| 1024 | 2 | 2032 | 1 384 769 | 13 |

Меньше всего проверок у клетки 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-физика и столкновения входят в проверенные внутри разработки основы. Движок в разработке и публично пока не открыт, заявку можно оставить на [странице раннего доступа](/early-access?utm_source=blog&utm_medium=article&utm_campaign=prostranstvennoe-heshirovanie-stolknoveniya-soten-obektov-bez-perebora) (подача заявки не гарантирует приглашение).

**Источники (проверено: 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](https://cgl.ethz.ch/Downloads/Publications/Papers/2003/Tes03/Tes03.pdf) (хеш-функция с простыми числами 73856093, 19349663, 83492791 и `mod n`; размер клетки влияет сильнее размера таблицы и хеш-функции, лучший — средняя длина ребра; пометка шагом симуляции вместо очистки таблицы). Все числа проверок и времени, размеры объектов, сценарий и рецепт выбора клетки — наш прогон в Node.js 24.22.1 и наш ориентир.

**Читайте также:**
- [Игровой цикл (Game Loop) и физика столкновений (AABB, хитбоксы и триггеры) простыми словами и на уровне профи](/blog/igrovoj-cikl-i-fizika-stolknovenij-aabb)
- [Как найти просадку FPS в браузерной 2D-игре: бюджет кадра, Chrome DevTools Performance, долгие задачи и сборка мусора](/blog/prosadki-fps-v-brauzernoj-igre-chrome-devtools-performance)
- [Спавн и удаление объектов в 2D-игре: время жизни, отложенное удаление и пулы](/blog/spavn-i-udalenie-obektov-v-2d-igre-vremya-zhizni-i-puly)
