Cálculo de las fichas que se encienden en un juego basado en fichas ("trazado de rayos")

Question

Estoy escribiendo un pequeño juego basado en fichas, para el cual me gustaría admitir 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 la siguiente: 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 fraccional sería aún mejor, por supuesto, donde una baldosa puede estar en un medio de sombras debido a ser parcialmente oscurecido. 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 sólo un bucle.)

Toda la toma?

Answer 1

La comunidad de desarrollo de roguelike tiene una obsesión con los algoritmos de campo de visión y línea de vista.

Aquí hay un enlace a un artículo roguelike wiki sobre el tema: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

Para mi juego roguelike, he implementado un algoritmo de bastidor de la sombra (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 "permisiva Campo de visión" parece estar ganando popularidad, así: http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View

Answer 2

rápida y sucia:

(Dependiendo del tamaño de la matriz es)

• bucle a través de cada baldosa
• dibujar una línea a la luz
• Si alguna pary de la línea golpea una X, luego 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 una cúpula bastante bien utilizando 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. Puede modificar el umbral de la imagen para determinar si la línea se ha cruzado con una 'X'

Si tiene una opción para utilizar 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.

Answer 3

Para comprobar si una ficha está en la sombra, debe dibujar una línea recta hacia 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 Raytracing article en Wikipedia tiene pseudocódigo.

Answer 4

Si no quieres perder 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.

Answer 5

Puede entrar en todo tipo de complejidades con el cálculo de oclusión, etc., o puede usar el método de fuerza bruta simple: para cada celda, use un algoritmo de dibujo de líneas como Bresenham Line Algorithm para examinar cada celda entre la actual y la fuente de luz. 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 usé en mi 2004 IOCCC winning entry. Obviamente, eso no es un buen ejemplo de código. ;)

Editar: Como Loren señala, con estas optimizaciones, solo tiene que elegir los píxeles a lo largo del borde del mapa para seguir.

Answer 6

La solución de TK es la que generalmente usaría para este tipo de cosas.

Para el escenario de iluminación parcial, puede tenerlo de modo que si una baldosa resulta en una sombra, esa loseta se divide en 4 mosaicos y cada uno de ellos se prueba. ¿Entonces podrías dividir todo lo que quisieras?

Editar:

También puede optimizar un poco al no probar cualquiera de las casillas adyacentes a una luz - esto sería más importante que hacer cuando se tiene múltiples fuentes de luz, supongo ...

Answer 7

Los algoritmos que se presentan aquí me parecen estar haciendo 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 Arachnid sugirió, utilice 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.

Answer 8

Esto es sólo por diversión:

Puede reproducir el enfoque de Doom 3 en 2D si primero se hace un paso para convertir tus mosaicos en líneas Por ejemplo,

- - - - - 
- X X X - 
- X X - - 
- X - - - 
- - - - L 

... se reducirían 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 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 desde 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.

proceder a través de todas las líneas y el resultado final será con una "plantilla" 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.

Answer 9

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 coordenadas x y, 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.

Answer 10

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".

A continuación, aplicamos esta regla recursiva para determinar la visibilidad de las teselas restantes.

1. Si el mosaico está en la misma fila o columna que el avatar, entonces solo está visible si el mosaico adyacente más cercano al avatar es visible y transparente.
2. Si la ficha está en una diagonal de 45 grados del avatar, entonces solo es visible si la ficha diagonal contigua (hacia el avatar) es visible y transparente.
3. 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). El mosaico en cuestión es visible si cualquiera de los de esos tres mosaicos es visible y transparente.

Para realizar este trabajo, los mosaicos deben inspeccionarse en un orden específico para garantizar que los casos recursivos ya se hayan calculado. Aquí está un ejemplo de una orden de trabajo, a partir de 0 (que es el avatar sí mismo) y contando:

9876789 
8543458 
7421247 
6310136 
7421247 
8543458 
9876789 

Azulejos con el mismo número pueden ser inspeccionados en cualquier orden entre ellos.

El resultado no es un hermoso sombreado de sombras, sino que computa la visibilidad del mosaico.

Answer 11

he implementado el campo de vista basado en mosaico en una sola función C. aquí está: https://gist.github.com/zloedi/9551625

Answer 12

Sé que esta es una pregunta de años, pero para cualquiera que busque este estilo de cosas, me gustaría ofrecer una solución que utilicé una vez para un 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.

Las tres ventajas principales para esto son: 1. Es muy rápido en caso de aplicarse la derecha 2. Tienes la oportunidad de decidir cómo la sombra sea echado, sin comparación, que algorith asas que la mejor situación 3. No se algorith raro casos de borde inducido que tiene que arreglar de alguna manera

El problema es que realmente no se puede implementar un algoritmo divertido.