Como calcular rapidamente a área de visão em um jogo 2D em mosaico?

Eu tenho uma matriz de ladrilhos, em alguns desses ladrilhos existem objetos. Quero calcular quais peças são visíveis para o jogador e quais não são, e preciso fazê-lo com bastante eficiência (para que ele calcule com rapidez suficiente, mesmo que possua matrizes grandes (100x100) e muitos objetos).

Tentei fazê-lo com o algoritmo de linha de Bresenham , mas foi lento. Além disso, isso me deu alguns erros:

----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)

Tenho certeza de que isso pode ser feito - afinal, temos o NetHack, o Zangband e todos eles lidaram com esse problema de alguma forma :)

Qual algoritmo você pode recomendar para isso?

Para minhas necessidades, definirei visível assim: o bloco é visível quando pelo menos uma parte (por exemplo, canto) do bloco pode ser conectada ao centro do bloco do jogador com uma linha reta que não cruza nenhum obstáculo.

Sua definição de visible é a seguinte:

o mosaico é visível quando pelo menos uma parte (por exemplo, canto) do mosaico pode ser conectada ao centro do mosaico do jogador com uma linha reta que não cruza nenhum obstáculo

Você pode implementar esse conceito literalmente traçando os raios do bloco do jogador e cruzando-os com a cena. Você interrompe cada iteração quando o raio atinge um obstáculo (ou excede um determinado limite de distância), pois você está interessado apenas nas peças que o jogador pode ver diretamente. Vou terminar o processo para você:

1. Especifique o nível de precisão que você deseja fornecer ao algoritmo. Esse será o número de raios que você rastreará.
2. Divida o círculo completo de 360 ​​graus pela precisão escolhida para saber quantos graus rodar entre cada raio.
3. Começando em 0 graus e aumentando a quantidade determinada na etapa 2, crie um raio com a origem no centro do bloco do jogador e a direção determinada pelo ângulo atual.
4. Para cada raio, começando pelo ladrilho do jogador, caminhe na direção do raio até atingir um ladrilho de obstáculos. Adicione esse bloco à lista de blocos visíveis e prossiga para o próximo raio. Você também pode adicionar uma distância máxima para "desistir" caso nenhuma colisão seja encontrada.

Aqui está uma imagem mostrando três raios de exemplo. Os azulejos coloridos mais escuros são o "resultado" de cada raio, ou seja, onde a colisão ocorreu. Você precisaria repetir isso em todo o círculo:

Ajuste a distância máxima e o número de raios para obter o desempenho. Muito pouco e você sentirá falta de peças, e seu desempenho será prejudicado. Além disso, quanto mais longe os raios viajarem, maior será o "erro" e mais precisão você precisará.

Editar

Verifique o seguinte tutorial sobre raycasting, em particular as etapas 3 e 4, para ajudá-lo a implementar o bit de interseção do algoritmo:

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

Prefiro lançar raios de sombra em vez de raios de linha de visão.

Digamos que esta seja sua área de visualização (a área potencialmente visível)

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

Os # blocos não são visíveis enquanto o. são visíveis

Vamos colocar um obstáculo X:

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

Você tem uma lista dos X que estão na área de visualização e marca como ocultos todos os blocos que estão atrás de cada um desses obstáculos: quando um obstáculo é marcado como oculto, você o remove da lista.

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

No exemplo acima, você pode ver a sombra projetada pela extremidade direita da parede inferior e como essa sombra exclui o obstáculo oculto da lista do obstáculo que você deve verificar (X precisa verificar; * verificado).

Se você classificar a lista usando alguma partição binária, para que o X mais confortável seja verificado primeiro, você pode acelerar um pouco sua verificação.

Você pode usar uma espécie de algoritmo "Batalhas Naval" para verificar o bloco de Xs de uma só vez (basicamente procurando por um X adiacent que esteja em uma direção que possa aumentar o cone da sombra)

[EDITAR]

São necessários dois raios para projetar corretamente uma sombra e, como um bloco é retangular, muitas suposições podem ser feitas usando as simetrias disponíveis.

As coordenadas dos raios podem ser calculadas usando um particionamento simples de espaço ao redor do bloco de obstáculos:

Cada área retangular constitui uma escolha sobre qual canto do ladrilho deve ser considerado como borda do cone da sombra.

Esse raciocínio pode ser aprimorado para conectar vários ladrilhos adjacentes e permitir que eles projetem um único cone mais largo, conforme a seguir.

O primeiro passo é garantir que não haja obstáculos na direção do observador; nesse caso, o obstáculo mais próximo é considerado:

Se o ladrilho amarelo é um obstáculo, esse ladrilho se torna o novo ladrilho vermelho.

Agora vamos considerar a borda superior do cone:

Os azulejos azuis são todos possíveis candidatos a deixar o cone da sombra mais largo: se pelo menos um deles for um obstáculo, o raio pode ser movido usando o espaço particionado em torno desse azulejo, como visto anteriormente.

O ladrilho verde é candidato apenas se o observador estiver acima da linha laranja a seguir:

O mesmo vale para o outro raio e para as outras posições do observador em relação ao obstáculo vermelho.

A idéia subjacente é cobrir o máximo de área possível para cada vazamento de cone e reduzir o mais rápido possível a lista de obstáculos a serem verificados.

O problema que você está tentando resolver é chamado de Campo de visão, FOV, para abreviar. Como você mencionou roguelikes como exemplos, dê uma olhada no que o wiki do RogueBasin tem a dizer sobre o assunto (há até links para implementações): http://www.roguebasin.com/index.php?title=Field_of_Vision

Existem alguns algoritmos diferentes, com prós e contras diferentes - uma comparação muito útil também está disponível no RogueBasin: http://www.roguebasin.com/index.php?title=

Eu também encontrei este que tem uma demonstração de trabalho:

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

Você pode encontrar http://blogs.msdn.com/b/ericlippert/archive/2011/12/12/shadowcasting-in-c-part-one.aspx útil junto com o restante da série .