Коротко
Циклы в логике кадра пишут так, чтобы они заканчивались как можно раньше: при 60 Гц на весь кадр есть 16,7 мс, при 144 Гц — 6,9 мс. Для этого дешёвые и часто ложные проверки ставят перед дорогими и выходят через return или continue при первой неудаче, поиск обрывают через break, вложенный цикл «каждый с каждым» начинают с j = i + 1, а удаляют из массива с конца. Дорогую работу, которая не обязана идти каждый кадр, раздают частями по круговому индексу, а у каждого while, который ждёт удачи, ставят предохранитель — предел числа попыток.
Содержание
- Сколько времени есть у кадра
- Ранний выход: return и continue
- break: остановиться, когда нашли
- Вложенные циклы и рост числа проверок
- Удаление из массива во время обхода
- Дорогая работа по частям
- Предохранитель для while
- Код на JavaScript
- Проверка в Node.js
- Что показал прогон: четыре ловушки
- Время в миллисекундах
- Что не подтвердилось
- Практический сценарий: 600 врагов думают в одном кадре
- Когда вам это не подойдёт
Сколько времени есть у кадра
У кадра при 60 Гц есть 1000 / 60 = 16,7 мс, и в них должны уложиться логика игры, отрисовка и работа самого браузера. MDN пишет, что requestAnimationFrame обычно вызывает функцию кадра с частотой обновления экрана: чаще всего это 60 Гц, но распространены и 75, 120 и 144 Гц. На 120 Гц кадр длится 8,3 мс, на 144 Гц — 6,9 мс.
бюджет кадра, мс = 1000 / частота экрана, Гц
60 Гц → 16,7 мс
120 Гц → 8,3 мс
144 Гц → 6,9 мс
Сколько из этого времени реально остаётся на вашу логику и как найти кадр, который не уложился, разобрано в статье про просадки FPS и Chrome DevTools. Как устроен сам игровой цикл с фиксированным шагом, — в статье про игровой цикл и AABB. Здесь — про то, что происходит внутри одного шага: циклы по объектам и условия в них.
Время мы почти не меряем, а считаем операции: сколько раз выполнилась проверка, сколько клеток прошёл луч, сколько пар сравнил цикл. Такие числа одинаковы на любом компьютере и при каждом запуске, а миллисекунды зависят от машины. Замер времени — отдельно, в разделе «Время в миллисекундах».
Ранний выход: return и continue
Ранний выход — это прекратить работу над объектом сразу после первой проверки, которая не прошла: return false из функции или continue в цикле. По MDN, continue завершает текущий проход цикла и переходит к следующему, то есть остальной код для этого объекта не выполняется.
Пример из прогона: 400 врагов на карте 640×480 px, и каждый кадр нужно узнать, кто из них видит игрока. Условий три:
| Условие | Что делает | Цена |
|---|---|---|
враг бодрствует (awake) | читает флаг; бодрствуют 121 из 400 | одно сравнение |
игрок ближе 160 px (near) | сравнивает квадрат расстояния с квадратом радиуса | два умножения и сложение |
между ними нет стены (los) | идёт лучом с шагом 4 px и смотрит клетку карты под каждой точкой | десятки клеток на врага |
Проверка обзора дорогая: она идёт от врага к игроку и смотрит клетку карты под каждой точкой, пока не упрётся в стену. Если поставить её первой, она выполнится для всех 400 врагов. Если сначала отсеять спящих и далёких, — только для тех, кто прошёл обе дешёвые проверки.
плохо: если нет_стены(враг, игрок) и близко(враг, игрок) и бодрствует(враг) → видит
хорошо: если не бодрствует(враг) → нет (ранний выход)
если не близко(враг, игрок) → нет (ранний выход)
если стена(враг, игрок) → нет
иначе → видит
Порядок условий
Условия ставят так: сначала дешёвые и часто ложные, в конце — дорогие. Это работает и внутри одного if: по MDN, оператор && вычисляет операнды слева направо и сразу возвращает первый ложный, поэтому в a && b && c условие c выполняется только для тех, у кого a и b истинны. Результат от порядка не меняется — меняется только объём работы.
В нашем прогоне все три порядка нашли одних и тех же 36 врагов, которые видят игрока. Обзор первым — 400 вызовов и 12821 клетка; обзор последним — 38 вызовов и 1040 клеток. Порядок двух дешёвых условий между собой дал 536 и 521 дешёвую проверку — разница мала, и об этом в разделе «Что не подтвердилось».
Ветвления тоже бывают дорогими, когда их много: длинная цепочка if по флагам вроде «прыгает», «падает», «атакует» в каждом объекте растёт с каждой новой механикой. Как заменить её состояниями, мы разбирали в статье про конечный автомат персонажа.
break: остановиться, когда нашли
Если цикл ищет хотя бы один подходящий объект, после находки его обрывают через break. По MDN, break завершает текущий цикл и передаёт управление следующей за ним строке. Тот же смысл у return из функции поиска и у методов массива some и find.
В прогоне 200 раз спрашивали, есть ли хоть один из 400 врагов в радиусе от точки. Без break — 80000 проверок при любом радиусе: цикл всегда доходит до конца. С break при радиусе 40 px — 14464 проверки: враг нашёлся в 196 точках из 200, и обычно рано. При радиусе 12 px враг нашёлся только в 81 точке, и break сократил работу до 62775 проверок: там, где искать нечего, цикл всё равно проходит весь список.
есть_ли_рядом(список, точка, r):
для каждого врага:
если расстояние² ≤ r² → вернуть «да» (дальше не смотрим)
вернуть «нет» (просмотрели всех)
break выходит только из одного, ближайшего цикла. Если поиск идёт во вложенных циклах, удобнее вынести его в функцию и выйти через return.
Вложенные циклы и рост числа проверок
Цикл внутри цикла «каждый с каждым» делает число проверок, которое растёт быстрее числа объектов: при j от i + 1 их n·(n − 1)/2. В прогоне с кругами радиусом 8 px: 50 кругов — 1225 проверок, 100 — 4950, 300 — 44850, 600 — 179700.
for i от 0 до n − 1:
for j от i + 1 до n − 1: ← не от 0: пару (i, j) не смотрим дважды, себя — вообще
проверить(i, j)
проверок = n·(n − 1)/2
Если внутренний цикл начать с нуля, проверок становится n·n: 2500 для 50 кругов вместо 1225. Это не только вдвое больше работы, но и неверный ответ — о нём в ловушке 2. Когда объектов сотни и перебор не помещается в кадр, проверяют только соседей через пространственное хеширование.
Удаление из массива во время обхода
Удалять элементы из массива прямо в цикле вперёд нельзя: splice сдвигает все следующие элементы на место удалённого, а индекс цикла всё равно растёт, и сосед удалённого пропускается. По MDN, splice меняет сам массив, удаляя или заменяя элементы на месте.
В прогоне игрок стоит в точке 150 и дотягивается на 22 px, а монеты лежат через каждые 10 px. Собрать он должен 5 монет — 130, 140, 150, 160 и 170. Цикл вперёд со splice убрал только 3: после каждой удалённой монеты следующая сдвигалась и пропускалась, и 140 и 160 остались лежать. Цикл с конца убрал все 5: удаление сдвигает только те элементы, которые уже просмотрены.
Обход с конца — самый короткий способ. Флаг «удалить» с уборкой после обхода, swap-and-pop и пулы объектов разобраны в статье про спавн и удаление объектов.
Дорогая работа по частям
Работу, которая не обязана идти каждый кадр, раздают частями: в каждом кадре её делают для 50 объектов, а следующий кадр продолжает с того места, где остановился предыдущий. Место хранят в круговом индексе: дошли до конца списка — начинаем с нуля.
состояние: next = 0
каждый кадр:
повторить min(50, длина списка) раз:
если next ≥ длина списка: next = 0 ← список мог укоротиться
обдумать(список[next])
next += 1
В прогоне 600 врагов, у каждого «обдумывание» стоит 40 операций, а на 60-м из 120 кадров 150 врагов погибают. Если думают все каждый кадр, пик — 24000 операций за кадр. По 50 за кадр — пик 2000 операций, а дольше всех враг ждал своей очереди 11 кадров. Цена — задержка реакции: враг замечает перемену не сразу, а в свою очередь. Так же разносят по кадрам решения врагов в статье про Utility AI; здесь — сам приём с индексом и его ошибки.
Бюджет по времени вместо числа
Вместо «50 за кадр» можно задать бюджет в миллисекундах: обрабатывать объекты, пока не кончилось, например, 2 мс, и продолжать в следующем кадре. Время в браузере берут из performance.now(): по MDN, он возвращает время в миллисекундах с дробной частью, но в обычной странице его точность огрублена до 100 мкс.
У такого бюджета есть плюс: на медленной машине объектов за кадр становится меньше, а кадр не растягивается. В нашем коде часы передаются в функцию снаружи, поэтому тест подставляет свои, детерминированные: 40 операций — 0,04 мс, а с 60-го кадра вдвое дольше, как на медленной машине. Результат — от 25 до 50 обдумываний за кадр и ожидание до 17 кадров. В игре вместо часов теста передают performance.now.
Предохранитель для while
У каждого while, который крутится «пока не повезёт», должен быть предел числа попыток и понятный ответ «не нашли». Типичный пример — поиск свободной клетки наугад для бонуса или врага: пока клетка занята, выбираем другую.
свободная_клетка_наугад(поле, предел):
попыток = 0
пока попыток < предел:
попыток += 1
c = случайная клетка
если c свободна → вернуть c
вернуть «не нашли» ← без этой строки цикл на полном поле вечный
На поле 10×10, где занята половина клеток, 100 запросов наугад потратили 200 попыток. При 90 занятых — 826, при 99 — 8843, а худший запрос — 541 попытку. Когда заняты все 100, без предела цикл не закончится никогда и вкладка зависнет; с пределом 1000 каждый из 100 запросов вернул «не нашли».
Второй путь — не гадать, а собрать список свободных клеток за один проход и выбрать из него: 100 проверок на запрос при любом заполнении, 10000 на 100 запросов. На полупустом поле это дороже, чем наугад, зато время не зависит от удачи, а пустой список сразу означает «мест нет».
Случайные числа в нашем коде берутся из своего генератора с зерном, поэтому числа прогона повторяются; почему для игр это полезно, — в статье про случайность без несправедливости.
Код на JavaScript
Пример — два файла: loops.mjs с функциями и test.mjs, который прогоняет шесть сцен и печатает счётчики. Нужен Node.js 24; запуск — node test.mjs в папке с файлами. Время не меряется, случайность — из генератора с зерном, поэтому вывод повторяется байт в байт. Третий файл, timing.mjs, меряет миллисекунды и в детерминированный вывод не входит.
Опции включают ошибки для ловушек: порядок ["los", "near", "awake"] в sees — дорогая проверка первой, режим "full" в overlaps — внутренний цикл с нуля, reset в thinkSome — индекс с нуля в каждом кадре, collect(…, "forward") — удаление вперёд со splice.
// loops.mjs — циклы и ветвления в логике кадра; счётчики операций вместо часов, своё зерно
export const W = 640;
export const H = 480;
export const TILE = 16;
// Генератор с зерном: одни и те же числа при каждом запуске
export function makeRng(seed) {
let s = seed >>> 0;
return () => {
s = (Math.imul(s, 1664525) + 1013904223) >>> 0;
return s / 4294967296;
};
}
// Карта стен 40×30 клеток: рамка и несколько отрезков стен
export function makeWalls() {
const cols = W / TILE;
const rows = H / TILE;
const walls = new Uint8Array(cols * rows);
for (let x = 0; x < cols; x++) { walls[x] = 1; walls[(rows - 1) * cols + x] = 1; }
for (let y = 0; y < rows; y++) { walls[y * cols] = 1; walls[y * cols + cols - 1] = 1; }
for (let y = 6; y < 24; y++) walls[y * cols + 14] = 1;
for (let x = 22; x < 34; x++) walls[10 * cols + x] = 1;
for (let x = 6; x < 18; x++) walls[20 * cols + x] = 1;
return { cols, rows, walls };
}
export function makeEnemies(n, seed) {
const rnd = makeRng(seed);
const list = [];
for (let i = 0; i < n; i++) {
list.push({ id: i, x: 24 + rnd() * (W - 48), y: 24 + rnd() * (H - 48), awake: rnd() < 0.3, dead: false });
}
return list;
}
// Дорогая проверка: идём от врага к игроку шагом 4 px и смотрим клетку под каждой точкой
export function lineOfSight(map, ax, ay, bx, by, ops) {
ops.losCalls += 1;
const n = Math.max(1, Math.ceil(Math.hypot(bx - ax, by - ay) / 4));
for (let k = 0; k <= n; k++) {
const x = ax + (bx - ax) * k / n;
const y = ay + (by - ay) * k / n;
ops.cells += 1;
if (map.walls[Math.floor(y / TILE) * map.cols + Math.floor(x / TILE)]) return false; // ранний выход
}
return true;
}
// Видит ли враг игрока: три условия, порядок задаётся списком
export function sees(map, e, p, order, ops) {
for (const c of order) {
if (c === "awake") { ops.cheap += 1; if (!e.awake) return false; }
if (c === "near") {
ops.cheap += 1;
const dx = p.x - e.x;
const dy = p.y - e.y;
if (dx * dx + dy * dy > 160 * 160) return false;
}
if (c === "los" && !lineOfSight(map, e.x, e.y, p.x, p.y, ops)) return false;
}
return true;
}
// Есть ли враг в радиусе r от точки: с break и без
export function anyInRadius(list, x, y, r, useBreak, ops) {
let found = false;
for (const e of list) {
ops.checks += 1;
const dx = e.x - x;
const dy = e.y - y;
if (dx * dx + dy * dy <= r * r) {
found = true;
if (useBreak) break;
}
}
return found;
}
// Пары «каждый с каждым»: half — j от i + 1, full — j от 0 (ошибка)
export function overlaps(list, r, mode, ops) {
let hits = 0;
for (let i = 0; i < list.length; i++) {
for (let j = mode === "half" ? i + 1 : 0; j < list.length; j++) {
ops.pairs += 1;
const dx = list[i].x - list[j].x;
const dy = list[i].y - list[j].y;
if (dx * dx + dy * dy <= 4 * r * r) hits += 1;
}
}
return hits;
}
// Сбор монет: удаление прямо во время обхода, вперёд и с конца
export function collect(coins, px, reach, dir) {
if (dir === "forward") {
for (let i = 0; i < coins.length; i++) {
if (Math.abs(coins[i] - px) <= reach) coins.splice(i, 1); // следующий сдвинулся на место i
}
} else {
for (let i = coins.length - 1; i >= 0; i--) {
if (Math.abs(coins[i] - px) <= reach) coins.splice(i, 1);
}
}
return coins;
}
// Дорогое «обдумывание» врага: 40 операций, запоминаем кадр
export function think(e, frame, ops) {
ops.think += 1;
ops.units += 40;
e.lastThink = frame;
}
// Часть врагов за кадр по круговому индексу; reset — ошибка: каждый кадр с нуля
export function thinkSome(list, state, perFrame, frame, ops, reset) {
if (reset) state.next = 0;
const n = Math.min(perFrame, list.length);
for (let k = 0; k < n; k++) {
if (state.next >= list.length) state.next = 0; // список мог укоротиться
think(list[state.next], frame, ops);
state.next += 1;
}
}
// Бюджет по времени: часы передаются снаружи — в игре performance.now, в тесте свои
export function thinkWithBudget(list, state, budgetMs, now, frame, ops) {
const start = now();
let done = 0;
while (done < list.length && now() - start < budgetMs) {
if (state.next >= list.length) state.next = 0;
think(list[state.next], frame, ops);
state.next += 1;
done += 1;
}
return done;
}
// Свободная клетка наугад: предохранитель maxTries против бесконечного цикла
export function randomFreeCell(taken, size, rnd, maxTries, ops) {
let tries = 0;
while (tries < maxTries) {
tries += 1;
ops.tries += 1;
const c = Math.floor(rnd() * size);
if (!taken[c]) return c;
}
ops.gaveUp += 1;
return -1;
}
// Без случайных попыток: собрать свободные клетки за один проход и выбрать одну
export function listFreeCell(taken, size, rnd, ops) {
const free = [];
for (let c = 0; c < size; c++) { ops.tries += 1; if (!taken[c]) free.push(c); }
if (free.length === 0) { ops.gaveUp += 1; return -1; }
return free[Math.floor(rnd() * free.length)];
}
// test.mjs — node test.mjs; вывод детерминирован: считаем операции, а не миллисекунды
import { makeRng, makeWalls, makeEnemies, sees, anyInRadius, overlaps, collect, think,
thinkSome, thinkWithBudget, randomFreeCell, listFreeCell } from "./loops.mjs";
const out = [];
const say = (s) => out.push(s);
const num = (x, d) => x.toFixed(d).replace(".", ",");
say("# 0. Бюджет кадра");
for (const hz of [60, 120, 144]) say(hz + " Гц: 1000 / " + hz + " = " + num(1000 / hz, 1) + " мс на кадр");
say("");
say("# 1. Видит ли враг игрока: карта 640×480 px, 400 врагов, игрок в (400,300), один кадр");
say("условия: бодрствует; ближе 160 px; луч с шагом 4 px без стен");
const map = makeWalls();
const enemies = makeEnemies(400, 74);
const player = { x: 400, y: 300 };
say("бодрствуют " + enemies.filter((e) => e.awake).length + " из 400");
for (const order of [["los", "near", "awake"], ["near", "awake", "los"], ["awake", "near", "los"]]) {
const ops = { cheap: 0, losCalls: 0, cells: 0 };
let seen = 0;
for (const e of enemies) if (sees(map, e, player, order, ops)) seen += 1;
say(order.join(" → ") + ": видят " + seen + ", дешёвых проверок " + ops.cheap + ", вызовов обзора " + ops.losCalls +
", клеток " + ops.cells);
}
say("");
say("# 2. Есть ли враг в радиусе: 200 точек, 400 врагов");
{
const rnd = makeRng(2026);
const points = [];
for (let i = 0; i < 200; i++) points.push([rnd() * 640, rnd() * 480]);
for (const r of [40, 12]) {
for (const useBreak of [false, true]) {
const ops = { checks: 0 };
let found = 0;
for (const [x, y] of points) if (anyInRadius(enemies, x, y, r, useBreak, ops)) found += 1;
say("r " + r + " px, " + (useBreak ? "с break" : "без break") + ": найдено в " + found + " точках, проверок " + ops.checks);
}
}
}
say("");
say("# 3. Каждый с каждым: круги r 8 px");
for (const n of [50, 100, 300, 600]) {
const list = makeEnemies(n, 7);
const a = { pairs: 0 };
const b = { pairs: 0 };
const half = overlaps(list, 8, "half", a);
const full = overlaps(list, 8, "full", b);
say("n " + n + ": j от i+1 — проверок " + a.pairs + ", касаний " + half + "; j от 0 — проверок " + b.pairs + ", касаний " + full);
}
say("");
say("# 4. Удаление во время обхода: 10 монет через 10 px, игрок в 150, дотягивается на 22 px");
say("монеты: 100, 110, 120, 130, 140, 150, 160, 170, 180, 190");
for (const dir of ["forward", "backward"]) {
const coins = [100, 110, 120, 130, 140, 150, 160, 170, 180, 190];
collect(coins, 150, 22, dir);
say((dir === "forward" ? "вперёд со splice" : "с конца со splice") + ": осталось " + coins.length + " — " + coins.join(", "));
}
say("");
say("# 5. Дорогая работа по кадрам: 600 врагов, обдумывание — 40 операций, 120 кадров, на кадре 60 убиты 150");
function spread(mode) {
let list = makeEnemies(600, 5).map((e) => ({ ...e, lastThink: -1 }));
const state = { next: 0 };
let total = 0;
let peak = 0;
let low = Infinity;
let gap = 0;
for (let f = 0; f < 120; f++) {
if (f === 60) list = list.filter((e) => e.id % 4 !== 0);
const ops = { think: 0, units: 0 };
if (mode === "all") for (const e of list) think(e, f, ops);
if (mode === "circle") thinkSome(list, state, 50, f, ops, false);
if (mode === "reset") thinkSome(list, state, 50, f, ops, true);
if (mode === "budget") thinkWithBudget(list, state, 2, () => ops.units * (f < 60 ? 1 : 2) / 1000, f, ops);
total += ops.think;
peak = Math.max(peak, ops.units);
low = Math.min(low, ops.think);
if (f >= 20) for (const e of list) gap = Math.max(gap, e.lastThink < 0 ? f + 1 : f - e.lastThink);
}
const never = list.filter((e) => e.lastThink < 0).length;
return "обдумываний " + total + ", за кадр " + low + "–" + (peak / 40) + ", пик операций " + peak +
", дольше всех ждал " + gap + " кадров, ни разу — " + never + " из " + list.length;
}
say("все каждый кадр: " + spread("all"));
say("50 за кадр, круговой индекс: " + spread("circle"));
say("50 за кадр, индекс с нуля: " + spread("reset"));
say("бюджет 2 мс (часы теста: 40 операций — 0,04 мс, с кадра 60 вдвое дольше): " + spread("budget"));
say("");
say("# 6. Свободная клетка: поле 10×10, 100 запросов на каждое заполнение, предел 1000 попыток");
for (const filled of [50, 90, 99, 100]) {
const rnd = makeRng(filled);
const order = Array.from({ length: 100 }, (_, i) => i);
for (let i = 99; i > 0; i--) { const j = Math.floor(rnd() * (i + 1)); [order[i], order[j]] = [order[j], order[i]]; }
const taken = new Uint8Array(100);
for (let i = 0; i < filled; i++) taken[order[i]] = 1;
const a = { tries: 0, gaveUp: 0 };
const b = { tries: 0, gaveUp: 0 };
let worst = 0;
for (let q = 0; q < 100; q++) {
const before = a.tries;
randomFreeCell(taken, 100, rnd, 1000, a);
worst = Math.max(worst, a.tries - before);
}
for (let q = 0; q < 100; q++) listFreeCell(taken, 100, rnd, b);
say("занято " + filled + ": наугад — попыток " + a.tries + ", худший запрос " + worst + ", сдался " + a.gaveUp +
"; списком — проверок " + b.tries + ", не нашёл " + b.gaveUp);
}
process.stdout.write(out.join("\n") + "\n");
Проверка в Node.js
Ниже — полный вывод node test.mjs на Node.js 24.22.1; мы запускали его 25 раз подряд, вывод совпадал байт в байт.
Вывод прогона:
# 0. Бюджет кадра
60 Гц: 1000 / 60 = 16,7 мс на кадр
120 Гц: 1000 / 120 = 8,3 мс на кадр
144 Гц: 1000 / 144 = 6,9 мс на кадр
# 1. Видит ли враг игрока: карта 640×480 px, 400 врагов, игрок в (400,300), один кадр
условия: бодрствует; ближе 160 px; луч с шагом 4 px без стен
бодрствуют 121 из 400
los → near → awake: видят 36, дешёвых проверок 340, вызовов обзора 400, клеток 12821
near → awake → los: видят 36, дешёвых проверок 536, вызовов обзора 38, клеток 1040
awake → near → los: видят 36, дешёвых проверок 521, вызовов обзора 38, клеток 1040
# 2. Есть ли враг в радиусе: 200 точек, 400 врагов
r 40 px, без break: найдено в 196 точках, проверок 80000
r 40 px, с break: найдено в 196 точках, проверок 14464
r 12 px, без break: найдено в 81 точках, проверок 80000
r 12 px, с break: найдено в 81 точках, проверок 62775
# 3. Каждый с каждым: круги r 8 px
n 50: j от i+1 — проверок 1225, касаний 4; j от 0 — проверок 2500, касаний 58
n 100: j от i+1 — проверок 4950, касаний 15; j от 0 — проверок 10000, касаний 130
n 300: j от i+1 — проверок 44850, касаний 132; j от 0 — проверок 90000, касаний 564
n 600: j от i+1 — проверок 179700, касаний 502; j от 0 — проверок 360000, касаний 1604
# 4. Удаление во время обхода: 10 монет через 10 px, игрок в 150, дотягивается на 22 px
монеты: 100, 110, 120, 130, 140, 150, 160, 170, 180, 190
вперёд со splice: осталось 7 — 100, 110, 120, 140, 160, 180, 190
с конца со splice: осталось 5 — 100, 110, 120, 180, 190
# 5. Дорогая работа по кадрам: 600 врагов, обдумывание — 40 операций, 120 кадров, на кадре 60 убиты 150
все каждый кадр: обдумываний 63000, за кадр 450–600, пик операций 24000, дольше всех ждал 0 кадров, ни разу — 0 из 450
50 за кадр, круговой индекс: обдумываний 6000, за кадр 50–50, пик операций 2000, дольше всех ждал 11 кадров, ни разу — 0 из 450
50 за кадр, индекс с нуля: обдумываний 6000, за кадр 50–50, пик операций 2000, дольше всех ждал 120 кадров, ни разу — 400 из 450
бюджет 2 мс (часы теста: 40 операций — 0,04 мс, с кадра 60 вдвое дольше): обдумываний 4500, за кадр 25–50, пик операций 2000, дольше всех ждал 17 кадров, ни разу — 0 из 450
# 6. Свободная клетка: поле 10×10, 100 запросов на каждое заполнение, предел 1000 попыток
занято 50: наугад — попыток 200, худший запрос 8, сдался 0; списком — проверок 10000, не нашёл 0
занято 90: наугад — попыток 826, худший запрос 51, сдался 0; списком — проверок 10000, не нашёл 0
занято 99: наугад — попыток 8843, худший запрос 541, сдался 0; списком — проверок 10000, не нашёл 0
занято 100: наугад — попыток 100000, худший запрос 1000, сдался 100; списком — проверок 10000, не нашёл 100
Что показал прогон: четыре ловушки
Четыре ловушки воспроизвелись: ловушка 1 — раздел 1 вывода, ловушка 2 — раздел 3, ловушка 3 — раздел 5, ловушка 4 — раздел 6. Раздел 4 показывает пропуск при удалении вперёд, который подробно разобран в статье про спавн и удаление.
Ловушка 1: дорогая проверка первой
Если дорогую проверку поставить перед дешёвыми, она выполняется для всех объектов, хотя большинство отсеялось бы даром. Обзор первым — 400 вызовов и 12821 клетка за кадр; после проверок «бодрствует» и «близко» — 38 вызовов и 1040 клеток. Ответ одинаковый: игрока видят 36 врагов. Такая ошибка не видна на экране — игра просто медленнее, поэтому её находят только замером или счётчиком.
Ловушка 2: внутренний цикл с нуля
Если внутренний цикл «каждый с каждым» начать с j = 0, каждый объект «касается» сам себя, а каждое настоящее касание считается дважды. Для 50 кругов цикл с j = i + 1 нашёл 4 касания, а с j = 0 — 58: 4 пары по два раза и ещё 50 касаний с собой. Для 600 кругов — 502 против 1604. Если по касанию наносится урон, враг бьёт сам себя каждый кадр, а настоящий удар засчитывается дважды; проверок при этом вдвое больше — 360000 против 179700.
Ловушка 3: круговой индекс сбрасывается каждый кадр
Если индекс «с кого продолжить» обнулять в начале каждого кадра, каждый кадр обрабатываются одни и те же первые 50 объектов, а остальные не обрабатываются никогда. В прогоне за 120 кадров 400 врагов из 450 выживших не подумали ни разу, а «дольше всех ждал» — все 120 кадров. С индексом, который хранится между кадрами, — 0 из 450 и не больше 11 кадров ожидания. Обдумываний в обоих вариантах поровну, 6000, и пик тот же, 2000 операций, — по счётчику нагрузки ошибку не заметить: враги просто стоят.
Ловушка 4: while без предохранителя
Цикл «пока не найдём свободную клетку» на полном поле никогда не закончится. В прогоне на поле 10×10 с 100 занятыми клетками его остановил только предел: каждый из 100 запросов сделал 1000 попыток и вернул «не нашли». Опасна и почти полная карта: при 99 занятых клетках худший запрос потратил 541 попытку, а все 100 — 8843. В игре такая ошибка выглядит как зависшая вкладка в момент, когда игрок заполнил уровень, — то есть редко и не на тесте.
Время в миллисекундах
Время меняется от запуска к запуску, поэтому оно вне детерминированного вывода. timing.mjs прогоняет каждый вариант семь серий подряд — 2000 кадров для проверки обзора и 20 для пар — и печатает медиану и разброс времени одного кадра. Linux, 8 виртуальных ядер Intel Xeon, 15 ГиБ памяти, Node.js 24.22.1, три запуска 12.11.2026:
| Что | Диапазон, мс на кадр | Медианы трёх запусков, мс |
|---|---|---|
| 400 врагов, обзор первым | 0,0928–0,1127 | 0,1010; 0,0944; 0,0942 |
| 400 врагов, расстояние → бодрствует → обзор | 0,0095–0,0126 | 0,0098; 0,0097; 0,0103 |
| 400 врагов, бодрствует → расстояние → обзор | 0,0092–0,0105 | 0,0095; 0,0094; 0,0099 |
600 кругов, j от 0 | 0,5446–0,7552 | 0,5600; 0,5631; 0,5918 |
600 кругов, j от i + 1 | 0,3054–0,4971 | 0,3131; 0,3143; 0,3323 |
Ранний выход перед дорогой проверкой дал заметную разницу и во времени: медианы около 0,094–0,101 мс против 0,0094–0,0103 мс. Даже худший вариант здесь — малая доля кадра в 16,7 мс, но это 400 врагов и одна проверка; в настоящей игре таких циклов в кадре много.
// timing.mjs — время в мс, не входит в детерминированный вывод: node timing.mjs
import { makeWalls, makeEnemies, sees, overlaps } from "./loops.mjs";
const SERIES = 7;
const map = makeWalls();
const enemies = makeEnemies(400, 74);
const player = { x: 400, y: 300 };
function median(label, frames, fn) {
const per = [];
for (let s = 0; s < SERIES; s++) {
const t = performance.now();
for (let f = 0; f < frames; f++) fn();
per.push((performance.now() - t) / frames);
}
per.sort((a, b) => a - b);
console.log(label + ": медиана " + per[SERIES >> 1].toFixed(4) + " мс на кадр (от " + per[0].toFixed(4) +
" до " + per[SERIES - 1].toFixed(4) + ")");
}
function frame(order) {
const ops = { cheap: 0, losCalls: 0, cells: 0 };
let seen = 0;
for (const e of enemies) if (sees(map, e, player, order, ops)) seen += 1;
return seen;
}
console.log("Node.js " + process.version + ", серий " + SERIES);
for (let w = 0; w < 3; w++) { frame(["los", "near", "awake"]); frame(["near", "awake", "los"]); frame(["awake", "near", "los"]); }
median("обзор первым", 2000, () => frame(["los", "near", "awake"]));
median("расстояние → бодрствует → обзор", 2000, () => frame(["near", "awake", "los"]));
median("бодрствует → расстояние → обзор", 2000, () => frame(["awake", "near", "los"]));
const list = makeEnemies(600, 7);
median("600 кругов, j от 0", 20, () => overlaps(list, 8, "full", { pairs: 0 }));
median("600 кругов, j от i+1", 20, () => overlaps(list, 8, "half", { pairs: 0 }));
Что не подтвердилось
Три ожидания прогон не подтвердил или подтвердил слабее, чем мы думали:
- «Порядок условий сильно ускоряет». Только когда в конце стоит дорогая проверка. Порядок двух дешёвых условий между собой дал 536 и 521 дешёвую проверку, а по времени — медианы 0,0097–0,0103 мс против 0,0094–0,0099 мс при перекрывающихся диапазонах 0,0095–0,0126 и 0,0092–0,0105 мс. На современном движке JavaScript такая перестановка — не оптимизация; переставлять стоит то, что действительно дорого.
- «break всегда экономит много». Только когда искомое находится. При радиусе 40 px
breakсократил 80000 проверок до 14464, а при радиусе 12 px, где враг нашёлся только в 81 точке из 200, — до 62775. - «Вдвое больше проверок — вдвое дольше». Не совсем: цикл с
jот 0 сделал 360000 проверок против 179700, а по времени медианы 0,5600–0,5918 мс против 0,3131–0,3323 мс. Счётчик операций показывает, растёт ли работа, но не переводится в миллисекунды один к одному.
Ещё одно ожидание оказалось верным только наполовину: список свободных клеток надёжнее поиска наугад, но не всегда дешевле. На поле, занятом наполовину, наугад вышло 200 попыток на 100 запросов, а списком — 10000 проверок.
Практический сценарий: 600 врагов думают в одном кадре
Задача: 600 врагов каждый кадр «обдумывают» положение игрока, и кадр перестал укладываться в бюджет. Нужно снизить пик работы за кадр так, чтобы ни один враг не остался без обновления. Входные данные — функции think и thinkSome и сцена из раздела 5 теста.
- Посчитать, сколько работы в кадре. Строка «все каждый кадр»: от 450 до 600 обдумываний и пик 24000 операций за кадр.
- Раздать работу по 50 за кадр с круговым индексом. Индекс храним между кадрами в объекте
stateи обнуляем, только когда он вышел за конец списка. - Прогнать и проверить пик. Строка «круговой индекс»: 50 за кадр, пик 2000 операций.
- Проверить, что никто не забыт. Там же: ни разу не подумали 0 из 450, дольше всех ждали 11 кадров. Если у вас вышло «400 из 450» и «120 кадров», как в строке «индекс с нуля», индекс обнуляется каждый кадр.
- Если машина бывает медленной, — перейти на бюджет по времени. Строка «бюджет 2 мс»: на медленной половине прогона 25 обдумываний за кадр вместо 50, ожидание до 17 кадров, а пик не вырос.
Проверяемый итог: строка «50 за кадр, круговой индекс» в разделе 5 показывает пик 2000 операций вместо 24000 и 0 забытых врагов. Задержку в 11 кадров стоит проверить в игре глазами: если враг реагирует заметно поздно, увеличьте порцию за кадр — пик операций вырастет вместе с ней.
Когда вам это не подойдёт
Ранний выход, break и круговой индекс подходят для обычной логики кадра с десятками и сотнями объектов; вот где этого мало или это лишнее:
- Реакция должна быть в этом же кадре. Управление игроком, попадания пуль и урон нельзя раздавать по кадрам: задержка в 11 кадров для них заметна и нечестна. По частям делают только то, что может подождать, — решения врагов, поиск пути, обновление дальних объектов.
- Повтор прохождения и одинаковый результат на всех машинах. Бюджет по времени делает число обработанных объектов зависимым от скорости машины — в нашем прогоне 25 вместо 50. Для повтора прохождения берите фиксированное число за кадр.
- Сотни объектов проверяют друг друга. Ранний выход и
j = i + 1не меняют того, что число пар растёт быстрее числа объектов; нужен поиск соседей через пространственную сетку. - Вы не знаете, где теряется время. Переставлять условия наугад бесполезно, как показал прогон; сначала найдите медленную функцию профайлером или выведите счётчики на экран в отладочном оверлее.
- Объектов единицы. При десятке объектов вложенный цикл, полный перебор и обновление всех каждый кадр проще и укладываются в бюджет с запасом; усложнять код ради них не нужно.
Мы разрабатываем J2DRU — браузерный 2D игровой движок, где логика собирается из событий, условий и действий, а проект можно углублять на TypeScript. Движок в разработке и публично пока не открыт, заявку можно оставить на странице раннего доступа (подача заявки не гарантирует приглашение).
Источники (проверено: 12.11.2026, все страницы открываются с HTTP 200): MDN — Window: requestAnimationFrame() (частота вызовов обычно совпадает с частотой обновления экрана; чаще всего 60 Гц, распространены 75, 120 и 144 Гц); MDN — Logical AND (&&) (операнды вычисляются слева направо, возврат на первом ложном); MDN — continue (завершает текущий проход цикла и переходит к следующему); MDN — break (завершает текущий цикл); MDN — Array.prototype.splice() (меняет сам массив, удаляя или заменяя элементы на месте); MDN — Performance: now() (время в миллисекундах с дробной частью; в неизолированной странице точность огрублена до 100 мкс). Карта, враги, условия, сцены и все числа прогона и замера — наш пример в Node.js 24.22.1.
Читайте также:
- Как найти просадку FPS в браузерной 2D-игре: бюджет кадра, Chrome DevTools Performance, долгие задачи и сборка мусора
- Игровой цикл (Game Loop) и физика столкновений (AABB, хитбоксы и триггеры) простыми словами и на уровне профи
- Спавн и удаление объектов в 2D-игре: время жизни, отложенное удаление и пулы
- Пространственное хеширование: столкновения сотен объектов без проверки «каждый с каждым»
- Отладочный оверлей на JavaScript: хитбоксы, FPS и журнал событий