Siguiendo con mi pregunta anterior sobre cómo encontrar la pendiente de un terreno de mapa de bits 2D, ahora necesito saber la mejor manera de encontrar el punto en el terreno 2D que golpeó el misil. Obviamente, puedo ver si algún píxel debajo del misil se cruza con el terreno, pero digo que se ha movido bastante profundo en el terreno.
¿Cuál es la mejor manera de retroceder para encontrar dónde colisionó inicialmente? Podría retroceder X píxeles a la vez hacia la posición anterior del misil, pero ¿cuál sería un buen valor de X? ¿Y hay una manera más inteligente? ¿Tal vez moverse la mitad de la distancia, luego un cuarto, etc.?
Respuestas:
Para las pruebas de colisión, no debe hacer una prueba estática tick por tick, debe hacer pruebas de rastreo / barrido.
Aquí hay una lista exhaustiva de varias fórmulas para diferentes tipos de primitivas: http://www.realtimerendering.com/intersections.html
Eso es, por supuesto, suponiendo que puede dividir su terreno en algún tipo de conjunto de primitivas con las que puede probar (es decir, segmentos de línea). Hay varias formas de hacerlo.
Vea también esta pregunta (solo ligeramente relacionada): ¿Cuál es un buen algoritmo para detectar la colisión entre esferas en movimiento?
fuente
La búsqueda binaria no ayudará si tiene pequeños fragmentos de paisajes y proyectiles que se mueven rápidamente; puede que los pierda.
Creo que su mejor opción es barrer una línea a través del frente del proyectil a lo largo del camino que toma, píxel a la vez. Puede hacer una verificación de límites primero en todo el volumen para evitar hacerlo en cada paso.
fuente
Dado que es poco probable que el misil mueva una gran cantidad de píxeles en cada cuadro (no sería uniforme en la pantalla), no veo ninguna razón para no solo verificar cada píxel en el camino. El algoritmo de línea de Bressenham es tu amigo, y también te aseguras de tener una copia local de tu mapa de bits, ya que generalmente no quieres acceder a la memoria de video por cada píxel. Esto supone que su terreno de mapa de bits es completamente aleatorio (según el terreno de gusanos destruibles). Si su mundo está basado en mosaicos, podría omitir cada mosaico que sepa que está vacío para comenzar, pero como se mencionó anteriormente, a menos que tenga una gran cantidad de misiles para verificar, no podría pensar en una plataforma que necesitaría que sea demasiado lenta solo para probar píxel por píxel, y no necesitará tener su mundo definido en primitivas (un clon de gusanos haría eso complicado)
fuente
Además de las otras respuestas, hay algunas cosas que puede hacer para acelerar esto si desea hacer un poco de contabilidad con respecto a "recopilar" un montón de píxeles en bloques de "estado similar conocido". Por ejemplo, puede almacenar la altura de la pieza de terreno más alto, por lo que puede dar por sentado que el misil no golpeará nada mientras esté por encima de eso. También puede almacenar la altura del espacio "aéreo" más bajo, de modo que sabrá que si el misil llega a esa altitud, debe haber golpeado algo (aunque esto podría utilizarse mejor como un control de cordura). Yendo más allá de esto, podría almacenar rectángulos que representan áreas que son todo terreno y otros rectángulos que son todos aire, pero eso podría ser más trabajo que valor.
En última instancia, el mejor método probablemente será "almacenar la altura de cada columna de terreno" y luego simplemente calcular la altura del misil en cada paso de su camino. No puedo hablar con juegos más modernos, pero creo que cuando hiciste una "cueva" en Scorched Earth, el terreno sobre esa cueva cayó directamente, sin dejar salientes. Si desea sobresalir, el trabajo será un poco mayor, pero será una extensión de esta idea básica. (Sugerencia: ¡haga que la idea básica funcione primero!)
Dado que su terreno es presumiblemente completamente arbitrario, no hay atajos. Incluso si forzaste tu terreno a ser una spline o algo así, eso se alterará una vez que comiences a destruirlo y las pruebas de intersección de la línea-spline sean iterativas y no perfectas o exhaustivas e inusualmente lentas para tu tipo de problema.
fuente