Cálculos de gravidade 2D multithreading

Estou construindo um jogo de exploração espacial e atualmente comecei a trabalhar com gravidade (em C # com XNA).

A gravidade ainda precisa ser aprimorada, mas antes que eu possa fazer isso, preciso resolver alguns problemas de desempenho com meus cálculos de física.

Isso está usando 100 objetos, normalmente renderizando 1000 deles sem cálculos de física chega a mais de 300 FPS (que é meu limite de FPS), mas mais de 10 objetos traz o jogo (e o único segmento em que ele é executado) joelhos ao fazer cálculos de física.

Eu verifiquei o uso do meu thread e o primeiro thread estava acabando com todo o trabalho, então achei que só precisava fazer o cálculo da física em outro thread. No entanto, quando tento executar o método Update da classe Gravity.cs em outro segmento, mesmo que o método Update da Gravity não contenha nada, o jogo ainda diminui para 2 FPS.

Gravity.cs

public void Update()
    {
        foreach (KeyValuePair<string, Entity> e in entityEngine.Entities)
        {
            Vector2 Force = new Vector2();

            foreach (KeyValuePair<string, Entity> e2 in entityEngine.Entities)
            {
                if (e2.Key != e.Key)
                {
                    float distance = Vector2.Distance(entityEngine.Entities[e.Key].Position, entityEngine.Entities[e2.Key].Position);
                    if (distance > (entityEngine.Entities[e.Key].Texture.Width / 2 + entityEngine.Entities[e2.Key].Texture.Width / 2))
                    {
                        double angle = Math.Atan2(entityEngine.Entities[e2.Key].Position.Y - entityEngine.Entities[e.Key].Position.Y, entityEngine.Entities[e2.Key].Position.X - entityEngine.Entities[e.Key].Position.X);

                        float mult = 0.1f *
                            (entityEngine.Entities[e.Key].Mass * entityEngine.Entities[e2.Key].Mass) / distance * distance;

                        Vector2 VecForce = new Vector2((float)Math.Cos(angle), (float)Math.Sin(angle));
                        VecForce.Normalize();

                        Force = Vector2.Add(Force, VecForce * mult);
                    }
                }
            }

            entityEngine.Entities[e.Key].Position += Force;
        }

    }

Sim, eu sei. É um loop foreach aninhado, mas não sei mais como fazer o cálculo da gravidade, e isso parece funcionar, é tão intenso que ele precisa de seu próprio encadeamento. (Mesmo que alguém conheça uma maneira super eficiente de fazer esses cálculos, eu ainda gostaria de saber como eu poderia fazê-lo em vários threads)

EntityEngine.cs (gerencia uma instância de Gravity.cs)

public class EntityEngine
{
    public Dictionary<string, Entity> Entities = new Dictionary<string, Entity>();
    public Gravity gravity;
    private Thread T;


    public EntityEngine()
    {
        gravity = new Gravity(this);
    }


    public void Update()
    {
        foreach (KeyValuePair<string, Entity> e in Entities)
        {
            Entities[e.Key].Update();
        }

        T = new Thread(new ThreadStart(gravity.Update));
        T.IsBackground = true;
        T.Start();
    }

}

EntityEngine é criado no Game1.cs e seu método Update () é chamado no Game1.cs.

Preciso que meu cálculo físico no Gravity.cs seja executado sempre que o jogo for atualizado, em um thread separado, para que o cálculo não diminua o jogo para um FPS horrivelmente baixo (0-2).

Como eu faria para fazer esse rosqueamento funcionar? (quaisquer sugestões para um sistema de gravidade planetária aprimorado são bem-vindas, se alguém as tiver)

Também não estou procurando uma lição sobre por que não devo usar o encadeamento ou os perigos de usá-lo incorretamente. Estou procurando uma resposta direta sobre como fazê-lo. Eu já passei uma hora pesquisando essa questão com poucos resultados que entendi ou que foram úteis. Não quero parecer grosseiro, mas sempre parece difícil para um noob de programação obter uma resposta direta significativa. Geralmente, prefiro uma resposta tão complexa que seria capaz de resolver meu problema com facilidade, se eu entendesse isso, ou alguém dizendo por que não devo fazer o que quero e não oferecendo alternativas (que são úteis).

Obrigado pela ajuda!

Edição : Depois de ler as respostas que recebi, vejo que vocês realmente se importam e não estão apenas tentando dizer uma resposta que possa funcionar. Eu queria matar dois coelhos com uma cajadada (melhorando o desempenho e aprendendo algumas noções básicas de multithread), mas parece que a maior parte do problema está nos meus cálculos e que o threading é mais problemático do que vale a pena aumentar o desempenho. Obrigado a todos, vou ler suas respostas novamente e experimentar suas soluções quando terminar a escola, obrigado novamente!

O que você tem aqui é um algoritmo O (n²) clássico . A causa raiz do seu problema não tem nada a ver com encadeamento e tudo a ver com o fato de seu algoritmo ter uma alta complexidade.

Se você não encontrou a notação "Big O" antes, significa basicamente o número de operações necessárias para trabalhar em n elementos (esta é a explicação super simplificada). Seus 100 elementos estão executando a parte interna do seu loop 10000 vezes .

No desenvolvimento de jogos, você geralmente deseja evitar algoritmos O (n²) , a menos que tenha uma quantidade pequena (e de preferência fixa ou limitada) de dados e um algoritmo muito rápido.

Se todas as entidades estivessem afetando todas as outras, você exigiria, necessariamente, um algoritmo O (n²). Mas parece que apenas algumas entidades estão realmente interagindo (devido a if (distance < ...)) - portanto, você pode reduzir significativamente seu número de operações usando algo chamado " Particionamento Espacial ".

Como este é um tópico bastante detalhado e um pouco específico do jogo, recomendo que faça uma nova pergunta para obter mais detalhes. Vamos continuar...

Um dos principais problemas de desempenho do seu código é bastante simples. Isso é muito lento :

foreach (KeyValuePair<string, Entity> e in Entities)
{
    Entities[e.Key].Update();
}

Você está fazendo uma pesquisa no dicionário por string, a cada iteração (várias vezes em seus outros loops), para um objeto que você já possui!

Você poderia fazer isso:

foreach (KeyValuePair<string, Entity> e in Entities)
{
    e.Value.Update();
}

Ou você pode fazer o seguinte: (Eu pessoalmente gosto mais disso, ambos devem ter a mesma velocidade)

foreach (Entity e in Entities.Values)
{
    e.Update();
}

Uma pesquisa no dicionário por string é bem lenta. A iteração direta será significativamente mais rápida.

Embora, com que frequência você realmente precisa procurar itens pelo nome? Comparado com a frequência com que você deve percorrer todos eles? Se você fizer pesquisas de nome apenas raramente, considere armazenar suas entidades em List(dê um Namemembro a elas ).

O código que você realmente tem lá é relativamente trivial. Não criei um perfil, mas aposto que a maior parte do seu tempo de execução está nas pesquisas repetidas do dicionário . Seu código pode ser "rápido o suficiente" apenas corrigindo esse problema.

EDIT: O próximo maior problema provavelmente é chamar Atan2e imediatamente convertê-lo novamente em um vetor com Sine Cos! Basta usar o vetor diretamente.

Por fim, vamos abordar o encadeamento e os principais problemas do seu código:

Primeiro e mais obviamente: não crie um novo tópico a cada quadro! Objetos de segmento são bastante "pesados". A solução mais simples para isso seria simplesmente usar ThreadPool.

Claro, não é assim tão simples. Vamos para o problema número dois: não toque em dados em dois threads ao mesmo tempo! (Sem adicionar a infraestrutura de segurança de thread apropriada.)

Você está basicamente acumulando memória aqui da maneira mais horrível . Não há segurança para threads aqui. Qualquer um dos vários " gravity.Update" threads que você está iniciando pode substituir os dados usados ​​em outro thread em momentos inesperados. Enquanto isso, seu segmento principal também estará tocando todas essas estruturas de dados. Eu não ficaria surpreso se esse código produzisse violações de acesso à memória difíceis de reproduzir.

Tornar algo como esse encadeamento seguro é difícil e pode adicionar uma sobrecarga significativa de desempenho, de modo que geralmente não vale a pena o esforço.

Mas, vendo como você perguntou (não tão) bem sobre como fazê-lo, vamos falar sobre isso ...

Normalmente, eu recomendaria começar praticando algo simples, onde seu tópico é basicamente "disparar e esquecer". Tocar áudio, gravar algo no disco, etc. As coisas ficam complicadas quando você precisa alimentar o resultado de volta no thread principal.

Existem basicamente três abordagens para o seu problema:

1) Coloque bloqueios em torno de todos os dados que você usa nos threads. Em C #, isso é bastante simples com a lockdeclaração.

Geralmente, você cria (e retém!) Um new objectespecificamente para bloqueio para proteger algum conjunto de dados (é por razões de segurança que geralmente surgem ao escrever APIs públicas - mas com bom estilo ao mesmo tempo). Você deve bloquear seu objeto de bloqueio em todos os lugares em que acessar os dados que ele protege!

Obviamente, se algo estiver "bloqueado" por um encadeamento porque está em uso e outro encadeamento tentar acessá-lo - esse segundo encadeamento será forçado a esperar até que o primeiro encadeamento seja concluído. Portanto, a menos que você selecione cuidadosamente as tarefas que podem ser executadas em paralelo, basicamente obterá desempenho de thread único (ou pior).

Portanto, no seu caso, não há sentido em fazer isso, a menos que você possa arquitetar seu jogo de forma que outro código seja executado em paralelo que não toque sua coleção de entidades.

2) Copie os dados no encadeamento, deixe-o processar e retire o resultado novamente quando terminar.

Exatamente como você implementa isso depende do que você está fazendo. Mas, obviamente, isso envolverá uma operação de cópia potencialmente cara (ou duas) que, em muitos casos, será mais lenta do que apenas fazer coisas de thread único.

E, é claro, você ainda precisa fazer outro trabalho em segundo plano; caso contrário, seu encadeamento principal ficará parado aguardando o término do outro encadeamento para que possa copiar os dados de volta!

3) Use estruturas de dados seguras para encadeamento.

Eles são um pouco mais lentos do que seus equivalentes de rosca única e geralmente mais difíceis de usar do que o bloqueio simples. Eles ainda podem exibir os problemas de travamento (reduzindo o desempenho em um único encadeamento), a menos que você os use com cuidado.

Por fim, como se trata de uma simulação baseada em quadro, será necessário que o encadeamento principal aguarde que outros encadeamentos forneçam seus resultados, para que o quadro seja renderizado e a simulação possa continuar. Uma explicação completa é realmente muito longa para colocar aqui, mas basicamente você vai querer aprender como usar Monitor.Waite Monitor.Pulse. Aqui está um artigo para você começar .

Sei que não forneci detalhes de implementação específicos (exceto o último bit) ou código para qualquer uma dessas abordagens. Primeiro de tudo, haveria muito o que cobrir. E, em segundo lugar, nenhum deles é aplicável ao seu código por si só - você precisa abordar toda a sua arquitetura com o objetivo de adicionar threading.

O encadeamento não irá magicamente o código que você tem lá mais rapidamente - apenas permite que você faça outra coisa ao mesmo tempo!

Ok, à primeira vista, há algumas coisas que você deve experimentar. No começo, você deve tentar reduzir as verificações de colisão, usando um tipo de estrutura espacial como um quadtree . Isso permitirá que você reduza a segunda contagem foreach, pois somente consultará entidades que fechem a primeira.

Em relação ao seu encadeamento: tente não criar um encadeamento a cada turno de atualização. Essa sobrecarga talvez esteja atrasando mais o seu desempenho do que acelerando as coisas. Em vez disso, tente criar um único segmento de colisão e deixe-o fazer o trabalho por você. Não tenho uma abordagem concreta de copiar e colar este código , mas há artigos sobre sincronização de threads e trabalho em segundo plano para C #.

Outro ponto é que no loop foreach você não precisa fazer isso entityEngine.Entities[e.Key].Textureporque já acessou o dict no cabeçalho foreach. Em vez disso, você pode apenas escrever e.Texture. Eu realmente não sei o impacto disso, só queria que você soubesse;)

Uma última coisa: no momento, você está verificando duas vezes cada entidade, porque ela é consultada no primeiro e no segundo loop foreach.

Exemplo com 2 entidades A e B:

pick A in first foreach loop
   pick A in second foreach loop
      skip A because keys are the same
   pick B in second foreach loop
      collision stuff
pick B in first foreach loop
   pick A in second foreach loop
      collision stuff
   pick B in second foreach loop
      skip B because keys are the same

Embora essa seja uma abordagem possível, talvez você possa lidar com A e B em um turno, pulando metade das verificações de colisão

Espero que isso ajude você =)

PS: Mesmo que você tenha dito que não quer ouvi-lo: tente manter a detecção de colisão no mesmo encadeamento e apenas aumente a velocidade. Rosquear parece uma boa ideia, mas com isso vem a necessidade de sincronizar como o inferno. Se a verificação de colisão for mais lenta que a sua atualização (motivo para a segmentação), você receberá falhas e erros, porque a colisão será acionada depois que os navios já se moverem e vice-versa. Não quero desencorajar você, isso é apenas uma experiência pessoal.

EDIT1: Links com o tutorial QuadTree (Java): http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

Honestamente, a primeira coisa que você deve fazer é mudar para um algoritmo melhor.

Paralelamente, sua simulação pode, mesmo na melhor das hipóteses, acelerá-la apenas por um fator igual ao número de CPUs × núcleos por CPU × threads por núcleo disponível em seu sistema - ou seja, algo entre 4 e 16 para um PC moderno. (Mover seu código para a GPU pode gerar fatores de paralelização muito mais impressionantes, com um custo adicional de complexidade de desenvolvimento e uma velocidade de computação de linha de base por thread mais baixa.) Com um algoritmo O (n²), como seu código de exemplo, isso permite que você use de 2 a 4 vezes mais partículas que você possui atualmente.

Por outro lado, mudar para um algoritmo mais eficiente pode acelerar a simulação com facilidade, digamos, um fator de 100 a 10000 (números puramente estimados). A complexidade do tempo dos bons algoritmos de simulação de n corpos usando subdivisão espacial varia aproximadamente como O (n log n), que é "quase linear", de modo que você pode esperar quase o mesmo fator de aumento no número de partículas que você pode manipular. Além disso, isso ainda estaria usando apenas um encadeamento; portanto, ainda haveria espaço para paralelização em cima disso .

De qualquer forma, como as outras respostas observaram, o truque geral para simular com eficiência um grande número de partículas em interação é organizá-las em um quadtree (em 2D) ou um octree (em 3D). Em particular, para simular a gravidade, o algoritmo básico que você deseja usar é o algoritmo de simulação Barnes – Hut , no qual você armazena a massa total (e o centro de massa) de todas as partículas contidas em cada célula do seu quad / octree e use isso para aproximar o efeito gravitacional médio das partículas naquela célula em outras partículas distantes.

Você pode encontrar muitas descrições e tutoriais no algoritmo Barnes – Hut, pesquisando no Google, mas aqui está um bom e simples para você começar , enquanto aqui está a descrição de uma implementação avançada usada para simulação de colisões de galáxias por GPU.

Outra resposta de otimização que não tem nada a ver com threads. Me desculpe por isso.

Você está calculando a distância () de cada par. Isso envolve obter uma raiz quadrada, que é lenta. Também envolve várias pesquisas de objetos para obter os tamanhos reais.

Você pode otimizar isso usando a função DistanceSquared (). Pré-calcule a distância máxima na qual dois objetos podem interagir, ajuste-o ao quadrado e compare-o com o DistanceSquared (). Se e somente se a distância ao quadrado estiver dentro do máximo, pegue a raiz quadrada e compare-a com o tamanho real do objeto.

EDIT : Essa otimização é principalmente para quando você está testando colisões, o que eu notei agora não é realmente o que você está fazendo (embora você certamente o faça em algum momento). Ainda pode ser aplicável à sua situação, se todas as partículas tiverem tamanho / massa semelhante.

Eu não sei muito sobre segmentação, mas parece que seus loops estão demorando, então talvez mudando disso

i = 0; i < count; i++
  j = 0; j < count; j++

  object_i += force(object_j);

para isso

i = 0; i < count-1; i++
  j = i+1; j < count; j++

  object_i += force(object_j);
  object_j += force(object_i);

Poderia ajudar

Se você já tem problemas enormes com 10 objetos simulados, precisará otimizar o código! Seu loop aninhado causaria apenas 10 * 10 iterações, das quais 10 são ignoradas (mesmo objeto), resultando em 90 iterações do loop interno. Se você atingir apenas 2 FPS, isso significa que seu desempenho é tão ruim que você alcança apenas 180 iterações do loop interno por segundo.

Eu sugiro que você faça o seguinte:

1. PREPARAÇÃO / REFERÊNCIA: Para saber com certeza que essa rotina é o problema, escreva uma pequena rotina de referência. Ele deve executar o Update()método da Gravidade várias vezes, por exemplo, 1000 vezes e medir sua hora. Se você deseja atingir 30 FPS com 100 objetos, simule 100 objetos e meça o tempo de 30 execuções. Deve ser inferior a 1 segundo. É necessário usar essa referência para fazer otimizações razoáveis. Caso contrário, você provavelmente alcançará o oposto e tornará o código mais lento, porque você acha que deve ser mais rápido ... Então, eu realmente o encorajo a fazer isso!

2. OTIMIZAÇÕES: Embora você não possa fazer muito sobre o problema do esforço O (N²) (ou seja: o tempo de cálculo aumenta quadraticamente com o número de objetos simulados N), você pode melhorar o próprio código.

   a) Você usa muitas pesquisas de "matriz associativa" (Dicionário) em seu código. Estes são lentos! Por exemplo entityEngine.Entities[e.Key].Position. Você não pode simplesmente usar e.Value.Position? Isso salva uma pesquisa. Você faz isso em qualquer lugar do loop interno para acessar as propriedades dos objetos referenciados por e e e2 ... Altere isso! b) Você cria um novo vetor dentro do loop new Vector2( .... ). Todas as chamadas "novas" implicam em alguma alocação de memória (e mais tarde: desalocação). Estes são ainda mais lentos que as pesquisas de dicionários. Se você precisar apenas deste vetor temporariamente, aloque-o fora dos loops E-reutilize-o reinicializando seus valores para os novos valores, em vez de criar um novo objeto. c) Você usa muitas funções trigonométricas (por exemplo, atan2ecos) dentro do loop. Se sua precisão não precisar realmente ser exata, tente usar uma tabela de pesquisa. Para fazer isso, você dimensiona seu valor para um intervalo definido, arredonde-o para um valor inteiro e procure-o em uma tabela de resultados pré-calculados. Se você precisar de ajuda com isso, basta perguntar. d) Você costuma usar .Texture.Width / 2. Você pode pré-calcular isso e armazenar o resultado como .Texture.HalfWidthou - se esse é sempre um valor inteiro positivo - você pode usar a operação de deslocamento de bits>> 1 dividir por dois.

Faça apenas uma das alterações de cada vez e meça a alteração pelo benchmark para ver como isso afetou seu tempo de execução! Talvez uma coisa seja boa enquanto a outra ideia foi ruim (até eu as propus acima!) ...

Eu acho que essas otimizações serão muito melhores do que tentar obter melhor desempenho usando vários threads! Você terá muitos problemas para coordenar os threads, para que eles não substituam os outros valores. Eles também entrarão em conflito ao acessar regiões de memória semelhantes também. Se você usar 4 CPUs / Threads para este trabalho, poderá esperar apenas uma velocidade de 2 a 3 para a taxa de quadros.

Você é capaz de retrabalhá-lo sem as linhas de criação do objeto?

Vector2 Force = novo Vector2 ();

Vector2 VecForce = novo Vector2 ((flutuante) Math.Cos (ângulo), (flutuante) Math.Sin (ângulo));

se talvez você pudesse colocar o valor da força na entidade em vez de criar dois novos objetos a cada vez, isso pode ajudar a melhorar o desempenho.