Localizando peças não obstruídas no jogo baseado em peças

Estou trabalhando em um jogo 2D baseado em blocos e, no momento, estou tentando obter um equivalente em 2D dos volumes de sombra para funcionar. Estou tendo problemas para encontrar as superfícies que devem projetar sombras. A partir de qualquer ponto do jogo, preciso encontrar os rostos não obstruídos ou o bloco inteiro.

Minha pergunta é: como posso encontrar esses ladrilhos / arestas o mais rápido possível, considerando um ponto?

Há muito trabalho feito para esse problema na comunidade de roguelike.

Aqui está uma página que lista alguns algoritmos e bibliotecas que podem ajudá-lo. http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision

Esta não é uma resposta completa, mas espero que ajude.

O seu mapa / conjunto de blocos estático ou dinâmico? Se é estática, eu fortemente incentivá-lo a fazer o processamento off-line e precompute tanto quanto você pode assim. Você pode fazê-lo da maneira que quiser (raycasting ou algo mais inteligente), mas não se importa em acelerar muito, porque tudo acontecerá offline enquanto você "assa" seus níveis. Você pode pré-calcular exatamente quais blocos são visíveis em cada ponto ou criar algum tipo de região maior e todos os blocos potencialmente visíveis em cada região.

Em tempo de execução, a consulta dos blocos visíveis deve ser muito direta e muito rápida.

Obviamente, se você está criando níveis dinamicamente, isso não se aplica :-)

Você pode ver como eu implementei isso para um c # roguelike aqui . O código não é altamente otimizado, mas parece ser rápido o suficiente para mim e (mais importante) deve ser bastante fácil de ler. É basicamente criar um algoritmo simples de projeção de sombras que funciona um octante de cada vez.

Não tenho certeza de qual plataforma você está, mas não consigo pensar em nenhuma plataforma que não fosse rápida o suficiente para fazer um círculo em torno de suas entidades de transmissão de luz (a menos que haja muitas) e detectar se o um bloco prestes a ser plotado no algoritmo do seu círculo é um bloco sólido e, portanto, bloqueia a luz. A partir daí, seria um pouco mais complicado, pois você teria que acompanhar os segmentos do círculo que estão ocluídos ou não, mas seria o que eu faria. Outra opção seria lançar raios em um círculo (novamente bem rápido) no espaço de resolução do bloco e parar cada raio quando ele atingir um bloco sólido.