Como otimizar a função de distância?

23

Ao desenvolver um jogo RTS razoavelmente simples, notei que meus cálculos de distância estavam causando um impacto no desempenho.

Em todos os momentos, há verificações de distância para saber se uma unidade está dentro do alcance do alvo, se o projétil atingiu o alvo, se o jogador atropelou uma partida, colisão geral, etc. A lista continua e verifica se a distância entre dois pontos é muito usada.

Minha pergunta é exatamente sobre isso. Quero saber quais alternativas os desenvolvedores de jogos têm para verificar distâncias, além da abordagem usual sqrt (x * x + y * y), que consome bastante tempo se estiver sendo executada milhares de vezes por quadro.

Gostaria de ressaltar que estou ciente das comparações entre distâncias de Manhattan e distâncias quadradas (ignorando o gargalo do sqrt). Algo mais?

Grimshaw
fonte
Se você tiver objetos que não espera mover, como edifícios, por exemplo, pode valer a pena pegar uma série 2D de taylor da função de distância, truncá-la no termo do quadrado e armazenar a função resultante como a função de distância daquele edifício em particular. Isso realocaria parte do trabalho pesado para a inicialização e poderia acelerar um pouco as coisas.
Alexander Gruber

Respostas:

26

TL; DR; Seu problema não está em executar a função de distância. Seu problema está executando a função de distância tantas vezes. Em outras palavras, você precisa de uma otimização algorítmica em vez de matemática.

[EDIT] Estou excluindo a primeira seção da minha resposta, porque as pessoas estão odiando. O título da pergunta pedia funções de distância alternativas antes da edição.

Você está usando uma função de distância na qual calcula a raiz quadrada sempre. No entanto, você pode simplesmente substituí-lo sem usar a raiz quadrada e calcular a distância ao quadrado. Isso economizará muitos ciclos preciosos.

Distância ^ 2 = x * x + y * y;

esse é realmente um truque comum. Mas você precisa ajustar seus cálculos de acordo. Também pode ser usado como verificação inicial antes de calcular a distância real. Assim, por exemplo, em vez de calcular a distância real entre dois pontos / esferas para um teste de interseção, podemos calcular a Distância ao quadrado e comparar com o raio ao quadrado em vez do raio.

Edit, bem depois que @ Byte56 apontou que eu não li a pergunta e que você estava ciente da otimização da distância ao quadrado.

Bem, no seu caso, infelizmente, estamos na computação gráfica lidando quase exclusivamente com o Espaço Euclidiano , e a distância é exatamente definida como Sqrt of Vector dot itselfno espaço euclidiano.

Distância ao quadrado é a melhor aproximação que você obterá (em termos de desempenho), não consigo ver nada superando 2 multiplicações, uma adição e uma tarefa.

Então você diz que não posso otimizar a função de distância, o que devo fazer?

Seu problema não está em executar a função de distância. Seu problema está executando a função de distância tantas vezes. Em outras palavras, você precisa de uma otimização algorítmica em vez de matemática.

O ponto é, em vez de verificar a interseção do jogador com cada objeto na cena, cada quadro. Você pode usar facilmente a coerência espacial em seu proveito e verificar apenas os objetos que estão próximos ao player (com maior probabilidade de acertar / cruzar).

Isso pode ser feito facilmente, armazenando essas informações espaciais em uma estrutura de dados de particionamento espacial . Para um jogo simples, sugiro um Grid, porque é basicamente fácil de implementar e se encaixa perfeitamente na cena dinâmica.

Cada célula / caixa contém uma lista de objetos que a caixa delimitadora da grade inclui. E é fácil rastrear a posição do jogador nessas células. E para os cálculos de distância, você só verifica a distância do jogador com esses objetos dentro da mesma célula ou nas células vizinhas, em vez de tudo na cena.

Uma abordagem mais complicada é usar BSP ou Octrees.

concept3d
fonte
2
Acredito que a última frase da pergunta diz que o OP está procurando outras alternativas (eles sabem como usar a distância ao quadrado).
MichaelHouse
@ Byte56 sim, você está correto, eu não li isso.
concept3d
Obrigado por você responder de qualquer maneira. Você acrescentaria uma frase confirmando que, embora esse método não nos dê uma distância euclidiana, é muito preciso nas comparações? Eu acho que isso adicionaria algo a alguém vindo aqui de um mecanismo de pesquisa.
Grimshaw
@ Grimshaw Eu editei a resposta para resolver o problema original.
concept3d
@ Byte56 obrigado por apontar. Eu editei a resposta.
concept3d
29

Se você precisar de algo que permaneça linear a qualquer distância (ao contrário distance^2) e, no entanto, pareça vagamente circular (ao contrário das distâncias quadradas de Chebyshev e Manhattan, como diamante), você pode calcular a média das duas últimas técnicas para obter uma aproximação de distância em formato octogonal:

dx = abs(x1 - x0)
dy = abs(y1 - y0)

dist = 0.5 * (dx + dy + max(dx, dy))

Aqui está uma visualização (plotagem de contorno) da função, graças ao Wolfram Alpha :

Gráfico de Contorno

E aqui está um gráfico de sua função de erro quando comparado à distância euclidiana (radianos, somente no primeiro quadrante):

Gráfico de erro

Como você pode ver, o erro varia de 0% nos eixos a aproximadamente + 12% nos lobos. Ao modificar um pouco os coeficientes, podemos reduzi-lo para +/- 4%:

dist = 0.4 * (dx + dy) + 0.56 * max(dx, dy)

insira a descrição da imagem aqui

Atualizar

Usando os coeficientes acima, o erro máximo estará dentro de +/- 4%, mas o erro médio ainda será de + 1,3%. Otimizado para erro médio zero, você pode usar:

dist = 0.394 * (dx + dy) + 0.554 * max(dx, dy)

que gera erros entre -5% e + 3% e um erro médio de + 0,043%


Ao pesquisar na Web por um nome para esse algoritmo, encontrei essa aproximação octogonal semelhante :

dist = 1007/1024 * max(dx, dy) + 441/1024 * min(dx, dy)

Observe que isso é essencialmente equivalente (embora os expoentes sejam diferentes - esses dão um erro de -1,5% a 7,5%, mas podem ser massageados em +/- 4%) porque max(dx, dy) + min(dx, dy) == dx + dy. Usando este formulário, as chamadas mine maxpodem ser fatoradas em favor de:

if (dy > dx)
    swap(dx, dy)

dist = 1007/1024 * dx + 441/1024 * dy

Isso vai ser mais rápido que a minha versão? Quem sabe ... depende do compilador e de como ele otimiza cada um para a plataforma de destino. Meu palpite é que seria muito difícil ver alguma diferença.

bcrist
fonte
3
Interessante, não vi isso antes! Tem um nome ou apenas "média de Chebyshev e Manhattan"?
congusbongus
@congusbongus Provavelmente tem um nome, mas não sei o que é. Se não, talvez um dia ele vai ser chamado a Distância Crist (hah ... provavelmente não)
bcrist
1
Observe que as multiplicações de ponto flutuante não são muito eficientes. É por isso que a outra aproximação usa 1007/1024 (que será implementada como multiplicação de números inteiros seguida de deslocamento de bits).
MSalters
@MSalters Sim, as operações de ponto flutuante geralmente são mais lentas que as operações com números inteiros, mas isso é irrelevante - 0,4 e 0,56 poderiam ser facilmente convertidos para usar operações com números inteiros. Além disso, no hardware x86 moderno, a maioria das operações de ponto flutuante (além de FDIV, FSQRTe outras funções transcendentais) custa essencialmente o mesmo que suas versões inteiras: 1 ou 2 ciclos por instrução.
bcrist
1
Isso parece muito semelhante à Alpha max + Beta Min: en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algorithm
drake7707
21

Às vezes, essa pergunta pode surgir não pelo custo de realizar cálculos de distância, mas pelo número de vezes que o cálculo está sendo feito.

Em um grande mundo de jogos com muitos atores, não é escalável verificar a distância entre um ator e todos os outros. À medida que mais jogadores, NPCs e projéteis entrar no mundo, o número de comparações que precisam ser feitas irá crescer de forma quadrática com O(N^2).

Uma maneira de reduzir esse crescimento é usar uma boa estrutura de dados para descartar rapidamente atores indesejados dos cálculos.

Estamos procurando uma maneira de iterar com eficiência todos os atores que possam estar ao alcance, excluindo a maioria dos atores que estão definitivamente fora do alcance .

Se seus atores estão distribuídos de maneira bastante uniforme pelo espaço mundial, uma grade de baldes deve ser uma estrutura adequada (como sugere a resposta aceita). Mantendo as referências aos atores em uma grade grossa, você precisa apenas verificar alguns dos baldes próximos para cobrir todos os atores que possam estar ao alcance, ignorando o restante. Quando um ator se move, pode ser necessário movê-lo de seu antigo balde para um novo.

Para atores dispersos de maneira menos uniforme, uma quadtree pode se sair melhor em um mundo bidimensional, ou uma octree seria adequada para um mundo tridimensional. Essas são estruturas de propósito mais geral que podem particionar eficientemente grandes áreas de espaço vazio e pequenas áreas contendo muitos atores. Para atores estáticos , existe o BSP ( binary space particitioning), que é muito rápido para pesquisar, mas é muito caro para atualizar em tempo real. Os BSPs separam o espaço usando planos para cortá-lo ao meio repetidamente e podem ser aplicados a qualquer número de dimensões.

É claro que existem custos indiretos para manter os atores com essa estrutura, especialmente quando eles estão se movendo entre as partições. Porém, em um mundo grande, com muitos atores, mas com pequenas faixas de interesse, os custos devem ser bem menores do que os incorridos pela comparação ingênua de todos os objetos.

A consideração de como a despesa de um algoritmo aumenta à medida que recebe mais dados é crucial para o design de software escalável. Às vezes, basta escolher a estrutura de dados correta . Os custos são geralmente descritos utilizando Big O notação .

(Sei que essa não é uma resposta direta à pergunta, mas pode ser útil para alguns leitores. Peço desculpas se perdi seu tempo!)

joeytwiddle
fonte
7
Esta é a melhor resposta. Não há nada para otimizar na função de distância; é preciso apenas usá-lo com menos frequência.
Sam Hocevar
3
A resposta aceita também abrange o particionamento espacial, caso contrário, sua resposta é realmente ótima. Obrigado.
precisa
Meu tempo foi muito bem gasto lendo sua resposta. Obrigado Joey.
Patrick M
1
Esta é a melhor resposta e a única que se concentra no problema real, e não no desempenho da função à distância. A resposta aceita também pode incluir particionamento espacial, mas é um aparte; ele se concentra no cálculo da distância. O cálculo da distância não é o principal problema aqui; otimizar o cálculo da distância é uma não solução de força bruta que não é dimensionada.
Maximus Minimus
Você poderia explicar por que o número de comparações seria exponencial? Eu pensei que seria quadrático, comparando cada ator entre si durante cada período de tempo.
Petr Pudlák
4

Que tal a distância de Chebyshev? Para os pontos p, q, é definido da seguinte forma:

distância

Portanto, para os pontos (2, 4) e (8, 5), a distância de Chebyshev é 6, como | 2-8 | > 4-5 |.

Além disso, seja E a distância euclidiana e C seja a distância de Chebyshev. Então:

distance2

O limite superior provavelmente não é muito útil, já que você teria que calcular a raiz quadrada, mas o limite inferior pode ser útil - sempre que a distância Chebyshev for grande o suficiente para ficar fora do alcance, a distância euclidiana também deve ser, poupando você de ter que calculá-lo.

A desvantagem, é claro, é que, se a distância Chebyshev estiver dentro do alcance, você terá que calcular a distância euclidiana de qualquer maneira, perdendo tempo. Apenas uma maneira de descobrir se será uma vitória líquida!

Tetrinity
fonte
1
Você também pode usar a distância de Manhattan como limite superior.
congusbongus
1
É verdade. Suponho que a partir daí seja apenas um salto, pule e pule para a "média de Chebyshev e Manhattan", como sugerido por bcrist.
Tetrinity
2

Uma otimização local muito simples é simplesmente verificar primeiro uma dimensão única.

Isso é :

distance ( x1, y1 , x1, y2) > fabs (x2 - x1)

Portanto, apenas verificar fabs (x2 - x1)como primeiro filtro pode proporcionar um ganho apreciável. Quanto dependerá do tamanho do mundo versus os intervalos relevantes.

Além disso, você pode usar isso como uma alternativa à estrutura de dados de particionamento espacial.

Se todos os objetos relevantes forem classificados em uma lista na ordem de coordenadas x, os objetos próximos deverão estar próximos na lista. Mesmo que a lista fique fora de ordem devido a não ser totalmente mantida à medida que os objetos se movem, dados limites de velocidade conhecidos, você ainda pode reduzir a seção da lista a ser pesquisada por objetos próximos.

Keith
fonte
2

Esforços foram feitos no passado para otimizar sqrt. Embora não se aplique mais às máquinas atuais, aqui está um exemplo do código-fonte do Quake, que usa o número mágico 0x5f3759df :

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the hell?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration (optional)
  // ...
  return y;
}

Uma explicação detalhada do que está acontecendo aqui pode ser encontrada na Wikipedia.

Em resumo, são algumas iterações do método de Newton (um algoritmo numérico que melhora iterativamente uma estimativa), com o número mágico usado para fornecer uma estimativa inicial razoável.

Como Travis aponta, esse tipo de otimização não é mais útil nas arquiteturas modernas. E mesmo que fosse, isso só poderia fornecer uma velocidade constante para o seu gargalo, enquanto o redesenho algorítmico pode obter melhores resultados.

joeytwiddle
fonte
2
Isso não é mais uma otimização que vale a pena. Quase todas as arquiteturas de PC de nível consumidor que você pode adquirir hoje em dia possuem instruções sqrt otimizadas para hardware que executam a raiz quadrada em um ciclo de clock ou menos. Se você realmente precisa do sqrt mais rápido possível, use a instrução sqrt de ponto flutuante x86 simd: en.wikipedia.org/wiki/… Para coisas como shaders na GPU, chamar o sqrt resultará automaticamente nessa instrução. Na CPU, presumo que muitos compiladores implementem o sqrt via SIMD sqrt, se disponível.
TravisG
@ TravisG Sim, vale a pena mencionar, por isso atualizei a resposta. Esta resposta foi fornecida apenas por diversão e interesse histórico!
precisa saber é o seguinte