Encontrar fichas desocupadas en un juego basado en fichas

Estoy trabajando en un juego basado en mosaicos 2D, y en este momento estoy tratando de hacer que funcione un equivalente en 2D de los volúmenes de sombra. Tengo problemas para encontrar las superficies que deberían proyectar sombras. Desde cualquier punto del juego, necesito encontrar las caras desocupadas o todo el mosaico.

Mi pregunta es, ¿cómo puedo encontrar estos mosaicos / bordes lo más rápido posible dado un punto?

Se ha trabajado mucho para resolver ese problema en la comunidad roguelike.

Aquí hay una página que enumera algunos algoritmos y bibliotecas que podrían ayudarlo. http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

Esta no es una respuesta completa, pero espero que ayude.

¿Su mapa / mosaico está configurado como estático o dinámico? Si es estático, lo haría recomiendo encarecidamente que realice el procesamiento fuera de línea y precalcule todo lo que pueda de esa manera. Puede hacerlo de la forma que desee (emisión de rayos o algo más inteligente), pero realmente no le importa hacerlo muy rápido porque todo sucederá sin conexión mientras "hornea" sus niveles. Puede precalcular exactamente qué mosaicos son visibles desde cada punto, o crear algún tipo de regiones más grandes y todos los mosaicos potencialmente visibles desde cada región.

Luego, en tiempo de ejecución, la consulta de los mosaicos visibles debe ser muy sencilla y muy rápida.

Por supuesto, si tiene niveles creados dinámicamente, esto no se aplica en absoluto :-)

Puedes ver cómo implementé esto para un C # roguelike aquí . El código no está muy optimizado, pero parece ser lo suficientemente rápido para mí y (más importante) debería ser bastante fácil de leer. Básicamente está haciendo un algoritmo simple de proyección de sombras que funciona un octavo a la vez.

No estoy seguro de en qué plataforma se encuentra, pero realmente no puedo pensar en ninguna plataforma que no sea lo suficientemente rápida como para hacer crecer un círculo alrededor de sus entidades de transmisión de luz (a menos que haya muchas em) y detectar si El mosaico a punto de ser "trazado" en su algoritmo de círculo es un mosaico sólido y, por lo tanto, bloqueador de luz. A partir de ahí, sería un poco más complicado, ya que tendría que realizar un seguimiento de los segmentos del círculo que están ocluidos o no, pero sería lo que haría. Otra opción sería lanzar rayos en un círculo (de nuevo bastante rápido) en el espacio de resolución de mosaico y detener cada rayo cuando golpea un mosaico sólido.