Qual é a melhor maneira de verificar a colisão de um grande número de círculos?
É muito fácil detectar colisões entre dois círculos, mas se verificarmos todas as combinações, seráEm2) que definitivamente não é uma solução ideal.

Podemos supor que o objeto circle tenha as seguintes propriedades:

CoordenadasRaioVelocidadeDireção

A velocidade é constante, mas a direção pode mudar.

Eu vim com duas soluções, mas talvez haja algumas soluções melhores.

Solução 1
Divida o espaço inteiro em quadrados sobrepostos e verifique se há colisão apenas com círculos que estão no mesmo quadrado. Os quadrados precisam se sobrepor para que não haja problemas quando um círculo se move de um quadrado para outro.

Solução 2
No início, as distâncias entre cada par de círculos precisam ser calculadas.
Se a distância for pequena, esse par será armazenado em alguma lista e precisamos verificar a colisão em todas as atualizações.
Se a distância for grande, armazenamos após a atualização que pode haver uma colisão (pode ser calculada porque sabemos a distância e as velocidades). Ele precisa ser armazenado em algum tipo de fila de prioridade. Após o número calculado anteriormente de atualizações, a distância precisa ser verificada novamente e, em seguida, fazemos o mesmo procedimento - coloque-o na lista ou novamente na fila de prioridade.

Respostas às perguntas de Mark Byers

É para um jogo?
É para simulação, mas pode ser tratado também como um jogoDeseja recalcular a nova posição a cada n milissegundos e também verificar colisões neste momento?
Sim, o tempo entre a atualização é constante.Deseja encontrar a hora em que ocorre a primeira / cada colisão?
Não, eu quero encontrar todas as colisões e fazer 'algo' quando ocorrer.Quão importante é a precisão?
Depende do que você quer dizer com precisão. Eu preciso detectar todas as colisões.É um grande problema se pequenos círculos em movimento rápido podem passar um pelo outro ocasionalmente?
Pode-se supor que a velocidade é tão pequena que não vai acontecer.