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

https://stackoverflow.com/questions/174659

05-07-2019
|

Pregunta

Estoy escribiendo un pequeño juego basado en fichas, para el que me gustaría apoyar las fuentes de luz. Pero mi algoritmo-fu es demasiado débil, por eso acudo a ti en busca de ayuda.

La situación es así: hay un mapa basado en mosaicos (mantenido como una matriz 2D), que contiene una única fuente de luz y varios elementos alrededor. Quiero calcular qué baldosas están iluminadas por la fuente de luz y cuáles están en la sombra.

Una ayuda visual de cómo 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 los -s son azulejos en 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 loseta puede estar en media sombra debido a que está parcialmente oculta. El algoritmo no tendría que 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.)

¿Algún comprador?

Solución

La comunidad de desarrollo roguelike tiene un poco de obsesión con los algoritmos de línea de visión, campo de visión.

Aquí hay un enlace a un artículo de roguelike wiki 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 vista permisivo " parece estar ganando popularidad también: http://roguebasin.roguelikedevelopment.org/index.php?title=Permissive_Field_of_View_of_View

Otros consejos

Puede obtener todo tipo de complejidades al calcular la oclusión, etc., o puede optar por el método simple de fuerza bruta: para cada celda, use un algoritmo de dibujo de líneas como Algoritmo de línea de Bresenham para examinar cada celda entre la actual y la fuente de luz. Si alguna es celdas rellenas o (si solo tiene una fuente de luz) las celdas que ya se han probado y se encuentran en la sombra, su celda está en la sombra. Si se encuentra con 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 cualquier celda que encuentre a lo largo de la línea a cualquiera que sea el resultado final.

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

Editar: como señala loren, con estas optimizaciones, solo necesitas seleccionar los píxeles a lo largo del borde del mapa para rastrear.

Los algoritmos que se presentan aquí me parecen que hacen más cálculos de los que creo que son necesarios. No he probado esto, pero creo que funcionaría:

Inicialmente, marca 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, marca todos los píxeles desde el borde hasta justo más allá de la obstrucción como si estuvieran en la sombra.

Rápido y sucio:

(Dependiendo de qué tan grande sea la matriz)

Recorre cada ficha
dibuja una línea hacia la Luz
Si alguna parte 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 sofisticados para determinar la proporción del azulejo en la sombra. NB: Esto se puede hacer suavizando la línea entre la baldosa y la Luz (por lo tanto, mirando otras baldosas a lo largo de la ruta de regreso a la fuente de luz) durante el proceso de umbral, aparecerán como pequeñas anomolías. Dependiendo de la lógica utilizada, podría determinar la cantidad (si la hay) del mosaico en la sombra.

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

Este domo podría ser bastante bueno utilizando la manipulación de imágenes y dibujando líneas rectas entre los píxeles (mosaicos) Si las líneas son semitransparentes y los bloques X son semitransparentes nuevamente. Puede crear un 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 es probable que la identificación 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 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, haz lo que hace el motor Doom 3: desde la perspectiva de la fuente de luz, considera cada " pared " que se enfrenta a la luz. (En esta escena, solo se consideraría la línea diagonal). Para cada línea de este tipo, proyectarla en un trapecio cuyo borde frontal es la línea original, cuyos lados se encuentran en las 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 trapezoide que " apunta a " la luz. Contiene todo el espacio sobre el que el muro proyecta su sombra. Rellena todas las fichas de este trapecio con oscuridad.

Continúa por todas estas líneas y terminarás con una " plantilla " Eso incluye todos los azulejos visibles desde la fuente de luz. Rellena estos azulejos con el color claro. Es posible que desee encender un poco menos la baldosa a medida que se aleja de la fuente (" atenuación ") o hacer otras cosas elegantes.

Repita para cada fuente de luz en su escena.

Para verificar si un azulejo está en la sombra, debe dibujar una línea recta de regreso a la fuente de luz. Si la línea se interseca con otra ficha que está ocupada, entonces la ficha que estaba probando está en la sombra. Los algoritmos de trazado de rayos hacen esto para cada objeto (en el mosaico de su caso) en la vista.

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

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

Comenzamos marcando el avatar como " visible " ;.

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

Si el mosaico está en la misma fila o columna que el avatar, solo será visible si el mosaico adyacente más cercano al avatar es visible y transparente.
Si el mosaico está en una diagonal de 45 grados con respecto al avatar, solo será visible si el azulejo diagonal adyacente (hacia el avatar) es visible y transparente.
En todos los demás casos, considere los tres mosaicos adyacentes que están más cerca del avatar que el mosaico 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 esos tres mosaicos es visible y transparente.

Para que esto funcione, los mosaicos deben inspeccionarse en un orden específico para garantizar que los casos recursivos ya estén computados. Aquí hay un ejemplo de un orden de trabajo, comenzando desde 0 (que es el propio avatar) y contando:

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

El resultado no es un hermoso lanzamiento de sombras, pero calcula una visibilidad de mosaico creíble.

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

Para el escenario de iluminación parcial, podría tenerlo de manera que si una baldosa resulta en sombra, esa baldosa se divida en 4 baldosas y se pruebe cada una de ellas. ¿Entonces podrías dividir eso tanto como quisieras?

Editar:

También puede optimizarlo un poco si no prueba ninguna de las baldosas adyacentes a una luz. Esto sería más importante cuando tenga varias fuentes de luz, supongo ...

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 las adaptas para tu propio uso. El tipo de lugar se define simplemente como una posición x e y por conveniencia.

La función de línea se toma de Wikipedia con modificaciones muy pequeñas. En lugar de imprimir las 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 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 tipo de cosas, me gustaría ofrecer una solución que utilicé una vez para mi propio roguelike; manualmente " precalculado " FOV. Si el campo de visión de la fuente de luz tiene una distancia externa 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 rectas y diagonales); Puedes usar la simetría para las otras ocho. Tendrás tantos mapas de sombras como cuadrados en ese 1/8 de círculo. Entonces solo O ellos juntos de acuerdo a los objetos.

Los tres principales pros para esto son: 1. Es muy rápido si se implementa correctamente. 2. Tienes que decidir cómo se debe proyectar la sombra, sin comparar qué algoritmo maneja la mejor situación. 3. No hay casos extraños inducidos por algoritmos extraños que tengas que arreglar de alguna manera

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

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

Si no quieres perder el tiempo reinventando / reimplementando esto, hay muchos motores de juego por ahí. Ogre3D es un motor de juego de código abierto que es totalmente compatible con la iluminación, así como con los controles de sonido y juego.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow