Melhorando uma função O (N ^ 2) (todas as entidades iterando sobre todas as outras entidades)

Um pouco de experiência, estou codificando um jogo de evolução com um amigo em C ++, usando ENTT para o sistema de entidades. As criaturas andam em um mapa 2D, comem verduras ou outras criaturas, se reproduzem e suas características mudam.

Além disso, o desempenho é bom (60fps sem problemas) quando o jogo é executado em tempo real, mas eu quero ser capaz de acelerar significativamente para não ter que esperar 4h para ver alterações significativas. Então, eu quero obtê-lo o mais rápido possível.

Estou lutando para encontrar um método eficiente para as criaturas encontrarem sua comida. Cada criatura deve procurar a melhor comida que esteja perto o suficiente deles.

Se quiser comer, a criatura retratada no centro deve olhar em torno de si em um raio de 149,64 (sua distância de visão) e julgar qual alimento deve buscar, com base na nutrição, distância e tipo (carne ou planta) .

A função responsável por encontrar todas as criaturas que sua comida consome cerca de 70% do tempo de execução. Simplificando como está escrito atualmente, é mais ou menos assim:

for (creature : all_creatures)
{
  for (food : all_entities_with_food_value)
  {
    // if the food is within the creatures view and it's
    // the best food found yet, it becomes the best food
  }
  // set the best food as the target for creature
  // make the creature chase it (change its state)
}

Esta função é executada a cada escala para todas as criaturas que procuram comida, até que a criatura encontre comida e mude de estado. Também é executada toda vez que novos alimentos aparecem para criaturas que já perseguem um determinado alimento, para garantir que todos sigam a melhor comida disponível para eles.

Estou aberto a idéias sobre como tornar esse processo mais eficiente. Adoraria reduzir a complexidade de $O(N^2)$ , mas não sei se isso é possível.

Uma maneira de eu já melhorar é classificando o all_entities_with_food_valuegrupo para que, quando uma criatura interage com alimentos grandes demais para comer, pare por aí. Quaisquer outras melhorias são mais que bem-vindas!

EDIT: Obrigado a todos pelas respostas! Eu implementei várias coisas de várias respostas:

Em primeiro lugar, eu simplesmente fiz isso para que a função culpada fosse executada apenas uma vez a cada cinco ticks, o que tornava o jogo cerca de 4x mais rápido, sem alterar visivelmente nada sobre o jogo.

Depois disso, guardei no sistema de busca de alimentos uma matriz com os alimentos gerados no mesmo carrapato que ele executa. Dessa forma, eu só preciso comparar os alimentos que a criatura está perseguindo com os novos que apareceram.

Por fim, depois de pesquisar o particionamento espacial e considerar o BVH e o quadtree, fui com o último, pois sinto que é muito mais simples e mais adequado ao meu caso. Eu o implementei rapidamente e melhorou muito o desempenho, a pesquisa de alimentos mal leva tempo!

Agora a renderização é o que está me atrasando, mas isso é um problema para outro dia. Obrigado a todos!

Eu sei que você não conceitua isso como colisões, no entanto, o que você está fazendo é colidir um círculo centrado na criatura, com todos os alimentos.

Você realmente não deseja verificar os alimentos que sabe que estão distantes, apenas o que está próximo. Esse é o conselho geral para otimização de colisão. Gostaria de incentivar a pesquisa de técnicas para otimizar colisões e não se limite ao C ++ ao pesquisar.

Criatura que encontra comida

Para o seu cenário, sugiro colocar o mundo em uma grade. Faça as células pelo menos no raio dos círculos que você deseja colidir. Em seguida, você pode escolher a célula na qual a criatura está localizada e seus até oito vizinhos e pesquisar apenas as até nove células.

Nota : você pode criar células menores, o que significa que o círculo que você está pesquisando se estenderá além dos vizinhos imidiados, exigindo que você itere lá. No entanto, se o problema é que há muita comida, células menores podem significar iteração sobre menos entidades alimentares no total, o que, em algum momento, vira a seu favor. Se você suspeitar que este é o caso, teste.

Se o alimento não se mover, você poderá adicionar as entidades de alimentos à grade na criação, para não precisar pesquisar quais entidades estão na célula. Em vez disso, você consulta a célula e ela possui a lista.

Se você transformar o tamanho das células em uma potência de duas, poderá encontrar a célula na qual a criatura está localizada simplesmente truncando suas coordenadas.

Você pode trabalhar com a distância ao quadrado (também conhecida como não executar sqrt) ao comparar para encontrar a mais próxima. Menos operações sqrt significam uma execução mais rápida.

Novos alimentos adicionados

Quando novos alimentos são adicionados, apenas as criaturas próximas precisam ser despertadas. É a mesma idéia, exceto que agora você precisa obter a lista de criaturas nas células.

Muito mais interessante, se você anotar na criatura a que distância ela está do alimento que está perseguindo ... você pode verificar diretamente contra essa distância.

Outra coisa que o ajudará é ter a comida ciente de que criaturas a estão perseguindo. Isso permitirá que você execute o código para encontrar comida para todas as criaturas que estão perseguindo um pedaço de comida que acabou de ser comido.

De fato, inicie a simulação sem comida e quaisquer criaturas têm uma distância anotada do infinito. Então comece a adicionar comida. Atualize as distâncias à medida que as criaturas se movem ... Quando a comida é comida, pegue a lista de criaturas que a perseguiam e encontre um novo alvo. Além desse caso, todas as outras atualizações são tratadas quando alimentos são adicionados.

Ignorando simulação

Conhecendo a velocidade de uma criatura, você sabe quanto é até atingir seu alvo. Se todas as criaturas tiverem a mesma velocidade, a que alcançará primeiro é a que tiver a menor distância anotada.

Se você também sabe o tempo até adicionar mais comida ... E, esperançosamente, você tem uma previsibilidade semelhante para reprodução e morte, então você sabe o tempo para o próximo evento (comida adicionada ou criatura comendo).

Pule para esse momento. Você não precisa simular criaturas se movendo.

Você deve adotar um algoritmo de particionamento de espaço como o BVH para reduzir a complexidade. Para ser específico ao seu caso, você precisa criar uma árvore que consiste em caixas delimitadoras alinhadas ao eixo que contêm pedaços de comida.

Para criar uma hierarquia, coloque pedaços de alimentos próximos uns dos outros nos AABBs e depois coloque esses AABBs em AABBs maiores, novamente, pela distância entre eles. Faça isso até ter um nó raiz.

Para usar a árvore, primeiro execute um teste de interseção círculo-AABB contra um nó raiz e, em caso de colisão, teste contra filhos de cada nó consecutivo. No final, você deve ter um grupo de pedaços de comida.

Você também pode fazer uso da biblioteca AABB.cc.

Embora os métodos de partição de espaço descritos possam reduzir o tempo, seu principal problema não é apenas a pesquisa. É o grande volume de pesquisas que você faz que torna sua tarefa lenta. Então, você está otimizando o loop interno, mas você também pode otimizar o loop externo.

Seu problema é que você continua pesquisando dados. É um pouco como ter filhos no banco de trás pedindo milésima vez "já chegamos lá", não há necessidade de fazer isso que o motorista informará quando você estiver lá.

Em vez disso, você deve se esforçar, se possível, para resolver cada ação até sua conclusão, colocá-la em uma fila e liberar esses eventos de bolha. Isso pode fazer alterações na fila, mas tudo bem. Isso é chamado de simulação de evento discreto. Se você puder implementar sua simulação dessa maneira, estará procurando por uma aceleração considerável que supera em muito a aceleração que pode obter com a melhor pesquisa de partição de espaço.

Para enfatizar o ponto em uma carreira anterior, fiz simuladores de fábrica. Simulamos semanas de grandes fábricas / aeroportos todo o fluxo de material em cada nível de item com esse método em menos de uma hora. Embora a simulação baseada em timestep só possa simular 4-5 vezes mais rápido que o tempo real.

Também como uma fruta muito baixa, considere desacoplar suas rotinas de desenho da sua simulação. Mesmo que sua simulação seja simples, ainda há alguma sobrecarga de desenhar coisas. Pior ainda, o driver de vídeo pode estar limitando você a x atualizações por segundo, enquanto na realidade seus processadores podem fazer coisas centenas de vezes mais rápido. Isso enfatiza a necessidade de criação de perfil.

Você pode usar um algoritmo de linha de varredura para reduzir a complexidade para Nlog (N). A teoria é a dos diagramas de Voronoi, que dividem a área em torno de uma criatura em regiões que consistem em todos os pontos mais próximos a ela do que qualquer outra.

O chamado algoritmo da Fortune faz isso em Nlog (N), e a página da wiki contém pseudo-código para implementá-lo. Estou certo de que existem implementações de bibliotecas por aí também. https://en.wikipedia.org/wiki/Fortune%27s_algorithm

A solução mais fácil seria integrar um mecanismo de física e usar apenas o algoritmo de detecção de colisão. Basta criar um círculo / esfera em torno de cada entidade e deixar o mecanismo de física calcular as colisões. Para 2D, eu sugeriria Box2D ou Chipmunk e Bullet para 3D.

Se você acha que integrar um mecanismo de física inteiro é demais, sugiro examinar os algoritmos de colisão específicos. A maioria das bibliotecas de detecção de colisões funciona em duas etapas:

• Detecção de fase ampla: o objetivo desse estágio é obter a lista de pares de objetos candidatos que podem colidir o mais rápido possível. Duas opções comuns são:
  • Varredura e poda : classifique as caixas delimitadoras ao longo do eixo X e marque o par de objetos que se cruzam. Repita para todos os outros eixos. Se um par candidato passar em todos os testes, ele passará para o próximo estágio. Esse algoritmo é muito bom em explorar a coerência temporal: você pode manter as listas de entidades classificadas e atualizá-las a cada quadro, mas como elas são quase classificadas, será muito rápido. Ele também explora a coerência espacial: como as entidades são classificadas em ordem espacial crescente, quando você está verificando colisões, pode parar assim que uma entidade não colide, porque todas as próximas estarão mais distantes.
  • Estruturas de dados de particionamento espacial, como quadríceps, octrees e grades. As grades são fáceis de implementar, mas podem ser muito inúteis se a densidade da entidade for baixa e muito difícil de implementar para o espaço ilimitado. As árvores espaciais estáticas também são fáceis de implementar, mas difíceis de equilibrar ou atualizar no local; portanto, você precisará reconstruí-lo a cada quadro.
• Fase estreita: os pares candidatos encontrados na fase ampla são testados com algoritmos mais precisos.