Crear sombras en una cuadrícula 2D (1 fuente de luz + muchos muros)
En una cuadrícula de 30*50, hay 1 fuente de luz (amarilla) y más de 100 paredes (rojas) dispersas alrededor.
Pregunta: ¿Cómo calcular eficientemente un informe de toda la pantalla para determinar si cada bloque está en sombra? (Gris=sombra)
¿Existe algún nombre para dicho algoritmo?
Esto se utilizará para la inteligencia artificial. Por lo tanto, debe realizarse en la CPU, no en la GPU.
Mi solución muy lenta (pseudocódigo):
for cada bloque en todaLaCuadrícula {
bool estáEnSombra = false;
for cada pared en paredes {
estáEnSombra ||= verificar si "pared" proyecta sombra sobre "bloque"
}
// obtener el resultado del bloque
}
Para cada par (bloque vs. pared), es bastante rápido. Sin embargo, para toda la pantalla, es muy lento (O(pared * cantidadDeBloquesEnTodaLaPantalla)).
Mi segunda solución:
Cada pared genera de 1 a 3 nuevas paredes falsas adyacentes a sí misma en una dirección aproximadamente a 45 grados de distancia de la fuente de luz. Se realiza desde cerca de la fuente de luz primero, y luego se expande gradualmente.
Es rápido (O(cantidadDeBloquesEnTodaLaPantalla)), pero está equivocado. Los bloques azules se informan como si estuvieran en sombra, pero en realidad no lo están.
davy.ai
Algoritmo eficiente para el cálculo de sombras de bloques en C++ utilizando rasterización
Un algoritmo eficiente para calcular la sombra de bloques en toda la pantalla sería una técnica de rasterización. Podemos convertir toda la cuadrícula en una imagen rasterizada, donde cada píxel representa un bloque. Podemos usar una matriz 2D simple para almacenar el estado de cada píxel.
Luego podemos usar un método de ray casting para determinar si un bloque está en sombra o no. El método de ray casting funciona trazando un rayo desde la fuente de luz hasta cada píxel del bloque. Si el rayo colisiona con una pared antes de llegar al píxel, se considera que el píxel está en sombra. De lo contrario, se considera que está iluminado por la fuente de luz.
Para acelerar el proceso de ray casting, podemos utilizar el algoritmo de línea de Bresenham, que es un algoritmo rápido de dibujo de líneas. Podemos usar este algoritmo para determinar a través de qué píxeles pasa un rayo, sin calcular las coordenadas de todos los píxeles intermedios.
La técnica de rasterización y el método de ray casting se utilizan ampliamente en gráficos por computadora y se pueden implementar de manera eficiente en C++. No hay un nombre específico para este algoritmo, ya que es una combinación de diferentes técnicas.
Dado que este algoritmo se ejecuta en la CPU, debería ser adecuado para aplicaciones de inteligencia artificial.
Aquí tienes el pseudo código aproximado del algoritmo:
“`c++
// crear una matriz 2D para representar el estado de cada píxel
bool pixels[30][50] = {false};
// recorrer cada pared y marcar los píxeles correspondientes como bloqueados
for(auto& wall :walls){
for cada píxel bloqueado P en la pared {
pixels[P.x][P.y] = true;
}
}
// recorrer cada píxel y lanzar un rayo desde la fuente de luz
for(int x=0; x<30; x++){
for(int y=0; y<50; y++){
bool isInShadow = false;
// lanzar un rayo desde la fuente de luz hasta el píxel
for cada píxel P en el rayo {
// verificar si el píxel está bloqueado por una pared
if(pixels[P.x][P.y]){
isInShadow = true;
break;
}
}
// establecer el estado del píxel en función de si está en sombra o no
pixels[x][y] = isInShadow;
}
}
// la matriz 2D “pixels” ahora contiene el estado de cada píxel
// donde true significa que el píxel está en sombra y false significa que está iluminado por la fuente de luz
“`
Este algoritmo tiene una complejidad temporal de
O(cantidadDeBloquesEnTodaLaPantalla * paredes), dondeparedeses el número de paredes en la escena. Sin embargo, dado que solo recorremos cada pared una vez y lanzamos un rayo para cada píxel (lo cual es mucho más rápido que recorrer todas las paredes para cada píxel), este algoritmo debería ser mucho más rápido que el anterior mencionado en la pregunta.