- Explica el flujo de optimización en física de juegos, resolviendo la detección de colisiones recurrente con una simulación de pelotas y pasando de revisar todos los pares a sweep-and-prune
- El enfoque simple llama a
intersects() para todos los pares candidatos de n objetos, realizando cerca de (n*(n-1))/2 comprobaciones, por lo que crece rápidamente como O(n²)
- La prueba de intersección AABB está compuesta por varias desigualdades y
&&; usando la evaluación de cortocircuito y la transitividad de las desigualdades, se pueden descartar temprano candidatos sin posibilidad de colisión
- Tras ordenar los objetos por el borde izquierdo, es decir, el minimum x, cuando
ball2.left > ball1.right se hace break en el bucle interno para excluir de una vez los candidatos siguientes
- Al costo de ordenamiento O(n log n) se le suma el costo del bucle según la cantidad
m de solapamientos en el eje x, quedando en promedio cerca de O(n log n + m), y se reducen mucho las llamadas innecesarias a intersects()
Punto de partida de la detección de colisiones en juegos
- La detección de colisiones es un prerrequisito para muchas acciones en la programación de videojuegos
- Evita que los personajes se atraviesen entre sí
- Hace que un Goomba cambie de dirección cuando choca con otro objeto
- En agar.io, una célula grande se come a una célula pequeña al tocarla
- Maneja la física general del juego
- El ejemplo usa una simulación de pelotas de cuerpo rígido para comparar varios enfoques de detección de colisiones
- El alcance va desde el método más simple hasta sweep-and-prune, y excluye la partición espacial o la subdivisión con árboles espaciales
Enfoque simple que revisa todos los pares
- El método más directo consiste en considerar todos los pares de objetos como candidatos
- El bucle externo recorre cada pelota
- El bucle interno comienza en
i + 1 para evitar pares duplicados como A-B y B-A
- Para cada par candidato llama a
intersects(ball1, ball2) y, si es verdadero, ejecuta bounce(ball1, ball2)
- Esta comprobación se repite en cada paso de tiempo, por lo que las pelotas rebotan cuando llegan a colisionar
- Cuando hay pocos objetos es suficiente, pero a medida que aumenta la cantidad, el volumen de comprobaciones se convierte rápidamente en un cuello de botella de rendimiento
Los límites que impone O(n²)
- El algoritmo simple se ejecuta en tiempo O(n²) según Big O
- Para
n pelotas, los pares que hay que revisar son aproximadamente (n*(n-1))/2, es decir, 0.5n² - 0.5n
- Si
n = 5, son 10 pares
- Si
n = 10, son 45 pares
- Si
n = 15, son 105 pares
- Si
n = 20, son 190 pares
- En el peor caso, cuando todos los objetos se solapan al mismo tiempo, es difícil que cualquier algoritmo de detección de colisiones evite procesar O(n²) colisiones
- En comparaciones reales, los casos promedio y mejores son más prácticos que el peor caso
- El método simple siempre se mueve en Θ(n²) sin importar la cantidad real de colisiones, así que hay mucho margen de mejora
Trabajo repetido dentro de intersects()
- El punto de partida de la optimización es la función
intersects(), que se llama para cada par candidato
- Una prueba de intersección AABB típica está compuesta por varias comprobaciones de desigualdad que comparan los límites en cada dirección
function intersects(object1, object2) {
// compare objects' bounds to see if they overlap
return object1.left < object2.right
&& object1.right > object2.left
&& object1.top < object2.bottom
&& object1.bottom > object2.top;
}
- Esta prueba se divide en cuatro condiciones
object1.left < object2.rightobject1.right > object2.leftobject1.top < object2.bottomobject1.bottom > object2.top
- Debido a la evaluación de cortocircuito de
&&, si una sola condición es falsa, toda la prueba de intersección se vuelve falsa de inmediato
- Si generalizamos el caso en el que “al menos una condición es falsa” a través de varias pruebas, podemos reducir las llamadas a
intersects() en sí
- Es una idea en la misma línea que el teorema del eje separador: si las proyecciones no se solapan en un eje, dos objetos no colisionan
Descartar candidatos con la transitividad de las desigualdades
- Incluso mirando solo la condición
object1.right > object2.left, aparece una oportunidad de optimización
- Cuando tres objetos A, B y C están horizontalmente en el orden A-B-C, todas las siguientes pruebas pueden ser falsas
A.right > B.left // returns false
B.right > C.left // returns false
A.right > C.left // returns false
- Si
A > B es falso y B > C es falso, por la transitividad de las desigualdades sabemos que A > C también es falso
- Por lo tanto, se puede determinar que dos objetos no colisionan sin llamar a
intersects(A, C)
- Esta omisión solo se aplica cuando los objetos están en cierto orden, pero como las etiquetas de los objetos son arbitrarias, basta con llamar A al objeto de la izquierda, B al del medio y C al de la derecha
- Colocar los objetos en este orden lógico es, precisamente, ordenar
Ordenamiento por valor mínimo del eje x
- Una lista ordenada permite aplicar la transitividad de las desigualdades a muchos candidatos a la vez
- Los algoritmos rápidos de ordenamiento comunes son O(n log n), por debajo de O(n²)
- Como los objetos no son puntos sino que ocupan intervalos en el eje x, para ordenar por posición x se usa el borde izquierdo, es decir, el minimum x
- En el código O(n²) simple se necesitan dos cambios
- Antes de los bucles, ordenar las pelotas por la coordenada x del borde izquierdo con
sortByLeft(balls)
- En el bucle interno, hacer
break si ball2.left > ball1.right
// sort by min x
sortByLeft(balls);
// for each ball
for (let i = 0; i < balls.length; i++) {
const ball1 = balls[i];
// check each of the other balls
for (let j = i + 1; j < balls.length; j++) {
const ball2 = balls[j];
// stop when too far away
if (ball2.left > ball1.right) break;
// check for collision
if (intersects(ball1, ball2)) {
bounce(ball1, ball2);
}
}
}
- La función de ordenamiento ordena el arreglo tomando como criterio la diferencia entre los bordes izquierdos
function sortByLeft(balls) {
balls.sort((a,b) => a.left - b.left);
}
Por qué break es seguro
- Si la lista está ordenada, para cualquier entero positivo
c se cumple la siguiente relación
balls[j + c].left >= balls[j].left
- Si el candidato actual satisface la siguiente condición, el par actual no se solapa en el eje x
balls[j].left > ball1.right
- Al combinar las dos desigualdades, queda esta relación
balls[j + c].left >= balls[j].left > ball1.right
- Por transitividad,
balls[j + c].left > ball1.right también es verdadero, así que todos los candidatos posteriores tampoco se solapan con el ball1 actual en el eje x
- En el momento en que el
ball2 actual ya no se solapa con ball1, se puede interrumpir el resto del bucle interno sin revisar los candidatos restantes
- Esta optimización limita las llamadas reales a
intersects() a los pares que se solapan en el eje x
Complejidad temporal mejorada
- El costo de ordenamiento agrega un término O(n log n) si se usa un ordenamiento rápido como mergesort o quicksort
- El doble bucle con interrupción temprana puede verse, en promedio, como O(n + m)
m es la cantidad total de solapamientos en el eje x- En el mejor caso, si no hay solapamientos, casi no hay procesamiento innecesario y se acerca a O(n)
- En el peor caso, aún puede degradarse hasta O(n²)
- El caso promedio asume una situación en la que los objetos están distribuidos de forma bastante uniforme y solo ocurren unas pocas colisiones por objeto
- La complejidad total, combinando ordenamiento y bucle, es O(n log n + m)
- Mejora frente al método simple por dos razones
n log n es menor que n²- Depende en parte de la cantidad de solapamientos
m, así que no procesa más de lo necesario
Carga de implementación y próximos pasos
- Este enfoque basado en ordenamiento es un punto de equilibrio: requiere pocos cambios de código y mejora mucho el rendimiento en tiempo de ejecución
- En la demo comparativa, la revisión de pares basada en ordenamiento reduce de forma notable la cantidad de pruebas
intersects() por frame frente a revisar todos los pares globalmente
- El costo de ordenamiento no se muestra en la visualización comparativa, pero se parte de la premisa de que las pruebas de intersección son lo bastante costosas
- Los enfoques más avanzados y el código final continúan en Part 2
1 comentarios
Comentarios de Hacker News
Lo interesante de este enfoque es que el autor propone usar algoritmos de ordenamiento “rápidos” como merge sort/quick sort para obtener el mejor rendimiento
Pero en la práctica, un algoritmo de ordenamiento “peor” como insertion sort puede ser más rápido
Los objetos de un sistema de detección de colisiones normalmente solo se mueven un poco entre cuadros, así que se puede conservar la lista casi ordenada del cuadro anterior
En una lista así, insertion sort se acerca a O(n), mientras que quick sort puede acercarse a O(n^2)
Explica algo como: “La etapa de ordenamiento es el cuello de botella en el análisis, pero la mayor parte del tiempo ordenar no hace nada. La lista casi siempre ya viene ordenada del cuadro anterior. Incluso cuando se desordena, normalmente basta con unos pocos intercambios para volver a ordenarla. Aquí hay un ejemplo de insertion sort en acción”
Por ejemplo, se puede lograr aumentando el radio de las esferas en epsilon
Mientras la esfera no se haya movido epsilon, no hace falta recalcular el índice
Cuando sí haga falta recalcularlo, para evitar picos de latencia se puede ordenar 10% por cuadro y así construir un índice rezagado
Después de 10 cuadros se obtiene un índice válido, siempre que esté dentro de epsilon respecto a la posición de hace 10 cuadros
Si eliges el pivote al azar, será O(n log n), y si la lista ya está casi ordenada también podrías elegir el elemento del medio como pivote
Aun así, incluso con el pivote óptimo quick sort sigue siendo O(n log n) en el mejor caso
Hay variantes simples de merge sort que funcionan en O(n log k), donde k es la cantidad de runs ascendentes/descendentes en los datos
El
sortpredeterminado de la biblioteca estándar de Haskell usa un algoritmo de ese tipo, y probablemente Python tambiénLa estructura del artículo estuvo muy bien
He hecho desarrollo de juegos de una forma u otra desde finales de los 90, y aunque hoy en día la mayor parte de esto ya está abstraída dentro del motor, este tipo de contenido sigue siendo esencial para entender cómo funcionan las simulaciones de sistemas complejos
Gracias al autor por hacer un texto tan accesible
Sobre detección continua de colisiones, siempre me ha gustado este documento: https://github.com/bepu/bepuphysics2/blob/master/Documentati...
La biblioteca en sí también es excelente en rendimiento
Eso sí, integrarla es un poco complicado porque tiene mucha optimización encima
Me pregunto si es correcto decir “este algoritmo ingenuo corre en tiempo O(n2) en términos de Big O”
El bucle externo i corre n - 1 veces, y como el bucle interno j empieza en i + 1, parecería que cada vez corre menos de n - 1 veces
No soy especialista, así que me da curiosidad si para n grande se considera aproximadamente O(n2), o si en realidad es menor de lo que parece
Para el elemento i-ésimo, haces (n - i - 1) comparaciones y, si indexas desde 0, el total de comparaciones es (n - 1) * n / 2
Ver https://en.wikipedia.org/wiki/Triangular_number
Al final, en el análisis Big O no hay diferencia
Big O describe el comportamiento cuando n tiende a infinito, y ahí el término cuadrático es el que domina
j = i + 1sirve para no revisar todos los pares de objetos dos vecesTambién evita comparar un objeto consigo mismo
Como revisa cada par una sola vez, el algoritmo es O(n^2)
En general, si puedes expresar analíticamente el número de operaciones como una función del tamaño de entrada, Big O se queda solo con el término más grande y descarta todos los coeficientes
No necesariamente describe el rendimiento real del algoritmo
20n2^+5ny2n^2 + 9001nson ambos O(n^2)En la notación Big O se ignoran todos los coeficientes y los términos que crecen más lento, así que se reduce a complejidad cuadrática
El uso de ilustraciones estuvo muy bien, y parecía estar bien medido
A veces los artículos con ilustraciones interactivas se sienten como una excusa para meter un montón de demos bonitas y, como una charla TED, terminan teniendo más adorno que sustancia
Pero en este artículo las ilustraciones no se comieron el contenido
Parte 2: https://leanrada.com/notes/sweep-and-prune-2/
También vale la pena ver otros buenos artículos: https://leanrada.com/
Hace mucho hice algo parecido, pero en vez de ordenar mantenía una lista de índices por cada dirección y hacía que los objetos se ordenaran solos
Por ejemplo, había 4 listas como
objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdgeCuando un objeto se movía horizontalmente, actualizaba su índice en los arreglos leftEdge y rightEdge
Como incluso al moverse normalmente basta con intercambiar 1 o 2 índices
Mientras más elementos dinámicos haya, más sentido parece tener reconstruir el grafo
No conocía este enfoque, pero ¿no es parecido a usar algo como un quadtree para reducir la cantidad de colisionadores potenciales?
Aunque en renderizado offline se suele ver más seguido algo como un k-d tree que en renderizado en tiempo real
Me llamó la atención la parte que dice: “No voy a cubrir otros enfoques como la partición espacial o la subdivisión con árboles espaciales”
¿Alguien sabe si el algoritmo del artículo suele ser más rápido que la partición espacial/subdivisión con árboles espaciales?
Hace mucho usé un enfoque de tipo árbol espacial y, a simple vista, me parecía bastante bueno, pero era en los 80 antes de Internet, así que nunca investigué ni comparé qué algoritmos usaba otra gente
Gestionar una sola lista de entidades, o una cuadrícula de celdas de 256x256 que a su vez contiene listas de entidades, es mucho más fácil de escribir, depurar y optimizar que una estructura de partición compleja donde hay que mantener todos los invariantes del árbol cada vez que se mueve un objeto
En la época de DOOM o Quake, el rendimiento de estos sistemas base importaba mucho más que ahora, así que para los autores de motores tenía más sentido construir sistemas de partición muy complejos
Los CPU modernos son muy buenos recorriendo arreglos ordenados, y por el pipelining seguir listas enlazadas o árboles resulta relativamente menos ventajoso que antes
El tiempo de CPU tiende a gastarse más en cosas como IA o renderizado que en gestionar listas de entidades