Existem duas maneiras de abordar esta questão que eu posso ver. Primeiro, se você simplesmente deseja encontrar uma maneira de orientar, basta implementar o pathfinding ( acho isso bastante útil ). Isso seria o fim disso (e é a resposta prática correta para essa pergunta), mas acho que você está mais curioso sobre uma solução matemática para o seu problema.
Para resolver isso, vejamos um problema equivalente. Pegue uma fatia 2D da sua cena "à frente" do piloto de um avião que seja normal ao vetor original. O que você obterá é um ponto que representa seu vetor original e uma série de elipses que são as projeções 2D dos seus cones de oclusão. Agora, o que você quer fazer é encontrar o ponto mais próximo ao seu ponto original (vamos chamá-lo P
) que fica no exterior de elipses não sobrepostas. Acontece que este é um problema bastante difícil de resolver. Existem 3 etapas:
- Descobrir os pontos de interseção de todas as suas elipses
- Encontre todos os orifícios na união de todas as suas elipses
- Descobrir o ponto mais próximo de
P
todas as suas elipses fora da união (que pode estar dentro de um buraco)
Tudo bem, tudo isso requer multiplicadores Lagrange e verificação de ângulo e algumas outras coisas realmente complicadas para resolver. Vejamos outras opções. Se transformarmos nosso problema em espaço angular, veremos que o que realmente queremos é encontrar a distância mínima entre um ponto e vários círculos projetados na superfície de uma esfera. Na geometria diferencial, isso geralmente é chamado de 2 esferas e é útil aqui. Então, primeiro, precisamos encontrar a distância entre dois pontos na superfície da esfera, que usaremos a métrica de 2 esferas para encontrar. Felizmente, é bem fácil: ds^2 = (R^2)*(dth^2) + (R^2)*(sin(th)^2)*(dph^2)
onde mantemos R
constantes como o raio da nossa 2-esfera projetada no espaço 3. Vindo da física, considero th
o ângulo do positivo z
e ph
o ângulo do positivo x
coms
sendo a distância.
O que isso faz? Ele nos permite remover o uso de multiplicadores de Lagrange para minimizar a distância e nos permite trabalhar em coordenadas "nativas" (já que definimos nossos cones em termos de um ângulo de oclusão). Então agora precisamos encontrar o raio de nossas projeções de cone. Vamos pegar um cone por enquanto e chamar o ângulo que o define a
. O raio da projeção é então simplesmente R*a
. Isso foi fácil - que outra quantidade precisamos saber sobre os cones? Precisamos conhecer o centro da projeção, que é definido pelo vetor de aparência do ator. Primeiro, convertemos x
, y
e z
em coordenadas esféricas, onde sabemos que estamos à distância R
, e resolvemos th
e ph
, o que podemos fazer simplesmente conectando nossas fórmulas de conversão:th = acos(z/R)
e ph = atan2(y/x)
(use atan2
aqui para explicar as ambigências de quadrante do arco-tangente). O processo é o mesmo para encontrar a posição do seu vetor original em coordenadas esféricas.
Portanto, o problema foi simplificado. No entanto, o problema ainda é bastante difícil de resolver, mas agora você só precisa se preocupar com círculos e pontos, em vez de elipses e pontos ou ângulos e vetores. O restante do processo é bastante processual. Você precisa essencialmente encontrar uma área delimitadora formada por seus círculos, para a qual existem várias soluções. Vou apresentar um método que pode não ser o melhor, mas funcionará.
Primeiro, eu compararia a soma dos raios de todos os pares de círculos e a distância entre os centros; depois, se eles somarem maiores que a distância do centro, os definiriam iguais e resolveriam th
eph
para encontrar os cruzamentos. Você sabe que cada par de interseções descreve "ângulos proibidos" para o círculo em questão, que você armazenaria como uma matriz de ângulos de ponto de interseção (a partir do centro do círculo) para cada círculo que cruza esse - é importante que você precise " mesclar "todos os intervalos que se sobrepõem à medida que você os adiciona à matriz para que a próxima parte funcione corretamente. Em seguida, você encontra o ponto mais próximo na borda do círculo ao ponto original (que é tão simples quanto desenhar uma linha através do ponto central do círculo e do ponto original e, em seguida, encontrar o local na linha no raio do círculo longe do centro). Em seguida, passe pela matriz armazenada e teste se esse ângulo está no intervalo de cada ângulo proibido. Nesse caso, selecione a aresta mais próxima. Esse é o ponto mais próximo do exterior descrito dentro deste círculo. Repita o processo para todos os círculos (alguma otimização pode ser feita no processo de seleção - você realmente não precisa calcular isso para cada círculo). Agora compare todas as distâncias mais curtas, encontre a menor e essa é a sua resposta, descrita nos ângulosth
e ph
. Lembre-se de que a distância é descrita com a métrica de 2 esferas ao executar esse cálculo. Como você não se importa com a esfera em que tudo isso está ligado, apenas com os ângulos, é possível definir R=1
e fazer esses cálculos na esfera unitária.
Esta é a maneira mais simples de pensar em fazer isso. Não sei se é a maneira mais simples, mas funcionaria muito bem. Praticamente para um jogo, no entanto, você apenas deseja implementar o pathfinding.