Столкновения частиц: четыре способа моделирования

Полный перебор: каждая с каждой

Самый прямой способ — для каждой частицы проверить расстояние до каждой другой частицы. Если расстояние между центрами меньше суммы радиусов, частицы пересеклись и требуется обработать столкновение.

1. Берём частицу №1 и сравниваем её со всеми следующими.
2. Переходим к частице №2 и снова сравниваем только со следующими.
3. Для каждой пары вычисляем расстояние между центрами и сначала собираем все пересёкшиеся пары.
4. После завершения поиска сортируем список пар и только затем одинаково обрабатываем все найденные столкновения.

const hits = [];
for (let i = 0; i < n; i++) {
  for (let j = i + 1; j < n; j++) {
    checks++;
    if (isOverlapping(particles[i], particles[j])) {
      hits.push([i, j]);
    }
  }
}
resolvePairs(hits);

Поиск по сетке: проверяем только соседние ячейки

Разобьём поверхность на квадратные ячейки. Если размер ячейки не меньше диаметра самой крупной частицы, столкнуться могут только частицы из одной и соседних ячеек. Далёкие частицы можно вообще не сравнивать.

1. По координатам частицы определяем номер её ячейки.
2. Для каждой занятой ячейки рассматриваем её саму и соседние ячейки.
3. Точный тест расстояния выполняем только для найденных кандидатов и собираем пересёкшиеся пары.
4. После поиска сортируем пары и применяем ту же реакцию на столкновение, что и в полном переборе.

const hits = [];
for (const [key, ids] of grid) {
  // рассматриваем только эту и соседние ячейки
  for (const [i, j] of localCandidatePairs(key, ids, grid)) {
    checks++;
    if (isOverlapping(particles[i], particles[j])) {
      hits.push([i, j]);
    }
  }
}
resolvePairs(hits);

Список соседей: запоминаем ближайших

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

1. Периодически строим список пар, находящихся достаточно близко.
2. Между перестроениями проверяем столкновения только внутри этого списка и собираем пересёкшиеся пары.
3. Запас гарантирует, что частицы не успеют неожиданно войти в контакт.
4. Найденные пары сортируются и обрабатываются в том же порядке, что и в двух предыдущих методах.

buildNeighborList(); // перестраивается не каждый кадр
const hits = [];

for (const [i, j] of neighborPairs) {
  checks++;
  if (isOverlapping(particles[i], particles[j])) {
    hits.push([i, j]);
  }
}
resolvePairs(hits);

Вероятностное столкновение: моделируем событие, а не точную геометрию

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

1. Размещаем частицы по ячейкам.
2. Внутри каждой ячейки рассматриваем локальные пары.
3. Чем больше относительная скорость и размеры частиц, тем выше вероятность события.
4. Если случайное число меньше P, направления скоростей изменяются как после столкновения.

Формула в этой учебной модели не претендует на универсальный физический закон. Она показывает сам принцип: точное геометрическое событие заменяется статистическим правилом с управляемой вероятностью.

for (const ids of grid.values()) {
  for (let a = 0; a < ids.length; a++)
    for (let b = a + 1; b < ids.length; b++) {
      const A = particles[ids[a]], B = particles[ids[b]];
      checks++;
      const vRel = Math.hypot(A.vx-B.vx, A.vy-B.vy);
      const p = 1 - Math.exp(-7.5*vRel*(A.r+B.r)*dt
                             /(cellSize*cellSize));
      if (collisionRng() < p) {
        resolveStochastic(A, B);
        collisions++;
      }
    }
}