Línea de visión diagonal con dos esquinas.

En este momento estoy usando el algoritmo de línea de Bresenham para la línea de visión. El problema es que he encontrado un caso de borde donde los jugadores pueden mirar a través de las paredes. Ocurre cuando el jugador mira entre dos esquinas de una pared con un espacio en el otro lado en ángulos específicos.

El resultado que quiero es que el mosaico entre dos paredes se marque como no válido.

¿Cuál es la forma más rápida de modificar el algoritmo de línea de Bresenham para resolver esto? Si no hay una buena solución, ¿hay un algoritmo más adecuado? Cualquier idea es bienvenida. Tenga en cuenta que la solución también debe ser compatible con 3d.

Editar: Mi solución simple fue verificar si ambas esquinas están cerradas cuando cambian las coordenadas x e y de una línea. Para ver el código fuente de trabajo y una demostración interactiva del producto completo, consulte http://ashblue.github.io/javascript-pathfinding/

Eric Lippert escribió una excelente serie sobre la generación de la línea de visión en C # con Shadow Casting en una cuadrícula plana rectangular.

Entre otras cuestiones, Eric se ocupó de varias preguntas que deben responderse sobre los requisitos de la línea de visión, que dan resultados diferentes y dan ejemplos de un par de resultados diferentes. Uno de los artículos trata en profundidad la circunstancia de "mirar a la vuelta de la esquina" que ocurrió en una versión temprana de su algoritmo.

He adaptado el algoritmo de Eric a una cuadrícula hexagonal aquí , y lo utilicé con éxito en grandes cuadrículas hexagonales (> 400 x 700) con un radio de visibilidad extenso (> 60 hexes). Esta implementación calcula y muestra el campo de visión completo tan rápido como puedo parpadear, usando una sola CPU i7. Esto es sin duda lo suficientemente rápido para cualquier uso que espero utilizar.

Actualización : línea de visión con elevación:
la implementación de cuadrícula hexagonal vinculada a la anterior calcula la línea de visión con elevación, no solo obstáculos. Las notas de documentación también analizan una decisión adicional que debe tomarse con respecto a los cálculos de elevación: la altura del objetivo y la altura del observador. La selección predeterminada es hacer que ambos sean iguales, lo que crea un campo de visión simétrico, pero también se puede seleccionar tierra a tierra y ojos de observador a tierra. (El código es de código abierto bajo licencia MIT)

¿Qué pasa si para el cálculo de LOS tiene una cuadrícula separada de "mayor resolución" que llena los espacios en las esquinas? Estaba pensando en algo como esto:

La izquierda es la sección del bloque original de 4 cuadrados.

La derecha es la versión de "alta resolución", ya que puede ver que cada cuadrado original se subdividió en cuartos y se ha llenado una de las esquinas. No estoy seguro de que el algoritmo genere eso, pero puede calcularse previamente del mapa actual

Significa que el espacio de coordenadas se cuadruplica pero no imagino que sea un problema de rendimiento significativo.