Ordenamiento, barrido y poda: algoritmos de detección de colisiones (2023)

 (leanrada.com)
3 puntos por GN⁺ 2024-08-15 | 1 comentarios | Compartir por WhatsApp

Algoritmos de detección de colisiones

Detección de colisiones

  • En la programación de videojuegos, la detección de colisiones es un problema muy común
  • Es esencial para evitar que los personajes se atraviesen entre sí o para implementar un motor de física

Enfoque simple 🐥

  • Un método consiste en revisar cada par de objetos para verificar si colisionan
  • Ejemplo de código: 
    for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}
  • Este método tiene una complejidad temporal de O(n^2)

Problemas de rendimiento

  • A medida que aumenta la cantidad de objetos, aparecen problemas de rendimiento
  • Por ejemplo, cuando n = 20, hay que revisar 190 pares

Mejorando la solución

  • Es importante reducir el trabajo innecesario
  • Optimización de la función intersects(): 
    function intersects(object1, object2) {
  return object1.left < object2.right &&
         object1.right > object2.left &&
         object1.top < object2.bottom &&
         object1.bottom > object2.top;
}

Optimización mediante ordenamiento

  • Si se ordenan los objetos según la coordenada x, se pueden reducir las revisiones innecesarias
  • Ejemplo de código: 
    sortByLeft(balls);
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (ball2.left > ball1.right) break;
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

Análisis de rendimiento

  • Ordenamiento: O(n log n)
  • Bucle interno: en promedio O(n + m) (m es la cantidad total de superposiciones en el eje x)
  • Complejidad temporal final: O(n log n + m)

Comparación visual

  • Comparación entre revisar todos los pares globalmente y revisar pares ordenados
  • La revisión de pares ordenados realiza muchas menos comprobaciones

Resumen de GN⁺

  • Este artículo trata sobre cómo optimizar algoritmos de detección de colisiones en desarrollo de juegos
  • Comienza con un algoritmo simple de O(n^2) y mejora mucho el rendimiento mediante ordenamiento
  • Es información muy útil para desarrolladores de juegos o ingenieros de software
  • Otros proyectos con funciones similares incluyen Box2D y Bullet Physics

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-08-15
Comentarios en Hacker News

  • El autor sugiere usar algoritmos de ordenamiento "rápidos" como mergesort o quicksort para lograr un rendimiento óptimo

    • Sin embargo, en la práctica, algoritmos de ordenamiento "peores" como insertion sort pueden mostrar un mejor rendimiento
    • Los objetos en un sistema de detección de colisiones se mueven en pasos relativamente pequeños entre cuadros, por lo que se puede mantener la lista casi ordenada del cuadro anterior
    • Al ordenar estas listas casi ordenadas, insertion sort es cercano a O(n) y Quicksort se acerca a O(n^2)

  • Hicieron un trabajo similar en el pasado, pero en vez de ordenar mantuvieron una lista de índices para cada dirección

    • Por ejemplo, había 4 listas como objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge
    • Si un objeto se movía horizontalmente, actualizaban su índice en los arreglos leftEdge y rightEdge
    • Como mucho había que intercambiar 1 o 2 índices mientras se movía

  • Este artículo está realmente muy bien organizado

    • Llevo haciendo desarrollo de juegos desde finales de los 90, pero la mayor parte del trabajo ha quedado abstraída por el engine
    • Es esencial para entender simulaciones de sistemas complejos
    • Gracias al autor por escribir un artículo tan accesible

  • Siempre he disfrutado leer documentación sobre detección continua de colisiones

  • Me gustó el uso de ilustraciones

    • A veces este tipo de artículos se sienten como una excusa para reunir demos vistosas, pero en este caso las ilustraciones no se roban el protagonismo

  • Parte 2: https://leanrada.com/notes/sweep-and-prune-2/

  • Cuestionaron la afirmación de que "este algoritmo simple se ejecuta en tiempo O(n^2) en términos de Big O"

    • El bucle externo (i) cuenta hasta n - 1, y el bucle interno (j) empieza en i + 1 y cuenta cada vez menos elementos
    • No soy graduado de CS, pero me preguntaba si para valores grandes de n esto es aproximadamente igual a O(n^2) o si es menor

  • Se preguntaban si este método es similar a usar un quadtree para reducir los posibles colisionadores

  • Se preguntaban si alguna vez se ha propuesto un método de programación lineal

  • Este sitio web me distrajo, en el buen sentido

    • Es divertido e inspirador