algorithm - programar - trigger unity 2d
¿Cómo funciona la detección de colisión/objeto 3D? (6)
Correcto. Normalmente no hay un detector de eventos para cada objeto. A menudo hay una estructura de árbol no binaria en la memoria que imita tu mapa de juegos. Imagine un mapa de metro / subterráneo. Esta estrucutre de memoria es una colección de cosas en el juego. Eres el jugador, los monstruos y los objetos que puedes recoger o los objetos que pueden explotar y hacerte daño. Entonces, a medida que el jugador se mueve por el juego, el puntero del objeto del jugador se mueve en la estructura de la memoria del juego / mapa.
ver ¿Cómo debo hacer que mis entidades de juego conozcan las cosas que les rodean?
Siempre me he preguntado esto. En un juego como GTA donde hay decenas de miles de objetos, ¿cómo sabe el juego tan pronto como estés en un paquete de salud?
¿No puede haber un detector de eventos para cada objeto? Iterar no es bueno tampoco? Me pregunto cómo se hace realmente.
Me gustaría recomendar el sólido libro de Christer Ericson sobre la detección de colisiones en tiempo real. Presenta los conceptos básicos de la detección de colisiones y proporciona referencias sobre los esfuerzos de investigación contemporáneos.
Detección de colisiones en tiempo real (The Morgan Kaufmann Series en tecnología interactiva 3-D)
No hay una respuesta a esto, pero los grandes mundos a menudo se dividen usando algo parecido a un quadtree o kd-tree que trae tiempos de búsqueda para encontrar vecinos más cercanos debajo del tiempo lineal (potencia fraccional, o en el peor de los casos O (N ^ 2/3)) para un juego en 3D). Estos métodos a menudo se denominan BSP para particionamiento de espacio binario.
Con respecto a la detección de colisiones, cada objeto generalmente también tiene una malla de volumen delimitador (conjunto de polígonos que forman un casco convexo) asociado a ella. Estas mallas altamente simplificadas (a veces solo un cubo) no se dibujan sino que se usan en la detección de colisiones. El método más rudimentario es crear un plano que sea perpendicular a la línea que conecta los puntos medios de cada objeto con el plano que se cruza con la línea en el punto medio de la línea. Si el volumen delimitador de un objeto tiene puntos en ambos lados de este plano, se trata de una colisión (solo necesita probar uno de los dos volúmenes delimitadores contra el plano). Otro método es el algoritmo de distancia GJK mejorado. Si quieres un tutorial para bucear, mira la lección # 30 de OpenGL de NeHe Productions .
Incidentalmente, los volúmenes delimitadores también se pueden usar para otras optimizaciones, como las llamadas consultas de oclusión . Este es un proceso para determinar qué objetos están detrás de otros objetos (oclusores) y, por lo tanto, no es necesario procesarlos ni procesarlos. Los volúmenes delimitadores también se pueden usar para descarte de troncos, que es el proceso de determinar qué objetos están fuera del volumen de visualización en perspectiva (demasiado cerca, demasiado lejos o más allá del ángulo del campo de visión) y, por lo tanto, no es necesario representarlos.
Como señaló Kylotan, usar un volumen delimitador puede generar falsos positivos cuando se detecta la oclusión y simplemente no funciona en absoluto para algunos tipos de objetos como los toroides (p. Ej., Mirar a través del orificio de una rosquilla). Tener objetos como estos ocluir correctamente es un hilo totalmente diferente en el sacrificio del portal .
Una técnica común en los motores de física de juegos es el método de barrido y poda. Esto se explica en las notas SIGGRAPH de David Baraff (ver el capítulo Movimiento con restricciones). Havok definitivamente usa esto, creo que es una opción en Bullet, pero no estoy seguro acerca de PhysX.
La idea es que se puedan ver las superposiciones de AABB (recuadros delimitadores alineados con el eje) en cada eje; si la proyección de AABB de dos objetos se superpone en los tres ejes, entonces los AABB se deben superponer. Puede verificar cada eje con relativa rapidez clasificando los puntos de inicio y final de los AABB; hay mucha coherencia temporal entre fotogramas, ya que normalmente la mayoría de los objetos no se mueven muy rápido, por lo que la clasificación no cambia mucho.
Una vez que el barrido y la poda detectan una superposición entre las AABB, puede hacer una comprobación más detallada de los objetos, por ejemplo, esfera contra caja. Si la verificación detallada revela una colisión, puede resolver la colisión aplicando fuerzas y / o activando un evento de juego o reproduciendo un efecto de sonido.
Los Quadtrees y los Octrees , otro quadtree , son formas populares, usando particiones espaciales, para lograr esto. El último ejemplo muestra una reducción del 97% en el procesamiento sobre una búsqueda de colisiones de fuerza bruta par por par.
Se pueden usar muchas optimizaciones. En primer lugar, cualquier objeto (por ejemplo, con el índice i) está delimitado por cubo, con las coordenadas CXi , CYi y tamaño Si En segundo lugar, la detección de colisiones funciona con estimaciones:
a) Encuentre todos los pares cubos i, j con condición: Abs(CXi-CXj)<(Si+Sj) AND Abs(CYi-CYj)<(Si+Sj)
b) Ahora trabajamos solo con pares conseguidos en a). Calculamos las distancias entre ellos de forma más precisa, algo así como Sqrt(Sqr(CXi-CXj)+Sqr(CYi-CYj)) , objetos ahora representados como conjuntos de pocos números simples (cubos, esferas, conos) y usando fórmulas de geometría para verificar estas figuras intersecciones.
c) Los objetos de b) con intersecciones detectadas se procesan como colisiones con el cálculo de la física, etc.