Calcular qué fichas se iluminan en un juego basado en fichas ("raytracing")

Puede entrar en todo tipo de complejidades con el cálculo de la oclusión, etc., o puede optar por el método de fuerza bruta simple: Para cada celda, use un algoritmo de dibujo de líneas como el Algoritmo de Línea de Bresenham para examinar cada celda entre la actual y la fuente de luz. Si hay celdas llenas o (si solo tiene una fuente de luz) celdas que ya se han probado y se ha encontrado que están en sombra, su celda está en sombra. Si encuentra una celda que se sabe que está encendida, su celda del mismo modo se encienda. Una optimización fácil para esto es establecer el estado de cualquier celda que encuentre a lo largo de la línea a lo que sea el resultado final.

Esto es más o menos lo que usé en mi entrada ganadora del IOCCC 2004. Obviamente eso no hace un buen código de ejemplo, sin embargo. ;)

Editar: Como loren señala, con estas optimizaciones, solo necesita elegir los píxeles a lo largo del borde del mapa para trazar.

Los algoritmos que se presentan aquí me parecen hacer más cálculos de los que creo que son necesarios. No he probado esto, 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 hasta la luz. Si esa línea golpea una obstrucción, marque todos los píxeles desde el borde hasta justo más allá de la obstrucción como si estuvieran en sombra.

Rápido y sucio:

(Dependiendo del tamaño del array)

• Bucle a través de cada azulejo
• dibuja una línea hacia la Luz
• Si cualquier par de la línea golpea una X, entonces está en sombra
• (Opcional): calcule la cantidad de X que pasa la línea y haga cálculos sofisticados para determinar la proporción de la baldosa en sombra. NB: Esto se podría hacer suavizando la línea entre el azulejo y la Luz (por lo tanto, mirando otros azulejos a lo largo de la ruta de regreso a la fuente de luz) durante el procedimiento de umbral, estos aparecerán como anomalías pequeñas. Dependiendo de la lógica utilizada, podría determinar potencialmente cuánto (si es que lo hace) está el mosaico en sombra.

También puede realizar un seguimiento de los píxeles que se han probado, por lo tanto, optimizar un poco la solución y no volver a probar los píxeles dos veces.

Esto podría ser cúpula bastante bien mediante el uso de la manipulación de la imagen y el dibujo de líneas rectas entre pixles (azulejos) Si las líneas son semi transparentes y los bloques X son semitransparentes de nuevo. Puede establecer el umbral de la imagen para determinar si la línea ha intersectado una 'X'

Si tiene una opción para usar una herramienta de terceros, entonces Id probablemente la tome. A la larga, podría resultar más rápido, pero entenderías menos sobre tu juego.

Esto es solo por diversión:

Puedes replicar el enfoque de Doom 3 en 2D si primero haces un paso para convertir tus fichas 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 la luz. (En esta escena, solo se consideraría la línea diagonal.) Para cada línea, proyectarlo en un trapezoide cuyo borde frontal es la línea original, cuyos lados se encuentran en las líneas de la fuente de luz a través de cada punto final, y cuya espalda está muy lejos, más allá de toda la escena. Por lo tanto, es un trapezoide que "apunta" a la luz. Contiene todo el espacio sobre el que la pared proyecta su sombra. Llena cada ficha de este trapezoide con oscuridad.

Proceda a través de todas estas líneas y terminará con una "plantilla" que incluye todas las fichas visibles desde la fuente de luz. Rellene estos azulejos 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.

Para comprobar si una baldosa está en sombra, debe dibujar una línea recta de vuelta a la fuente de luz. Si la línea se cruza con otra baldosa que está ocupada, entonces la baldosa que estaba probando está en sombra. Los algoritmos de trazado de rayos hacen esto para cada objeto (en su mosaico de casos) en la vista.

El artículo Raytracing en Wikipedia tiene pseudocódigo.

Aquí hay un enfoque muy simple pero bastante efectivo que utiliza el tiempo lineal en el número de mosaicos en la pantalla. Cada mosaico es opaco o transparente (que se nos da), y cada uno puede ser visible o sombreado (eso es lo que estamos tratando de calcular).

Empezamos marcando el avatar como "visible".

Luego aplicamos esta regla recursiva para determinar la visibilidad de los mosaicos restantes.

1. Si el mosaico está en la misma fila o columna que el avatar, entonces es solo visible si la ficha adyacente más cercana al avatar es visible y transparente.
2. Si el azulejo está en una diagonal de 45 grados desde el avatar, entonces solo es visible si el azulejo diagonal vecino (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 esta ficha está en (x,y) y está arriba y a la derecha del avatar, entonces las tres fichas 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 azulejos deben inspeccionarse en un orden específico para asegurarse de que los casos recursivos ya están calculados. Aquí hay un ejemplo de un orden de trabajo, comenzando desde 0 (que es el avatar mismo) y contando hacia arriba:

9876789
8543458
7421247
6310136
7421247
8543458
9876789

Los azulejos con el mismo número se pueden inspeccionar en cualquier orden entre ellos mismos.

El resultado no es un hermoso sombreado, sino que calcula la visibilidad creíble de los mosaicos.

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

Para el escenario de iluminación parcial, podría tenerlo de modo que si un azulejo resulta en sombra, ese azulejo se divide en 4 azulejos y cada uno de ellos se prueba. ¿Podrías dividirlo todo lo que quisieras?

Editar:

También puede optimizarlo un poco al no probar ninguno de los mosaicos adyacentes a una luz, esto sería más importante cuando tiene múltiples fuentes de luz, supongo...

Recientemente he escrito 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 de lugar se define simplemente como una posición x e y por razones de comodidad.

La función line se toma 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. Los CheckPlaceLOS la función solo devuelve true o false en función de si el mosaico tiene un objeto en él. Hay algunas optimizaciones más que se podrían hacer con esto, pero esto está bien para mis necesidades.

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 usé una vez para un roguelike propio; FOV "precalculado" manualmente. Si el campo de visión de la fuente de luz tiene una distancia exterior máxima, realmente no es mucho esfuerzo dibujar a mano las sombras creadas por el bloqueo de objetos. Solo necesita dibujar 1/8 del círculo (más las direcciones recta y diagonal); puede usar symmerty para los otros ocho. Tendrás tantos shadowmaps como usted tiene cuadrados en ese 1/8 de un círculo. Entonces solo O juntos de acuerdo a los objetos.

Los tres pros principales para esto son: 1. Es muy rápido si se implementa correctamente 2. Puedes decidir cómo se debe proyectar la sombra, sin comparar qué algoritmo maneja qué situación es la mejor 3. Ningún algorith raro indujo casos de borde que usted tiene que arreglar de alguna manera

La estafa es que realmente no puedes implementar un algoritmo divertido.

Si no quieres pasar el tiempo para reinventar/volver a implementar esto, hay un montón de motores de juego por ahí. Ogre3D es un motor de juego de código abierto que admite completamente la iluminación, así como el sonido y los controles del juego.

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