Коротко
Проверка «каждый с каждым» требует n·(n − 1)/2 сравнений: для 2000 объектов это 1 999 000 проверок и около 10 мс в нашем замере — больше половины кадра при 60 FPS. Пространственный хеш раскладывает объекты по клеткам фиксированного размера и сравнивает только соседей по клетке: те же 3569 пар нашлись за 22 636 проверок и 0,8 мс. Главная настройка — размер клетки: в нашем прогоне с объектами 8–32 px лучшие клетки 32–64 px, а при 200 объектах хеш уже не быстрее простого перебора.
Содержание
- Почему «каждый с каждым» не масштабируется
- Как работает пространственный хеш
- Ключ клетки: упаковка или хеш-функция
- Код на JavaScript и проверка в Node.js
- Сколько это экономит: замер
- Размер клетки решает больше всего
- Хешируйте меньшую группу
- Практический сценарий: аркада с 1500 пулями
- Когда вам это не подойдёт
Почему «каждый с каждым» не масштабируется
Перебор всех пар растёт квадратично: при 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: проверок | Хеш, мс |
|---|---|---|---|---|---|
| 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 на том же ноутбуке. Шаги:
- Разделить группы. Пули игрока проверяются только с врагами, вражеские пули — только с героем. Пули между собой не сталкиваются.
- Вражеские пули — без хеша. 200 проверок с одним героем — это перебор, который дешевле любой таблицы.
- Пули игрока — через хеш врагов. Клетка 64 px (враги 32 px), хеш пересобирается раз в кадр; 450 000 проверок превращаются примерно в 5000.
- Отдельно — крупные объекты. Босс 400 × 300 px попал бы в 35–48 клеток по 64 px; его проверяют напрямую с пулями, не кладя в хеш.
- Проверка. Записать профиль той же волны до и после и сравнить время функции столкновений и частоту кадров. Как снимать профиль и читать дорожку 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 и наш ориентир.
Читайте также:
- Игровой цикл (Game Loop) и физика столкновений (AABB, хитбоксы и триггеры) простыми словами и на уровне профи
- Как найти просадку FPS в браузерной 2D-игре: бюджет кадра, Chrome DevTools Performance, долгие задачи и сборка мусора
- Спавн и удаление объектов в 2D-игре: время жизни, отложенное удаление и пулы