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

24

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.

Rogach
fonte
11
Opa, o meu erro, NetHack foi não mexer com line-of-sight :)
Rogach
Algumas idéias mais antigas podem ser encontradas em fadden.com/tech/fast-los.html , embora isso remonta aos dias em que as CPUs eram relativamente lentas e os cálculos de ponto flutuante eram algo que deveria ser evitado.
Fadden

Respostas:

10

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:

insira a descrição da imagem aqui

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

David Gouveia
fonte
Devo apenas "caminhar" ao longo de cada raio por uma distância fixa (digamos, 0,3 pontos) ou preciso executar algo como o algoritmo de Besenham em cada raio?
Rogach
Se você avançar apenas por uma distância fixa, terá problemas com as peças perdidas. Confira este tutorial sobre raycasting . Também vou editar esse recurso na minha resposta. Você basicamente verifica colisões horizontais e verticais separadamente.
David Gouveia
11
O algoritmo é bom, mas exigirá uma quantidade enorme de raios para funcionar corretamente com túneis longos de 1 peça de largura.
precisa saber é o seguinte
@HolyBlackCat - esse será o caso apenas se você enviar raios em ângulos uniformes em todas as direções. Mas você pode evitar o envio da maioria desses raios e apenas jogá-los nas extremidades da sua cena. Aqui está uma boa explicação: redblobgames.com/articles/visibility
Rogach
8

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:

Exemplo de particionamento de espaço

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:

escolha o obstáculo mais próximo

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

Agora vamos considerar a borda superior do cone:

telhas candidatas

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:

verificação estendida

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.

FxIII
fonte
Abordagem interessante e provavelmente uma idéia melhor por causa de sua natureza subtrativa. Depois de ler isso, eu provavelmente implementaria dessa maneira também.
David Gouveia
Eu posso prever problemas em situações como esta . Jogador em amarelo, obstáculos em azul e roxo. O jogador deve conseguir ver o obstáculo roxo (como mostra o raio verde). Mas o raio vermelho que atravessa o obstáculo azul rejeita o azulejo roxo. Mas acho que a versão da linha de visão tem o potencial de ter problemas maiores que isso.
David Gouveia
Esse problema vem da definição de "oculto": quando um raio cruza um ladrilho, ele quase nunca o cobre completamente. O mesmo problema é resolvido com o alias ao renderizar segmentos de linha. Pessoalmente, acho que um ladrilho fica oculto quando a maior parte dele é coberta, pode-se defini-lo oculto é totalmente coberto, você pode descobrir se ele expõe um lado que potencialmente pode aumentar o cone da sombra ... De qualquer forma, você pode lista apenas os blocos que estão totalmente cobertos.
FXIII
@DavidGouveia - que problemas maiores?
Rogach 6/01/12
@ DavidGouveia - Eu já tentei abordagem com sombra "cones", e foi muito ineficiente. Quanto à precisão dos raios de visibilidade - ~ 5500 raios são suficientes para ver a parede com 20 ladrilhos em cada direção, se você estiver diretamente perto dele, e a distância em que apenas um único ladrilho é visível é muito mais. E quanto a perder alguns ladrilhos a uma distância maior - bem, nem todo mundo tem uma visão perfeita, não é?
Rogach 6/01/12
8

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=

Tapio
fonte
Resumo realmente bom e completo!
Rogach
Esse site é um ótimo recurso, obrigado por compartilhar esse link. Ele também contém uma descrição incrivelmente compreensível de como o A * pathfinding funciona :-)
uliwitness
O link da resposta agora vai para a página inicial do site - roguebasin.com/index.php?title=Category:FOV parece ser uma correspondência razoável.
Fadden