Эффективный алгоритм обработки коллизий n кругов

Можно оптимизировать через quadtree. На современном железе 50 fps на 100000 шаров без отрисовки. Написано на JavaScript, соответственно C, C++, C#, Java смогут показать лучшие результаты. Решение однопоточное, но обработку поддеревьев можно делать параллельно. Так что есть куда двигаться.

Демо для 8000 шаров. Я дополнил условия: симулируется движение множества шаров различных радиусов. Шары упруго сталкиваются друг с другом и со стенками прямоугольного поля. Симуляция покадровая с FPS около 60.

Задача решается через quadtree. Наложим на прямоугольник квадрат, разбитый на четыре квадранта. Для каждого квадранта составим список шаров, которые с ним пересекаются. Большинство шаров окажется в каком-то одном квадранте, некоторые пересекутся с двумя, единицы пересекутся с тремя или четырьмя. Процесс разбиения будем повторять рекурсивно, пока списки шаров не станут короче некоторого порога или пока глубина рекурсии не превысит установленного предела. В каждом списке из листа дерева надо будет проделать попарную проверку пересечения. Так как мы рассчитываем что списки не длинные, то и проверка будет быстрой. Глубина дерева ограничена чтобы избежать ситуаций когда много шаров попадают во много квадрантов и списки почти не укорачиваются при разбиении.

В демо глубина дерева ограничена восемью, количество шаров в листе двадцатью. Оба параметра подбирались так чтобы минимизировать время симуляции.

Для 100000 шаров получилось уложить симуляцию в 20ms. Результаты и код: https://github.com/StanislavVolodarskiy/collision/blob/main/article/article.md

P.S. Симуляция довольно физичная, хотя не самая лучшая. Можно заметить некоторые вещи из газовой динамики и термодинамики: ударные волны в самом начале, броуновское движение, распределение энергии между шарами относительно их размеров.

Проще всего - кластеризация по сетке с шагом чуть больше чем в 2 раза больше максимального радиуса. Тогда для проверки коллизий для каждого объекта надо проверять только 9 корзин - его собственную и 8 соседних.

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

Искусственными тестами, естественно, этот алгоритм легко завалить, кинув все объекты в одну корзину.

Если есть маленькое количество больших объектов, то можно их вынести в отдельную корзину и пересекать со всеми.

Предлагаю прошерстить по одной координате (отсортировать же нужно) и для каждого круга проверять круги вперёд до расстояния (по этой координате) не более суммы радиуса этого круга и наибольшего радиуса.

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

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

Возможно, и сортировку удастся как-то оптимизировать с учётом ограниченного смещения кругов между кадрами.