Толпа на сетке: несколько клеток, а не миллион проверок

В boids каждому юниту нужны его ближайшие соседи — без них не сработают ни separation, ни alignment, ни cohesion. Наивный ответ — пройтись по всем и проверить расстояние:

// плохо: O(N²) на каждом кадре
for (int i = 0; i < N; i++) {
  for (int j = 0; j < N; j++) {
    if (i == j) continue;
    if ((boid[i].position - boid[j].position).sqrMagnitude < r * r) {
      // учесть соседа
    }
  }
}

Считаем по головам. 100 юнитов — 10 000 проверок за кадр. 500 — 250 000. 1000 — миллион. И всё это 60 раз в секунду.

Итак, spatial hash. Соседи по определению рядом — значит, проверять надо только тех, кто в той же зоне пространства. Разбиваем сцену на клетки фиксированного размера, раскладываем юнитов по клеткам и смотрим рядом:

// каждый кадр пересобираем
var grid = new Dictionary<Vector2Int, List<Boid>>();
foreach (var b in boids) {
  var cell = new Vector2Int(
    (int)(b.position.x / cellSize),
    (int)(b.position.z / cellSize));
  if (!grid.TryGetValue(cell, out var list))
    grid[cell] = list = new List<Boid>();
  list.Add(b);
}

Размер клетки чаще всего берут равными радиусу видимости соседей.

По сути алгоритм boids — это часть задачи. Ещё часть — найти соседей достаточно быстро. Без этого игры с сотнями юнитов на экране просто не существовали бы. 🔥 Кроме того их надо отрендерить, а об этом уже поговорим позже.


#мат_геймдев #МатРазбор #algorithms #optimization