No momento, estou usando o algoritmo de linha de Bresenham como linha de visão. O problema é que encontrei um caso em que jogadores podem olhar através das paredes. Ocorre quando o jogador olha entre dois cantos de uma parede com um espaço do outro lado em ângulos específicos.
O resultado que desejo é que o bloco entre duas paredes seja marcado como inválido.
Qual é a maneira mais rápida de modificar o algoritmo de linha de Bresenham para resolver isso? Se não houver uma boa solução, existe um algoritmo mais adequado? Todas as idéias são bem-vindas. Observe que a solução também deve ser capaz de suportar 3d.
Edit: Minha solução simples foi verificar se os dois cantos estão fechados quando as coordenadas x e y de uma linha são alteradas. Para obter o código fonte de trabalho e uma demonstração interativa do produto concluído, consulte http://ashblue.github.io/javascript-pathfinding/
fonte
Respostas:
Eric Lippert escreveu uma excelente série sobre a geração de linha de visão em C # com Shadow Casting em uma grade plana retangular.
Entre outras questões, Eric lidou com várias perguntas que devem ser respondidas sobre os requisitos da linha de visão, que fornecem resultados diferentes e exemplos de alguns resultados diferentes. Um dos artigos trata em profundidade de uma circunstância "olhando ao virar da esquina" que ocorreu em uma versão inicial de seu algoritmo.
Adaptei o algoritmo de Eric a uma grade hexagonal aqui e o usei com sucesso em grandes grades hexagonais (> 400 x 700) com um amplo raio de visibilidade (> 60 hexágonos). Essa implementação calcula e exibe o campo de visão completo o mais rápido possível, usando uma única CPU i7. Isso certamente é rápido o suficiente para qualquer uso que eu espere colocar.
Atualização - Linha de visão com elevação: a
implementação da grade hexadecimal vinculada acima calcula a linha de visão com elevação, não apenas obstáculos. As notas da documentação também discutem uma decisão adicional que deve ser tomada com relação aos cálculos de elevação: A altura do alvo e a altura do observador. A seleção padrão é tornar os dois iguais, o que cria um campo de visão simétrico, mas o solo para o solo e os olhos do observador para o solo também podem ser selecionados. (O código é Open Source sob licença MIT)
fonte
E se, para o cálculo do LOS, você tiver uma grade separada de "maior resolução" que preencha as lacunas dos cantos. Eu estava pensando algo assim:
A esquerda é a seção original do bloco de 4 quadrados.
O certo é a versão "alta resolução", pois você pode ver que cada quadrado original foi subdividido em quadrantes e um dos cantos foi preenchido. Não sei ao certo o algoritmo para gerar isso, mas pode ser pré-calculado do mapa atual.
Isso significa que o espaço de coordenadas é quadruplicado, mas não imagino que seja um problema de desempenho significativo.
fonte
0.5
para células de alta resolução a serem preenchidas ou não. Assim, o uso de uma grade de alta resolução me parece bastante hacky.