algorithm - software - Cálculo de las fichas que se encienden en un juego basado en fichas("trazado de rayos")
ray tracing nvidia (12)
Estoy escribiendo un pequeño juego basado en mosaicos, para el cual me gustaría apoyar las fuentes de luz. Pero mi algoritmo-fu es demasiado débil, por lo tanto, vengo a ti en busca de ayuda.
La situación es así: hay un mapa basado en mosaico (que se mantiene como una matriz 2D), que contiene una sola fuente de luz y varios elementos alrededor. Quiero calcular qué fichas están iluminadas por la fuente de luz y cuáles están en la sombra.
Una ayuda visual de lo que se vería, aproximadamente. La L es la fuente de luz, las X son elementos que bloquean la luz, los 0 son azulejos iluminados y las -s son mosaicos en la sombra.
0 0 0 0 0 0 - - 0
0 0 0 0 0 0 - 0 0
0 0 0 0 0 X 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 L 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 X X X X 0 0
0 0 0 - - - - - 0
0 0 - - - - - - -
Un sistema fraccionario sería aún mejor, por supuesto, donde una losa puede estar a media sombra debido a que está parcialmente oscurecida. El algoritmo no debería ser perfecto, simplemente no obviamente incorrecto y razonablemente rápido.
(Por supuesto, habría múltiples fuentes de luz, pero eso es solo un bucle).
¿Ningún arrendatario?
Esto es sólo por diversión:
Puede replicar el enfoque Doom 3 en 2D si primero hace un paso para convertir sus mosaicos en líneas. Por ejemplo,
- - - - -
- X X X -
- X X - -
- X - - -
- - - - L
... se reduciría en tres líneas que conectan las esquinas del objeto sólido en un triángulo.
Luego, haga lo que hace el motor Doom 3: desde la perspectiva de la fuente de luz, considere cada "pared" que enfrenta a la luz. (En esta escena, solo se consideraría la línea diagonal). Para cada línea, proyecte en un trapezoide cuyo borde frontal es la línea original, cuyos lados se encuentran en líneas de la fuente de luz a través de cada punto final, y cuya parte posterior es muy lejos, más allá de toda la escena. Entonces, es un trapecio que "apunta a" la luz. Contiene todo el espacio sobre el que la pared proyecta su sombra. Rellena todas las fichas de este trapecio con oscuridad.
Proceda a través de todas esas líneas y terminará con una "galería de símbolos" que incluye todas las fichas visibles desde la fuente de luz. Llena estas fichas con el color claro. Es posible que desee iluminar el azulejo un poco menos a medida que se aleja de la fuente ("atenuación") o hacer otras cosas de lujo.
Repita para cada fuente de luz en su escena.
La solución de TK es la que generalmente usarías para este tipo de cosas.
Para el escenario de iluminación parcial, puede tenerlo de modo que si un mosaico resulta estar en la sombra, ese mosaico se divide en 4 mosaicos y cada uno de ellos se prueba. ¿Entonces podrías dividir todo lo que quisieras?
Editar:
También puedes optimizarlo un poco al no probar ninguno de los mosaicos adyacentes a una luz; esto sería más importante cuando tienes varias fuentes de luz, supongo ...
Los algoritmos presentados aquí me parecen hacer más cálculos de los que creo que son necesarios. No lo he probado, pero creo que funcionaría:
Inicialmente, marque todos los píxeles como iluminados.
Para cada píxel en el borde del mapa: como sugirió Arachnid, use Bresenham para trazar una línea desde el píxel a la luz. Si esa línea choca con una obstrucción, marque todos los píxeles desde el borde hasta más allá de la obstrucción como en sombra.
Para verificar si una ficha está en la sombra, debe dibujar una línea recta de regreso a la fuente de luz. Si la línea se cruza con otra casilla que está ocupada, entonces la casilla que estaba probando está en sombra. Los algoritmos de Raytracing hacen esto para cada objeto (en su mosaico de caso) en la vista.
El artículo de Raytracing en Wikipedia tiene pseudocódigo.
Puede entrar en todo tipo de complejidades con el cálculo de la oclusión, etc., o puede usar el método de fuerza bruta simple: para cada celda, use un algoritmo de trazado de línea como el algoritmo de línea Bresenham para examinar cada celda entre la corriente y la luz fuente. Si hay celdas llenas o (si solo tienes una fuente de luz) celdas que ya han sido probadas y se encuentran en la sombra, tu celda está a oscuras. Si encuentra una celda que se sabe que está encendida, su celda también estará encendida. Una optimización fácil para esto es establecer el estado de las celdas que encuentres a lo largo de la línea para lo que sea el resultado final.
Esto es más o menos lo que utilicé en mi entrada ganadora del IOCCC 2004 . Obviamente, eso no es un buen ejemplo de código. ;)
Editar: Como señala Loren, con estas optimizaciones, solo tiene que elegir los píxeles a lo largo del borde del mapa para seguir.
Rápido y sucio:
(Dependiendo de qué tan grande sea la matriz)
- Pasa por cada azulejo
- dibuja una línea a la luz
- Si cualquier pary de la línea golpea una X, entonces está en la sombra
- (Opcional): calcule la cantidad de X por la que pasa la línea y haga cálculos extravagantes para determinar la proporción de la tesela en la sombra. NB: Esto se puede hacer al suavizar la línea entre el mosaico y la Luz (por lo tanto, mirando otras fichas a lo largo de la ruta de regreso a la fuente de luz) durante el procedimiento de umbralización, estos aparecerán como pequeños anomolios. Dependiendo de la lógica utilizada, podría determinar la cantidad (si es que lo hace) de la tesela en sombra.
También podría mantener una pista de los píxeles que se han probado, por lo tanto, optimice la solución un poco y no vuelva a probar los píxeles dos veces.
Esto podría ser bastante bueno usando la manipulación de imágenes y dibujando líneas rectas entre los píxeles (mosaicos) Si las líneas son semi transparentes y los bloques X son semitransparentes nuevamente. Puedes modificar el umbral de la imagen para determinar si la línea se ha cruzado con una ''X''
Si tiene una opción para usar una herramienta de terceros, entonces probablemente lo tome. A la larga, podría ser más rápido, pero entenderías menos sobre tu juego.
Si no quieres gastar el tiempo para reinventar / volver a implementar esto, hay muchos motores de juegos por ahí. Ogre3D es un motor de juegos de código abierto que admite completamente la iluminación, así como los controles de sonido y juegos.
De hecho, recientemente escribí esta funcionalidad en uno de mis proyectos.
void Battle::CheckSensorRange(Unit* unit,bool fog){
int sensorRange = 0;
for(int i=0; i < unit->GetSensorSlots(); i++){
if(unit->GetSensorSlot(i)->GetSlotEmpty() == false){
sensorRange += unit->GetSensorSlot(i)->GetSensor()->GetRange()+1;
}
}
int originX = unit->GetUnitX();
int originY = unit->GetUnitY();
float lineLength;
vector <Place> maxCircle;
//get a circle around the unit
for(int i = originX - sensorRange; i < originX + sensorRange; i++){
if(i < 0){
continue;
}
for(int j = originY - sensorRange; j < originY + sensorRange; j++){
if(j < 0){
continue;
}
lineLength = sqrt( (float)((originX - i)*(originX - i)) + (float)((originY - j)*(originY - j)));
if(lineLength < (float)sensorRange){
Place tmp;
tmp.x = i;
tmp.y = j;
maxCircle.push_back(tmp);
}
}
}
//if we''re supposed to fog everything we don''t have to do any fancy calculations
if(fog){
for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
}
}else{
bool LOSCheck = true;
vector <bool> placeCheck;
//have to check all of the tiles to begin with
for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
placeCheck.push_back(true);
}
//for all tiles in the circle, check LOS
for(int circleI = 0; circleI < (int) maxCircle.size(); circleI++){
vector<Place> lineTiles;
lineTiles = line(originX, originY, maxCircle[circleI].x, maxCircle[circleI].y);
//check each tile in the line for LOS
for(int lineI = 0; lineI < (int) lineTiles.size(); lineI++){
if(false == CheckPlaceLOS(lineTiles[lineI], unit)){
LOSCheck = false;
//mark this tile not to be checked again
placeCheck[circleI] = false;
}
if(false == LOSCheck){
break;
}
}
if(LOSCheck){
Map->GetGrid(maxCircle[circleI].x,maxCircle[circleI].y)->SetFog(fog);
}else{
LOSCheck = true;
}
}
}
}
Hay algunas cosas adicionales allí que no necesitarías si lo estás adaptando para tu propio uso. El tipo Lugar simplemente se define como una posición xey para el bien de las comodidades.
La función de línea está tomada de Wikipedia con modificaciones muy pequeñas. En lugar de imprimir las coordenadas xy, lo cambié para devolver un vector de lugar con todos los puntos en la línea. La función CheckPlaceLOS simplemente devuelve verdadero o falso en función de si el mosaico tiene un objeto en él. Hay más optimizaciones que se podrían hacer con esto, pero esto está bien para mis necesidades.
La comunidad de desarrollo de roguelike tiene un poco de obsesión con los algoritmos de campo de vista y línea de vista.
Aquí hay un enlace a un artículo de wiki de roguelike sobre el tema: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision
Para mi juego de roguelike, implementé un algoritmo de lanzamiento de sombras ( http://roguebasin.roguelikedevelopment.org/index.php?title=Shadow_casting ) en Python. Fue un poco complicado de armar, pero funcionó de manera razonablemente eficiente (incluso en Python puro) y generó buenos resultados.
El "campo de visión permisivo" parece estar ganando popularidad también: http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View
he implementado un campo de visión basado en mosaico en una sola función C. aquí está: https://gist.github.com/zloedi/9551625
Sé que esta es una pregunta de hace años, pero para cualquiera que busque este estilo de cosas, me gustaría ofrecer una solución que utilicé una vez para mis propios roguelike; FOV manualmente "precalculado". Si el campo de visión de la fuente de luz tiene una distancia exterior máxima, no es realmente un gran esfuerzo dibujar a mano las sombras creadas por el bloqueo de objetos. Solo necesita dibujar 1/8 del círculo (más las direcciones rectas y diagonales); puedes usar symmerty para los otros ocho. Tendrás tantos shadowmaps como cuadrados en esa 1/8 parte de un círculo. Entonces solo O juntos de acuerdo a los objetos.
Los tres principales pros para esto son: 1. Es muy rápido si se implementa correctamente 2. Se puede decidir cómo se debe lanzar la sombra, no se debe comparar qué algoritmo maneja qué situación es la mejor 3. No hay casos de borde inducido por algoritmos extraños que se deben de alguna manera arreglar
El problema es que realmente no puedes implementar un algoritmo divertido.
Aquí hay un enfoque muy simple pero bastante eficaz que utiliza el tiempo lineal en el número de mosaicos en la pantalla. Cada mosaico es opaco o transparente (eso nos lo dan), y cada uno puede ser visible o sombreado (eso es lo que intentamos calcular).
Comenzamos marcando el avatar como "visible".
Luego aplicamos esta regla recursiva para determinar la visibilidad de las fichas restantes.
- Si el mosaico está en la misma fila o columna que el avatar, solo se puede ver si el mosaico adyacente más cercano al avatar es visible y transparente.
- Si la ficha está en una diagonal de 45 grados desde el avatar, solo estará visible si la ficha diagonal contigua (hacia el avatar) es visible y transparente.
- En todos los demás casos, considere las tres fichas vecinas que están más cerca del avatar que la ficha en cuestión. Por ejemplo, si este mosaico está en (x, y) y está arriba y a la derecha del avatar, entonces los tres mosaicos a considerar son (x-1, y), (x, y-1) y (x- 1, y-1). La ficha en cuestión es visible si cualquiera de esas tres fichas es visible y transparente.
Para que esto funcione, los mosaicos deben inspeccionarse en un orden específico para garantizar que los casos recursivos ya se hayan calculado. Aquí hay un ejemplo de un orden de trabajo, comenzando desde 0 (que es el avatar en sí) y contando:
9876789
8543458
7421247
6310136
7421247
8543458
9876789
Las baldosas con el mismo número se pueden inspeccionar en cualquier orden entre ellas.
El resultado no es un hermoso sombreado, sino que computa la visibilidad creíble del mosaico.