Otimizando cálculos de gravidade

Eu tenho vários objetos de tamanho e velocidade variados que gravitam um para o outro. Em toda atualização, eu tenho que passar por cima de todos os objetos e somar as forças devido à gravidade de todos os outros objetos. Ele não escala muito bem, é um dos dois grandes gargalos que encontrei no meu jogo e não tenho certeza do que fazer para melhorar o desempenho.

Ele se sente como eu deveria ser capaz de melhorar o desempenho. A qualquer momento, provavelmente 99% dos objetos no sistema terão apenas uma influência desprezível em um objeto. É claro que não posso classificar os objetos por massa e considerar apenas os 10 maiores objetos ou algo assim, porque a força varia mais com a distância do que com a massa (a equação é ao longo das linhas de force = mass1 * mass2 / distance^2). Eu acho que uma boa aproximação seria considerar os objetos maiores e os objetos mais próximos, ignorando as centenas de pequenos fragmentos de rocha do outro lado do mundo que não podem afetar nada - mas para descobrir quais objetos são o mais próximo que eu tiver que percorrer todos os objetos, e suas posições estão mudando constantemente, então não é como se eu pudesse fazer isso apenas uma vez.

Atualmente estou fazendo algo parecido com isto:

private void UpdateBodies(List<GravitatingObject> bodies, GameTime gameTime)
{
    for (int i = 0; i < bodies.Count; i++)
    {
        bodies[i].Update(i);
    }
}

//...

public virtual void Update(int systemIndex)
{
    for (int i = systemIndex + 1; i < system.MassiveBodies.Count; i++)
    {
        GravitatingObject body = system.MassiveBodies[i];

        Vector2 force = Gravity.ForceUnderGravity(body, this);
        ForceOfGravity += force;
        body.ForceOfGravity += -force;
    }

    Vector2 acceleration = Motion.Acceleration(ForceOfGravity, Mass);
    ForceOfGravity = Vector2.Zero;

    Velocity += Motion.Velocity(acceleration, elapsedTime);
    Position += Motion.Position(Velocity, elapsedTime);
}

(observe que removi muito código - por exemplo, os testes de colisão, não repetimos os objetos pela segunda vez para detectar colisões).

Portanto, nem sempre estou repetindo a lista inteira - apenas faço isso para o primeiro objeto, e toda vez que o objeto encontra a força que sente em relação a outro objeto, esse outro objeto sente a mesma força, então apenas atualiza os dois. eles - e, em seguida, esse primeiro objeto não precisará ser considerado novamente pelo restante da atualização.

As funções Gravity.ForceUnderGravity(...)e Motion.Velocity(...)etc. apenas usam um pouco do XNA construído em matemática vetorial.

Quando dois objetos colidem, eles criam detritos sem massa. Ele é mantido em uma lista separada e os objetos maciços não iteram sobre os detritos como parte de seu cálculo de velocidade, mas cada pedaço de detrito deve iterar sobre as partículas maciças.

Isso não precisa ser escalado para limites incríveis. O mundo não é ilimitado, ele contém uma borda que destrói objetos que o atravessam - eu gostaria de poder lidar com talvez cerca de mil objetos, atualmente o jogo começa a sufocar cerca de 200.

Alguma idéia de como eu poderia melhorar isso? Alguma heurística que eu possa usar para raspar o comprimento do loop de centenas para poucos? Algum código que eu posso executar com menos frequência que todas as atualizações? Devo apenas multithread até que seja rápido o suficiente para permitir um mundo de tamanho decente? Devo tentar descarregar os cálculos de velocidade na GPU? Se sim, como eu arquitetaria isso? Posso manter dados estáticos e compartilhados na GPU? Posso criar funções HLSL na GPU e chamá-las arbitrariamente (usando XNA) ou elas precisam fazer parte do processo de desenho?

Isso soa como um trabalho para uma grade. Divida o espaço do jogo em uma grade e, para cada célula da grade, mantenha uma lista dos objetos atualmente nela. Quando os objetos se movem através de um limite de célula, atualize em qual lista eles estão. Ao atualizar um objeto e procurar outros com quem interagir, você pode ver apenas a célula atual da grade e algumas vizinhas. Você pode ajustar o tamanho da grade para obter o melhor desempenho (equilibrando o custo de atualização das células da grade - que é maior quando as células da grade são muito pequenas - com o custo de fazer as pesquisas, que é maior quando as células da grade são muito altas ampla).

Obviamente, isso fará com que objetos mais afastados do que algumas células da grade não interajam, o que provavelmente é um problema porque um grande acúmulo de massa (um objeto grande ou um cluster de muitos objetos pequenos) deve , como você mencionou, tem uma região de influência maior.

Uma coisa que você pode fazer é acompanhar a massa total dentro de cada célula da grade e tratar a célula inteira como um único objeto para fins de interações mais distantes. Ou seja: ao calcular a força em um objeto, calcule a aceleração direta de objeto a objeto para os objetos em algumas células da grade próximas e adicione uma aceleração de célula a célula para cada célula da grade mais distante (ou talvez apenas aqueles com uma quantidade não desprezível de massa). Por aceleração de célula a célula, quero dizer um vetor calculado usando as massas totais das duas células e a distância entre seus centros. Isso deve fornecer uma aproximação razoável da gravidade somada de todos os objetos nessa célula da grade, mas muito mais barata.

Se o mundo do jogo for muito grande, você poderá usar uma grade hierárquica , como uma quadtree (2D) ou octree (3D), e aplicar princípios semelhantes. Interações a longa distância corresponderiam a níveis mais altos da hierarquia.

O algoritmo de Barnes-Hut é o caminho a seguir com este. Ele foi usado em simulações de supercomputadores para resolver seu problema exato. Não é muito difícil de codificar e é muito eficiente. Na verdade, escrevi um applet Java não muito tempo atrás para resolver esse problema.

Visite http://mathandcode.com/programs/javagrav/ e pressione "start" e "show quadtree".

Na guia Opções, você pode ver que a contagem de partículas pode chegar a 200.000. No meu computador, o cálculo termina em cerca de 2 segundos (o desenho de 200.000 pontos leva cerca de 1 segundo, mas o cálculo é executado em um thread separado).

Veja como meu applet funciona:

1. Crie uma lista de partículas aleatórias, com massas, posições e velocidades iniciais aleatórias.
2. Construa um quadtree a partir dessas partículas. Cada nó quadtree contém o centro de massa de cada subnó. Basicamente, para cada nó, você tem três valores: massx, massy e mass. Toda vez que você adiciona uma partícula a um determinado nó, você aumenta massx e massy por particle.x * particle.mass e particle.y * particle.mass respectivamente. A posição (massax / massa, massa / massa) terminará como o centro de massa do nó.
3. Para cada partícula, calcule as forças (totalmente descritas aqui ). Isso é feito iniciando no nó superior e recorrendo através de cada subnó do quadtree até que o subnó fornecido seja pequeno o suficiente. Depois de parar de recorrer, é possível calcular a distância da partícula ao centro de massa do nó e, em seguida, calcular a força usando a massa do nó e a massa da partícula.

Seu jogo deve ser capaz de lidar com milhares de objetos que se atraem mutuamente. Se cada objeto for "burro" (como as partículas básicas no meu applet), você poderá obter 8000 a 9000 partículas, talvez mais. E isso está assumindo a segmentação única. Com aplicativos de computação multithread ou paralelos, você pode obter muito mais partículas do que a atualização em tempo real.

Veja também: http://www.youtube.com/watch?v=XAlzniN6L94 para obter uma grande renderização deste

Nathan Reed tem uma excelente resposta. A versão curta é usar uma técnica de fase larga que se encaixa na topologia da simulação e executar apenas os cálculos de gravidade em pares de objetos que terão um efeito perceptível um no outro. Realmente não é diferente do que você faria para a detecção regular de colisões em fase larga.

Continuando com isso, porém, outra possibilidade é atualizar apenas objetos de forma intermitente. Basicamente, cada etapa (quadro) atualiza apenas uma fração de todos os objetos e deixa a velocidade (ou aceleração, dependendo da sua preferência) a mesma para os outros objetos. É improvável que o usuário note qualquer atraso nas atualizações desde que os intervalos não sejam muito longos. Isso fornecerá uma aceleração linear do algoritmo, então, definitivamente, observe as técnicas de fase larga como Nathan sugeriu também, que podem fornecer acelerações muito mais significativas se você tiver uma tonelada de objetos. Embora nem um pouco modelado da mesma maneira, é como ter "ondas de gravidade". :)

Além disso, você pode gerar um campo de gravidade em uma passagem e atualizar os objetos em uma segunda passagem. Na primeira passagem, você está basicamente preenchendo uma grade (ou uma estrutura de dados espaciais mais complexa) com as influências da gravidade de cada objeto. O resultado agora é um campo de gravidade que você pode renderizar (parece bem legal) para ver qual aceleração será aplicada a um objeto em qualquer local. Então você itera sobre os objetos e simplesmente aplica os efeitos do campo de gravidade a esse objeto. Ainda mais legal, você pode fazer isso em uma GPU renderizando os objetos como círculos / esferas em uma textura e lendo a textura (ou usando outra passagem de feedback de transformação na GPU) para modificar as velocidades do objeto.

Eu recomendaria usar um Quad Tree. Eles permitem procurar rápida e eficientemente todos os objetos em uma área retangular arbitrária. Aqui está o artigo wiki sobre eles: http://en.wikipedia.org/wiki/Quadtree

E um link vergonhoso para o meu próprio projeto XNA Quad Tree no SourceForge: http://sourceforge.net/projects/quadtree/

Eu também manteria uma lista de todos os objetos grandes para que eles possam interagir com tudo, independentemente da distância.

Apenas um pouco de entrada (possivelmente ingênua). Não faço programação de jogos, mas o que sinto é que o seu gargalo fundamental é o cálculo da gravidade devido à gravidade. Em vez de iterar sobre cada objeto X e, em seguida, encontrar o efeito gravitacional de cada objeto Y e adicioná-lo, você pode pegar cada par X, Y e encontrar a força entre eles. Isso deve reduzir o número de cálculos de gravidade de O (n ^ 2). Então você fará muitas adições (O (n ^ 2)), mas isso normalmente é menos caro.

Também neste ponto você pode implementar regras como "se a força gravitacional for menor que \ epsilon, porque esses corpos são muito pequenos, defina a força como zero". Pode ser vantajoso ter essa estrutura também para outros fins (incluindo detecção de colisão).

Ao estender a resposta de seanmiddleditch, pensei que poderia lançar alguma luz (ironia?) Sobre a idéia do campo de gravidade.

Primeiro, não pense nisso como uma textura, mas como um campo discreto de valores que podem ser modificados (uma matriz bidimensional, por assim dizer); e a precisão subsequente da simulação poderia ser a resolução desse campo.

Quando você introduz um objeto no campo, seu potencial de gravitação pode ser calculado para todos os valores circundantes; criando assim um dissipador de gravitação no campo.

Mas quantos desses pontos você deve calcular antes que se torne mais ou tão ineficaz quanto antes? Provavelmente não muitos, mesmo 32x32 é um campo substancial para iterar para cada objeto. Portanto, divida todo o processo em várias passagens; cada um com diferentes resoluções (ou precisão).

Ou seja, a primeira passagem pode calcular a gravidade dos objetos representada em uma grade 4x4, com cada valor de célula representando uma coordenada 2D no espaço. Dando uma complexidade subtotal O (n * 4 * 4).

A segunda passagem pode ser mais precisa, com um campo de gravidade de resolução de 64x64, com cada valor de célula representando uma coordenada 2D no espaço. No entanto, como a complexidade é muito alta, você pode restringir o raio das células circundantes afetadas (talvez apenas as células 5x5 circundantes sejam atualizadas).

Uma terceira passagem adicional pode ser usada para cálculos de alta precisão, talvez com uma resolução de 1024x1024. Lembre-se de que em nenhum momento você está realizando cálculos separados de 1024x1024, mas operando apenas em partes desse campo (talvez subseções 6x6).

Dessa forma, sua complexidade geral para a atualização é O (n * (4 * 4 + 5 * 5 + 6 * 6)).

Para calcular as mudanças de velocidade de cada um de seus objetos, para cada campo de gravidade (4x4, 64x64, 1024x1024), basta mapear a posição das massas pontuais em uma célula da grade, aplicar o vetor de potencial gravitacional geral das células da grade a um novo vetor; repita para cada "camada" ou "passagem"; depois adicione-os. Isso deve fornecer um bom vetor de força gravitacional resultante.

Portanto, a complexidade geral é: O (n * (4 * 4 + 5 * 5 + 6 * 6) + n). O que realmente conta (por complexidade) é quantas células circundantes você atualiza ao calcular o potencial gravitacional nas passagens, não a resolução geral dos campos de gravidade.

A razão para os campos de baixa resolução (primeiras passagens) é obviamente abranger o universo como um todo e garantir que as massas periféricas sejam atraídas para áreas mais densas, apesar da distância. Em seguida, use campos de resolução mais alta como camadas separadas para aumentar a precisão dos planetas vizinhos.

Espero que isso faça sentido.

Que tal outra abordagem:

Atribua uma área de influência a objetos com base em sua massa - eles são pequenos demais para ter um efeito mensurável além desse intervalo.

Agora divida seu mundo em uma grade e coloque cada objeto em uma lista de todas as células nas quais ele influencia.

Faça seus cálculos de gravidade apenas nos objetos da lista anexada à célula em que ele está.

Você só precisa atualizar as listas quando um objeto se move para uma nova célula da grade.

Quanto menor a célula da grade, menor será o cálculo por atualização, mas mais trabalho será feito na atualização das listas.