Estoy haciendo un juego basado en una cuadrícula 2D, con algunas celdas pasables y otras no. Los objetos dinámicos pueden moverse continuamente, independientemente de la cuadrícula, pero deben colisionar con celdas intransitables.
Escribí un algoritmo para rastrear un rayo contra la cuadrícula, que me da todas las celdas que se cruzan. Sin embargo, el objeto real no tiene un tamaño de punto; Actualmente los estoy representando como círculos. Pero no puedo encontrar un algoritmo efectivo para trazar un círculo en movimiento. Aquí hay una foto de lo que necesito:
Los números muestran en qué orden el círculo choca con las celdas de la cuadrícula. ¿Alguien sabe el algoritmo para encontrar estas colisiones? Preferiblemente en C #.
Actualización El círculo puede ser más grande que una sola celda de cuadrícula.
fuente
Respuestas:
Creo que tu dibujo es un poco engañoso porque eliges dibujar trazos desde el punto de la tangente del círculo hasta tu dirección de movimiento. Puedo ver que las colisiones con los bordes de la cuadrícula ocurren cuando los puntos SUPERIOR e IZQUIERDO de su círculo tocan un borde.
Deje que C sea su centro y r el radio para que P ' = C + ( r , 0) y P " = C + (0, r).
Si D es tu vector de dirección (el versor) tienes dos líneas:
R '= D · t + P' ,
R "= D · t + P"
Simplemente tiene que encontrar la intersección de esas líneas con las líneas de ecuación:
y = i e y = i que son los bordes de su cuadrícula!
La solución es fácil porque simplemente tiene que considerar la componente x o y de R 'y R ". Encontrará el valor de t s para cada sección y los puntos para esas t , simplemente ordene esos puntos por t y usted están hechos.
Creo que puedes decir fácilmente qué celda es golpeada si conoces el punto de intersección.
Esto funciona si r <1 (el ancho y la altura de la celda).
Funciona también para los otros casos simplemente haciendo alguna consideración sobre P ' y P " . Elegimos ARRIBA e IZQUIERDA debido a la dirección, ABAJO y DERECHA deben considerarse para la dirección opuesta, entiendes por qué.
Ahora mira esta imagen:
El círculo es más grande que una sola celda y suponemos que va en la misma dirección que su dibujo. P1 es el primer punto que tocará, P2 es el segundo, P3 es inútil porque está en la mitad inferior. Lo que debe hacer es emitir rayos desde P1 y P2 como vimos antes y hacer lo mismo para las líneas verticales.
En general, tendrás otros puntos de partida junto con los SUPERIORES y los IZQUIERDOS desde donde disparas tus rayos, cuanto más grande sea tu círculo, más rayos lanzarás.
Para ser honesto, puedes evitar disparar todos esos rayos haciendo alguna consideración geométrica, pero eso puede hacer que las cosas sean más difíciles de entender.
fuente
Si desea usar su algoritmo de colisión de rayos, puede elegir ocho puntos en cada círculo (en incrementos de 45 grados, alineados con su cuadrícula cuadrada), y usar la colisión de rayos entre los puntos correspondientes (es decir, desde la parte superior de uno círculo a la parte superior de la otra). La unión de todas estas colisiones de rayos es el conjunto completo de células intersectadas.
Probablemente podría mejorar esto un poco, por ejemplo, utilizando el segmento de línea desde el centro de un círculo hasta el centro del otro, pero extendido a cada lado por el radio del círculo, así como los segmentos de línea paralelos en cualquier lado en las extremidades de los círculos.
fuente
No digo que sea una analogía perfecta, pero podrías pensar en el algoritmo de línea de Bresenham . Una modificación de este algoritmo o una de sus extensiones podría ser útil, especialmente si lo combina con algunas de las otras publicaciones y comentarios. Por lo general, este algoritmo no se preocupa por ordenar, pero creo que podría agregarlo de manera bastante trivial.
fuente