¿Cómo optimizar la función de distancia?

23

Mientras desarrollaba un juego similar a RTS razonablemente simple, noté que mis cálculos de distancia estaban causando un impacto en el rendimiento.

En todo momento, hay controles de distancia para saber si una unidad está dentro del alcance de su objetivo, si el proyectil ha alcanzado su objetivo, si el jugador ha atropellado una recolección, una colisión general, etc. La lista continúa y verifica la distancia entre dos puntos se usa mucho.

Mi pregunta es exactamente sobre eso. Quiero saber qué alternativas tienen los desarrolladores de juegos para verificar distancias, además del enfoque sqrt (x * x + y * y) habitual, que consume bastante tiempo si lo estamos realizando miles de veces por cuadro.

Me gustaría señalar que conozco las distancias de Manhattan y las comparaciones de distancia al cuadrado (omitiendo el cuello de botella de sqrt). ¿Algo más?

Grimshaw
fuente
Si tiene objetos que no espera mover, como edificios, por ejemplo, podría valer la pena tomar una serie taylor 2D de la función de distancia, truncarla en el término cuadrado y luego almacenar la función resultante como función de distancia desde ese edificio en particular. Eso reubicaría parte del trabajo duro en la inicialización y podría acelerar un poco las cosas.
Alexander Gruber

Respuestas:

26

TL; DR; Su problema no es realizar la función de distancia. Su problema es realizar la función de distancia tantas veces. En otras palabras, necesita una optimización algorítmica en lugar de una matemática.

[EDITAR] Estoy borrando la primera sección de mi respuesta, porque la gente la odia. El título de la pregunta pedía funciones de distancia alternativas antes de la edición.

Estás utilizando una función de distancia donde estás calculando la raíz cuadrada cada vez. Sin embargo, simplemente puede reemplazar eso sin usar la raíz cuadrada y calcular la distancia al cuadrado en su lugar. Esto te ahorrará muchos ciclos preciosos.

Distancia ^ 2 = x * x + y * y;

Esto es realmente un truco común. Pero debe ajustar sus cálculos en consecuencia. También se puede usar como verificación inicial antes de calcular la distancia real. Entonces, por ejemplo, en lugar de calcular la distancia real entre dos puntos / esferas para una prueba de intersección, podemos calcular la Distancia al cuadrado y compararla con el radio al cuadrado en lugar del radio.

Edite, mucho después de que @ Byte56 señaló que no leí la pregunta y que estaba al tanto de la optimización de la distancia al cuadrado.

Bueno, en su caso, lamentablemente estamos en gráficos de computadora que tratan casi exclusivamente con el espacio euclidiano , y la distancia se define exactamente como Sqrt of Vector dot itselfen el espacio euclidiano.

La distancia al cuadrado es la mejor aproximación que obtendrá (en términos de rendimiento), no puedo ver nada superando 2 multiplicaciones, una suma y una tarea.

Entonces dices que no puedo optimizar la función de distancia, ¿qué debo hacer?

Su problema no es realizar la función de distancia. Su problema es realizar la función de distancia tantas veces. En otras palabras, necesita una optimización algorítmica en lugar de una matemática.

El punto es, en lugar de verificar la intersección del jugador con cada objeto en la escena, cada cuadro. Puede usar fácilmente la coherencia espacial para su ventaja, y solo verificar los objetos que están cerca del jugador (que tienen más probabilidades de golpear / intersectarse).

Esto se puede hacer fácilmente almacenando esa información espacial en una estructura de datos de partición espacial . Para un juego simple, sugeriría un Grid porque es básicamente fácil de implementar y se adapta muy bien a la escena dinámica.

Cada celda / cuadro contiene una lista de objetos que encierra el cuadro delimitador de la cuadrícula. Y es fácil rastrear la posición del jugador en esas celdas. Y para los cálculos de distancia, solo verifica la distancia del jugador con esos objetos dentro de las mismas celdas vecinas en lugar de todo en la escena.

Un enfoque más complicado es usar BSP o Octrees.

concepto3d
fuente
2
Creo que la última oración de la pregunta dice que OP está buscando otras alternativas (saben sobre el uso de la distancia al cuadrado).
MichaelHouse
@ Byte56 sí, tienes razón, no leí eso.
concept3d
Gracias por tu respuesta de todos modos. ¿Agregaría una oración que confirme que aunque ese método no nos da una distancia euclidiana, es muy preciso en las comparaciones? Creo que eso agregaría algo a alguien que viene aquí desde un motor de búsqueda.
Grimshaw
@Grimshaw Edité la respuesta para abordar el problema original.
concept3d
@ Byte56 gracias por señalar. Edité la respuesta.
concept3d
29

Si necesita algo que permanezca lineal a cualquier distancia (a diferencia distance^2) y, sin embargo, parezca vagamente circular (a diferencia de las distancias cuadradas de Chebyshev y Manhattan con forma de diamante), puede promediar las dos últimas técnicas para obtener una aproximación de distancia en forma octagonal:

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

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

Aquí hay una visualización (diagrama de contorno) de la función, gracias a Wolfram Alpha :

Dibujo de contorno

Y aquí hay una gráfica de su función de error en comparación con la distancia euclidiana (radianes, primer cuadrante solamente):

Trama de error

Como puede ver, el error varía de 0% en los ejes a aproximadamente + 12% en los lóbulos. Al modificar un poco los coeficientes podemos reducirlo a +/- 4%:

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

ingrese la descripción de la imagen aquí

Actualizar

Usando los coeficientes anteriores, el error máximo estará dentro de +/- 4%, pero el error promedio seguirá siendo + 1.3%. Optimizado para error promedio cero, puede usar:

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

lo que da errores entre -5% y + 3% y un error promedio de + 0.043%


Mientras buscaba en la web un nombre para este algoritmo, encontré esta aproximación octogonal similar :

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

Tenga en cuenta que esto es esencialmente equivalente (aunque los exponentes son diferentes, estos dan un error de -1.5% a 7.5%, pero se puede dar masajes a +/- 4%) porque max(dx, dy) + min(dx, dy) == dx + dy. Con este formulario, las llamadas miny maxse pueden factorizar a favor de:

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

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

¿Será esto más rápido que mi versión? Quién sabe ... depende del compilador y de cómo optimiza cada uno para la plataforma de destino. Supongo que sería bastante difícil ver alguna diferencia.

bcrist
fuente
3
¡Interesante, no he visto esto antes! ¿Tiene un nombre, o simplemente "promedio de Chebyshev y Manhattan"?
congusbongus
@congusbongus Probablemente tiene un nombre, pero no sé qué es. Si no, quizás algún día se llamará Crist Distance (ja ... probablemente no)
bcrist
1
Tenga en cuenta que las multiplicaciones de punto flotante no son muy eficientes. Es por eso que la otra aproximación usa 1007/1024 (que se implementará como multiplicación de enteros seguida de desplazamiento de bits).
MSalters
@MSalters Sí, las operaciones de punto flotante son a menudo más lentas que las operaciones de enteros, pero eso es irrelevante: 0.4 y 0.56 podrían convertirse fácilmente para usar operaciones de enteros. Además, en el hardware moderno x86, la mayoría de las operaciones de coma flotante (que no sean FDIV, FSQRTy otras funciones trascendentales) cuestan esencialmente lo mismo que sus versiones enteras: 1 o 2 ciclos por instrucción.
bcrist
1
Esto se parece mucho a Alpha max + Beta Min: en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algorithm
drake7707
21

A veces, esta pregunta puede surgir no por el costo de realizar cálculos de distancia, sino por la cantidad de veces que se realiza el cálculo.

En un gran mundo de juegos con muchos actores, no es escalable seguir controlando la distancia entre un actor y todos los demás. A medida que más jugadores, NPC y proyectiles ingresen al mundo, la cantidad de comparaciones que deben hacerse crecerá de forma cuadrática con O(N^2).

Una forma de reducir ese crecimiento es utilizar una buena estructura de datos para descartar rápidamente los actores no deseados de los cálculos.

Estamos buscando una manera de iterar eficientemente a todos los actores que podrían estar dentro del alcance, excluyendo a la mayoría de los actores que están definitivamente fuera de rango .

Si sus actores están distribuidos de manera bastante uniforme en el espacio mundial, entonces una cuadrícula de cubos debería ser una estructura adecuada (como sugiere la respuesta aceptada). Al mantener las referencias a los actores en una grilla gruesa, solo necesita verificar algunos de los cubos cercanos para cubrir a todos los actores que podrían estar dentro del alcance, ignorando el resto. Cuando un actor se mueve, es posible que tengas que moverlo de su antiguo cubo a uno nuevo.

Para los actores que se distribuyen de manera menos uniforme, un quadtree puede funcionar mejor para un mundo bidimensional, o un octree sería adecuado para un mundo tridimensional. Estas son estructuras de propósito más general que pueden dividir eficientemente grandes áreas de espacio vacío y pequeñas áreas que contienen muchos actores. Para los actores estáticos existe una partición de espacio binario (BSP), que es muy rápida de buscar pero demasiado costosa de actualizar en tiempo real. Los BSP separan el espacio usando planos para cortarlo repetidamente por la mitad, y se pueden aplicar a cualquier cantidad de dimensiones.

Por supuesto, existen gastos generales para mantener una estructura de este tipo, especialmente cuando se mueven entre particiones. Pero en un mundo grande con muchos actores pero con pequeños rangos de interés, los costos deberían ser mucho más bajos que los incurridos por comparación ingenua contra todos los objetos.

La consideración de cómo crece el gasto de un algoritmo a medida que recibe más datos es crucial para el diseño de software escalable. A veces, simplemente elegir la estructura de datos correcta es suficiente. Los costes se describen generalmente usando Big O notación .

(Me doy cuenta de que esta no es una respuesta directa a la pregunta, pero puede ser útil para algunos lectores. ¡Mis disculpas si he perdido el tiempo!)

joeytwiddle
fuente
77
Esta es la mejor respuesta. No hay nada que optimizar en la función de distancia; uno solo necesita usarlo con menos frecuencia.
sam hocevar
3
La respuesta aceptada también cubre la partición espacial, de lo contrario su respuesta es realmente óptima. Gracias.
Grimshaw
Mi tiempo lo pasé muy bien leyendo tu respuesta. Gracias Joey
Patrick M
1
Esta es la mejor respuesta y la única que se enfoca en el problema real en lugar de en el arenque del rendimiento de la función de distancia. La respuesta aceptada también puede cubrir la partición espacial, pero es como un aparte; Se centra en el cálculo de la distancia. El cálculo de la distancia no es el problema principal aquí; La optimización del cálculo de la distancia es una no solución de fuerza bruta que no escala.
Maximus Minimus
¿Podría explicar por qué el número de comparaciones sería exponencial? Pensé que sería cuadrático, comparando a cada actor entre sí durante cada período de tiempo.
Petr Pudlák
4

¿Qué tal la distancia de Chebyshev? Para los puntos p, q se define de la siguiente manera:

distancia

Entonces, para los puntos (2, 4) y (8, 5), la distancia de Chebyshev es 6, como | 2-8 | > | 4-5 |.

Además, sea E la distancia euclidiana y C la distancia de Chebyshev. Luego:

distancia2

El límite superior probablemente no sea muy útil ya que tendrías que calcular la raíz cuadrada, pero el límite inferior podría ser útil: siempre que la distancia de Chebyshev sea lo suficientemente grande como para estar fuera del rango, la distancia euclidiana también debe serlo, lo que te ahorrará de tener que calcularlo.

La compensación, por supuesto, es que si la distancia de Chebyshev está dentro del rango, tendrá que calcular la distancia euclidiana de todos modos, perdiendo el tiempo. ¡Solo hay una forma de averiguar si será una ganancia neta!

Tetrinidad
fuente
1
También podría usar la distancia de Manhattan como un límite superior.
congusbongus
1
Suficientemente cierto. Supongo que a partir de ahí es solo un salto, un salto y un salto al "promedio de Chebyshev y Manhattan" como lo sugiere bcrist.
Tetrinity
2

Una optimización local muy simple es simplemente verificar primero una sola dimensión.

Es decir :

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

Por lo tanto, solo verificar fabs (x2 - x1)como primer filtro puede dar una ganancia apreciable. Cuánto dependerá del tamaño del mundo versus los rangos relevantes.

Además, puede usar esto como una alternativa a la estructura de datos de partición espacial.

Si todos los objetos relevantes se ordenan en una lista en orden de coordenadas x, entonces los objetos cercanos deben estar cerca en la lista. Incluso si la lista se vuelve desordenada debido a que no se mantiene completamente a medida que los objetos se mueven, entonces, dados los límites de velocidad conocidos, aún puede reducir la sección de la lista para buscar objetos cercanos.

Keith
fuente
2

Se hicieron esfuerzos en el pasado para optimizar sqrt. Aunque ya no se aplica a las máquinas de hoy, aquí hay un ejemplo del código fuente de Quake, que usa el 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;
}

Una explicación detallada de lo que está sucediendo aquí en Wikipedia.

En resumen, son algunas iteraciones del método de Newton (un algoritmo numérico que mejora iterativamente una estimación), con el número mágico utilizado para proporcionar una estimación inicial razonable.

Como señala Travis, este tipo de optimización ya no es útil en arquitecturas modernas. E incluso si lo fuera, solo podría proporcionar una velocidad de velocidad constante a su cuello de botella, mientras que el rediseño algorítmico podría lograr mejores resultados.

joeytwiddle
fuente
2
Esto ya no es una optimización que valga la pena. Casi todas las arquitecturas de PC de nivel de consumidor que puede comprar hoy en día tienen instrucciones sqrt optimizadas por hardware que realizan la raíz cuadrada en un ciclo de reloj o menos. Si realmente necesita el sqrt más rápido posible, use la instrucción sqrt de coma flotante simd x86: en.wikipedia.org/wiki/… Para cosas como sombreadores en GPU, llamar a sqrt automáticamente dará como resultado dicha instrucción. En la CPU, supongo que muchos compiladores implementan sqrt a través de SIMD sqrt si está disponible.
TravisG
@TravisG Sí, vale la pena mencionarlo, así que he actualizado la respuesta. ¡Esta respuesta se proporcionó solo por diversión e interés histórico!
joeytwiddle