encontrar objetos dentro do raio

Question

Procurando uma maneira leve de encontrar objetos dentro de um raio.

Até agora, a resposta que é óbvia para mim é percorrer cada objeto, comparando sua posição xey com o centro do raio.

Exemplo:

Turret - procurando alvos no raio.

TargetArray - conjunto de alvos possíveis.

WithinRangeArray - matriz para a qual enviamos metas aplicáveis

Distance^2 = (TargetArray[n].x - Turret.x)^2  +  (TargetArray[n].y - Turret.y)^2

if( Distance^2 < maxRadius^2 ){
WithinRangeArray.push(TargetArray[n])
}

Evitar a raiz quadrada deve me poupar algum poder de processamento.Mas tenho a sensação de que pode haver outros algoritmos/teorias/métodos que podem ser melhores (mais leves).

Comprimento ideal do TargetArray:menos de 500 alvos por vez.

Answer 1

Antes de calcular a distância radial, primeiro verifique se o objeto está dentro da caixa centralizada na localização da sua torre.Se target_x <turret_x-range então está fora do alcance e não há necessidade de verificar a distância, verifique também turret_x+range, turret_y-range, turret_y+range.Isso requer um máximo de 4 comparações e 4 operações de adição/subtração para determinar se o alvo está na caixa.

Answer 2

Em 2D você poderia implementar um Quadtree e em 3D você poderia implementar um Octree, o que significa que você seria capaz de agrupar objetos e descartar com mais eficiência grandes grupos deles antes de realmente verificar suas distâncias exatas.Você deve pesquisá-los no Google se quiser saber mais.São estruturas de dados muito úteis para mundos de objetos.

A implementação final pode não economizar tanto espaço, mas será incrivelmente rápida porque você pode descartar um grande número de objetos muito rapidamente.

Answer 3

Você poderia armazenar os alvos possíveis em um multiconjunto digitado no quadrado da grade que eles ocupam.Então você só precisa iterar sobre os alvos que estão nos quadrados da grade próximos o suficiente do quadrado da grade da torre para que possam ser alvos.

Se vale ou não a pena fazer isso, depende do número de alvos e do número de alvos que provavelmente estarão dentro do alcance.Estou trabalhando em um aplicativo com centenas de milhares de alvos, dos quais apenas 10 ou 20 provavelmente estarão dentro do alcance.Nesta situação, vale a pena investir em complexidade significativa para podar a lista de alvos potenciais.No seu caso, com apenas 500 alvos pode não valer a pena.