У меня есть большое количество объектов (для начала, мячей), которые ступенчато движутся в пространстве по одному и не должны перекрываться. В настоящее время при каждом движении я проверяю столкновение с любым другим объектом. Несколько другое вопросы, чтобы решить эту проблему, здесь, однако я подумал о, казалось бы, простом решении, которое, кажется, не подходит в этом контексте, и мне интересно, почему.
Почему бы просто не сохранить 2 коллекции (для 2D или 3 в трех измерениях) всех объектов, отсортированных по координате x и y (и z) соответственно, и при каждом движении искать все другие объекты на заданном расстоянии (диаметр шара здесь) в каждом измерении и проверяет ли фактическое столкновение только объекты в обоих (или всех 3) наборах результатов?
Я понимаю, что это работает только для объектов одинакового размера, но в качестве альтернативы можно использовать вдвое больше коллекций, отсортированных по (1) самой высокой (2) самой низкой координате каждого объекта для каждого измерения. Любая причина, по которой это не сработает или даст значительно меньшее улучшение по сравнению с переходом от «парной проверки» O (n) к «метод сетки" или "quad / octrees"? Я рассматриваю обновление этих отсортированных коллекций как дорогостоящую операцию здесь, но используя, например, TreeSet (моя реализация будет на Java) он все равно должен быть значительно меньше O (n), верно?
