Atualmente, estou escrevendo uma simulação 2D de IA, mas não tenho certeza de como verificar se a posição de um agente está dentro do campo de visão de outro.
Atualmente, meu particionamento mundial é simples particionamento de espaço celular (uma grade). Quero usar um triângulo para representar o campo de visão, mas como posso calcular as células que se cruzam com o triângulo?
Semelhante a esta imagem:
As áreas vermelhas são as células que quero calcular, verificando se o triângulo cruza essas células.
Desde já, obrigado.
EDITAR:
Apenas para aumentar a confusão (ou talvez até facilitar). Cada célula possui um vetor min e max, onde min é o canto inferior esquerdo e max é o canto superior direito.
collision-detection
intersection
Ray Dey
fonte
fonte
Respostas:
Calcule os três cantos do seu triângulo fov, gire-os para que estejam voltados para o caminho correto e faça um dos seguintes:
1) faça um teste de ponto no triângulo para todos os alvos em potencial
2) calcule a caixa delimitadora deste triângulo e faça um teste ponto a triângulo para todos os alvos em potencial nas células nessa caixa delimitadora - este será um código muito simples para depurar
Uma abordagem semelhante é usar um quadtree em vez de uma grade e fazer as interseções nele. Se o acesso ao bloco O (1) estiver acelerando, apenas o teste de todas as células nos limites do triângulo fov para triângulo deve ser tão rápido quanto instantâneo. Como você está olhando para outras opções, presumo que não, e que o O (1) está realmente tendo um enorme custo de perda de cache à medida que você troca seu cache. Obviamente, talvez você deva consultar as instruções de pré-busca para anotar sua caixa delimitadora com ...
3) 'rasterize' esse triângulo e verifique as células que ele 'pinta' - provavelmente o código mais eficiente, mas talvez apenas marginalmente, pois eu especularia que tudo é dominado por tempos de falha do cache e depende de quão complexas são suas células e quão ocupadas eles são.
Uma abordagem alternativa é renderizar o FOV em um bitmap fora da tela e ler o valor do pixel para cada um dos seus objetos; você não pode 'desmisturar tinta', mas com um número limitado de objetos e, escolhendo cuidadosamente sua tinta, pode deduzir quem viu quem. Essa abordagem é semelhante a quantos jogos funcionam no que o usuário clicou - eles desenham a cena fora da tela usando cores sólidas nas áreas atingidas. As GPUs são muito rápidas no preenchimento de triângulo ...
fonte
A solução canônica nos renderizadores de software (que devem executar exatamente esse algoritmo toda vez que rasterizam um triângulo) é, acredito, digitalizar o triângulo uma linha de pixels por vez. As bordas esquerda e direita de cada linha e calculadas andando pelas laterais do triângulo usando Bresenham e, em seguida, você preenche a linha entre elas.
Estou encobrindo muitos detalhes, mas essa é a idéia básica. Se você procurar "renderização de software" e "rasterização de triângulo", provavelmente encontrará mais alguns detalhes. Este é um problema bem resolvido. Sua placa de vídeo está fazendo isso milhões de vezes em um quadro.
Se você quer uma solução mais específico-roguelike, aqui está como eu implementado FOV na minha. Parece funcionar muito rapidamente. É essencialmente um lançador de sombras simples, trabalhando em octant de cada vez, digitalizando para fora do player.
fonte
Estou usando uma variação do algoritmo scanline para resolver exatamente o mesmo problema. Comecei classificando os três pontos do triângulo pela altura. Então, basicamente, verifico se duas arestas estão do lado esquerdo ou direito. Para o lado com duas arestas, é necessário marcar as linhas onde você altera a aresta que delimita suas linhas. Para o lado com uma borda, você sempre pode usar isso.
Então, para cada linha, eu sei quais são as duas arestas que a delimitam e posso calcular os limites superior e inferior na direção x. Parece bastante complicado, mas condensa-se a apenas algumas linhas de código. Certifique-se de lidar com o caso especial em que uma borda é completamente horizontal!
fonte
Que tal manter um intervalo de colunas para cada linha que está no triângulo? O que você pode fazer é definir a coluna min e max para cada linha em que cada ponto está e onde cada linha do triângulo cruza uma linha separadora de linha horizontal.
Resultado:
fonte
Há algum trabalho de algoritmo feito na comunidade roguelike que lida com FOV / LOS / iluminação em um mundo baseado em blocos.
Talvez você possa encontrar algo nesta página que possa ser usado para ajudar a resolver seu problema: http://roguebasin.roguelikedevelopment.org/index.php?title=Field_of_Vision
Especificamente "FOV permissivo" pode ser o mais aplicável à sua situação.
fonte