Estrutura de dados (ou algoritmo) para pesquisas rápidas de entidades baseadas em distância

8

Por exemplo, seu jogo tem 100 inimigos (em equipes diferentes) rodando e a IA deles quer inspecionar as entidades próximas para ver quais atacar. Qual é a maneira mais rápida de organizar essas entidades para que cada inimigo não precise calcular a distância entre si e todas as outras entidades?

Em resumo, qual é a maneira mais rápida de uma entidade de IA responder à pergunta "Quem está perto de mim?"

3d ai entity-system data-structure khayman218
fonte
tente usar árvores quad
Ali1S232 17/08
11
gamedev.stackexchange.com/questions/12318/…
Tetrad

Respostas:

8

Você deseja um índice espacial, como quadtree (2D) ou octree (3D).

Vai
fonte
11
@FxIII Não sei se sigo o que você está falando. Essas estruturas de dados em árvore espacial são projetadas especificamente para responder à pergunta do pôster e são bem compreendidas e usadas.
Will
5

A solução mais simples é uma grade . Coloque uma grade 2D sobre o seu nível. Cada célula na grade mantém uma coleção de quais entidades a estão ocupando no momento. À medida que as entidades se movem, retire-as da célula em que estão saindo e adicione-as à que elas entrarem.

Você pode encontrar entidades próximas apenas examinando as células próximas. Uma quadtree refina isso subdividindo recursivamente a grade, mas às vezes uma plana é adequada, especialmente se o tamanho do seu nível for fixo e relativamente pequeno.

maravilhoso
fonte