¿Cómo calcular rápidamente el área de visión en un juego en mosaico 2D?

Tengo una matriz de mosaicos, en algunos de esos mosaicos hay objetos. Quiero calcular qué mosaicos son visibles para el jugador y cuáles no, y necesito hacerlo de manera bastante eficiente (para que calcule lo suficientemente rápido incluso cuando tengo matrices grandes (100x100) y muchos objetos).

Traté de hacerlo con el algoritmo de línea de Bresenham , pero fue lento. Además, me dio algunos errores:

----XXX-        ----X**-     ----XXX-
-@------        -@------     -@------
----XXX-        ----X**-     ----XXX-
(raw version)   (Besenham)   (correct, since tunnel walls are 
                              still visible at distance)

(@ is the player, X is obstacle, * is invisible, - is visible)

Estoy seguro de que esto se puede hacer, después de todo, tenemos NetHack, Zangband, y todos trataron este problema de alguna manera :)

¿Qué algoritmo puedes recomendar para esto?

Para mis necesidades, definiré visible de esta manera: el mosaico es visible cuando al menos una parte (por ejemplo, una esquina) del mosaico se puede conectar al centro del mosaico del jugador con una línea recta que no se cruza con ninguno de los obstáculos.

Su definición de visible es la siguiente:

el mosaico es visible cuando al menos una parte (por ejemplo, una esquina) del mosaico se puede conectar al centro del mosaico del jugador con una línea recta que no se cruza con ninguno de los obstáculos

Puedes implementar este concepto literalmente trazando rayos desde la ficha de tu jugador e intersectándolos con tu escena. Se rompe de cada iteración una vez que el rayo golpea un obstáculo (o excede un cierto umbral de distancia) ya que solo le interesan las fichas que el jugador puede ver directamente. Romperé el proceso por ti:

1. Especifique el nivel de precisión que le gustaría dar al algoritmo. Esta será la cantidad de rayos que trazará.
2. Divida el círculo completo de 360 ​​grados por la precisión elegida para saber cuántos grados rotar entre cada rayo.
3. Comenzando en 0 grados e incrementándose en la cantidad determinada en el paso 2, cree un rayo con el origen en el centro de la ficha del jugador y la dirección determinada por el ángulo actual.
4. Para cada rayo, comenzando desde la ficha del jugador, camine a lo largo de la dirección del rayo hasta llegar a una casilla de obstáculo. Agregue ese mosaico a la lista de mosaicos visibles y continúe con el siguiente rayo. También es posible que desee agregar una distancia máxima para "darse por vencido" en caso de que no se encuentre una colisión.

Aquí hay una imagen que muestra 3 rayos de ejemplo. Los mosaicos de color más oscuro son el "resultado" de cada rayo, es decir, dónde ocurrió la colisión. Sin embargo, deberías repetir esto en todo el círculo:

Ajuste la distancia máxima y el número de rayos para el rendimiento. Demasiado poco y perderás fichas, demasiado y tu rendimiento se verá afectado. Además, cuanto más lejos tengan que viajar los rayos, mayor será el "error" y mayor precisión necesitará.

Editar

Consulte el siguiente tutorial sobre emisión de rayos, en particular el Paso 3 y el Paso 4, para ayudarlo a implementar el bit de intersección del algoritmo:

http://www.permadi.com/tutorial/raycast/rayc7.html

Prefiero lanzar rayos de sombra en lugar de rayos de línea de visión.

Digamos que esta es su área de visualización (el área potencialmente visible)

######################
#####.............####
###................###
##..................##
#....................#
#....................#
#..........@.........#
#....................#
#....................#
##..................##
###................###
#####.............####
######################

Los # bloques no son visibles mientras que. son visibles

Pongamos un obstáculo X:

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXXX...........#
##..................##
###....X...........###
#####.............####
######################

Tiene una lista de las X que se encuentran dentro del área de visualización y luego marca como ocultas cada mosaico que está detrás de cada uno de estos obstáculos: cuando un obstáculo se marca como oculto, lo elimina de la lista.

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXX*...........#
##......##..........##
###....*#..........###
#####.###.........####
######################

En el ejemplo anterior, puede ver la sombra proyectada en el extremo derecho de la pared inferior y cómo esta sombra elimina el obstáculo oculto de la lista del obstáculo que debe verificar (X debe verificar; * marcado).

Si ordena la lista usando alguna partición binaria para que primero se verifiquen el costo X, puede acelerar ligeramente su verificación.

Puede usar una especie de algoritmo de "Batallas Navales" para verificar el bloque de X a la vez (básicamente buscando una X adyacente que esté en una dirección que pueda ensanchar el cono de sombra)

[EDITAR]

Se necesitan dos rayos para proyectar correctamente una sombra y, dado que un mosaico es rectangular, se pueden hacer muchas suposiciones utilizando las simetrías disponibles.

Las coordenadas del rayo se pueden calcular utilizando un espacio simple que se divide alrededor del mosaico de obstáculos:

Cada área rectangular constituye una elección sobre qué esquina del mosaico debe tomarse como borde de cono de sombra.

Este razonamiento se puede impulsar aún más para conectar múltiples mosaicos adyacentes y permitirles lanzar un solo cono más ancho de la siguiente manera.

El primer paso es asegurarse de que no haya obstáculos hacia la dirección del observador, en ese caso se considera el obstáculo más cercano:

Si el mosaico amarillo es un obstáculo, ese mosaico se convierte en el nuevo mosaico rojo.

Ahora consideremos el borde del cono superior:

Las fichas azules son todas posibles candidatas para permitir que el cono de sombra se ensanche: si al menos una de ellas es un obstáculo, el rayo se puede mover usando el espacio que se divide alrededor de esa ficha como se vio anteriormente.

El mosaico verde es un candidato solo si el observador está por encima de la línea naranja que sigue:

Lo mismo significa el otro rayo y las otras posiciones del observador sobre el obstáculo rojo.

La idea subyacente es cubrir la mayor cantidad de área posible para cada lanzamiento de cono y acortar lo más rápido posible la lista de obstáculos para verificar.

El problema que está intentando resolver a veces se llama Campo de visión, FOV para abreviar. Como mencionó roguelikes como ejemplos, debe echar un vistazo a lo que dice la wiki de RogueBasin sobre el tema (incluso hay enlaces a implementaciones): http://www.roguebasin.com/index.php?title=Field_of_Vision

Hay bastantes algoritmos diferentes con diferentes pros y contras: una comparación muy útil también está disponible en RogueBasin: http://www.roguebasin.com/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds

También encontré esto que tiene una demostración funcional:

http://www.redblobgames.com/articles/visibility/

Puede encontrar http://blogs.msdn.com/b/ericlippert/archive/2011/12/12/shadowcasting-in-c-part-one.aspx útil junto con el resto de la serie .