Event-driven simulation: exact collisions without stepping through time

1. The tunneling problem

У покроковій (time-stepped) симуляції позиція частинки оновлюється дискретно: x(t + dt) = x(t) + v·dt. Якщо частинка рухається досить швидко відносно dt і товщини перешкоди, вона може «перестрибнути» перешкоду цілком — на кроці t вона перед стінкою, на кроці t+dt — вже за нею, і жодна перевірка перетину не спрацьовує. Це явище називають тунелюванням (tunneling).

Зменшення dt «вирішує» проблему ціною квадратичного зростання вартості (менший dt → більше кроків на ту саму тривалість симуляції). Для більярду, ігор з високою швидкістю снарядів чи молекулярної динаміки з жорсткими зіткненнями це неприйнятно.

2. Time-stepped vs. event-driven

Event-driven simulation інвертує підхід: замість «просувати всіх на dt і перевіряти перетини» вона обчислює точний аналітичний момент часу наступної колізії для кожної пари об'єктів, кладе всі майбутні події в чергу з пріоритетом за часом і просуває симуляцію рівно до наступної події — не менше, не більше.

3. Deriving time-of-impact analytically

Для двох куль радіусів r₁, r₂ з позиціями p₁, p₂ і швидкостями v₁, v₂ момент зіткнення — це найменше t > 0, за якого відстань між центрами дорівнює сумі радіусів. Позначимо відносну позицію Δp = p₂ − p₁ і відносну швидкість Δv = v₂ − v₁:

Розкриваючи квадрат, отримуємо квадратне рівняння відносно t:

Розв'язок: t = (−b − √(b² − 4ac)) / (2a) — беремо менший корінь (перший момент дотику, а не другий, коли кулі вже пройшли одна одну). Колізія реальна лише якщо:

• Дискримінант ≥ 0 — траєкторії взагалі перетинаються.
• t > 0 — зіткнення в майбутньому, не в минулому.
• Δp · Δv < 0 — кулі зближуються, а не віддаляються.

4. The priority queue algorithm

Алгоритм (класична схема, описана Sedgewick & Wayne для симуляції молекулярної динаміки твердих сфер) підтримує мін-купу подій, впорядковану за часом зіткнення:

Складність O(N² log N) для початкового заповнення черги (усі пари) плюс O(N log N) на кожну подію (перерахунок і вставка нових зіткнень для двох змінених частинок). Для N ~ 100–1000 куль це швидше і завжди точніше за time-stepped підхід.

5. Event invalidation

Найтонший момент реалізації: коли частинка i зіштовхується з j, усі раніше заплановані події за участю i чи j стають недійсними — швидкість i чи j змінилась, і старий прогноз зіткнення більше не вірний. Наївний підхід — видаляти застарілі події з черги (дорого для бінарної купи). Практичний підхід — залишати їх у черзі, але зберігати лічильник зіткнень кожної частинки на момент створення події; при витягуванні події з черги перевіряти, чи лічильники досі співпадають.

6. Elastic collision response

Для пружного (elastic) зіткнення двох куль мас m₁, m₂ у момент дотику, імпульс передається вздовж лінії центрів (нормаль n̂ = Δp / |Δp|):

Ця формула точно зберігає і імпульс, і кінетичну енергію системи двох тіл — на відміну від пружинної моделі контакту, де енергія неминуче трохи «просочується» через дискретизацію dt.

7. Method comparison

8. Псевдокод

Time-of-impact + priority queue (JS)

// Час до зіткнення двох куль (найменший додатний корінь)
function timeToCollision(a, b) {
  const dp = sub(b.pos, a.pos);
  const dv = sub(b.vel, a.vel);
  const R = a.radius + b.radius;

  const A = dot(dv, dv);
  if (A === 0) return Infinity;   // однакова швидкість — ніколи не зіткнуться

  const B = 2 * dot(dp, dv);
  if (B >= 0) return Infinity;    // віддаляються

  const C = dot(dp, dp) − R * R;
  const disc = B * B − 4 * A * C;
  if (disc < 0) return Infinity;    // траєкторії не перетинаються

  return (−B − Math.sqrt(disc)) / (2 * A);  // перший момент дотику
}

// Головний цикл: витягти найближчу подію, просунути час, розв'язати
function runEventDriven(particles, pq, tEnd) {
  let tNow = 0;
  while (tNow < tEnd) {
    const event = pq.popMin();
    if (!event.isValid()) continue;    // lazy invalidation

    const dt = event.time − tNow;
    for (const p of particles) p.advance(dt);  // прямолінійний рух
    tNow = event.time;

    resolveCollision(event.a, event.b);          // оновити швидкості
    predictNewCollisions(event.a, event.b, pq); // нові події в чергу
  }
}