Localização de caminhos em uma superfície planetária irregular

16

Minha pergunta é qual seria a melhor abordagem para encontrar caminhos em uma superfície planetária irregular?


Informações básicas

Eu criei um planeta a partir do deslocamento mapeando 6 planos projetados em esfera. Os planos inicialmente formaram um cubo antes de serem projetados em forma de esfera.

insira a descrição da imagem aqui

Gostaria de saber se é possível usar cada "face do cubo projetada em esfera" como grades e usar um algoritmo A * simples para encontrar a melhor rota possível, também gostaria que a altura do deslocamento fosse levada em consideração para que o caminho evitasse escalar montanhas etc (acho que isso seria apenas uma heurística dentro do algoritmo A *). Outra consideração é que eu consegui o movimento planetário utilizando o mecanismo de física do Unity3d, aplicando a gravidade no centro do planeta. Minha solução proposta exigiria que o movimento dos agentes fosse controlado independentemente da física gravitacional?

Para ajudar a articular melhor minha pergunta, este é meu corpo planetário atual:

insira a descrição da imagem aqui

Caius Eugene
fonte
2
Você pode estar interessado neste vídeo da Aniquilação Planetária. Eles parecem estar fazendo o mesmo que você envolve o mundo a partir de um cubo e encontra o caminho ao redor dele. Não é realmente uma resposta, mas você pode ver que eles estão usando A * junto com outras estratégias para otimizar a localização de caminhos em uma esfera. O bit de localização do caminho começa às 24:30 .
MichaelHouse
@ Byte56 Obrigado por este link, uma abordagem realmente interessante ao custo, mal posso esperar para ver esse jogo quando terminar!
Caius Eugene

Respostas:

12

Parece que você já respondeu sua própria pergunta. A * é provavelmente a melhor abordagem. Sim, é claro que pode ser usado da maneira que você descreve, incluindo o uso de informações de altura para evitar montanhas. Contanto que você possa acessar informações sobre qualquer grade na superfície do seu mundo, não há motivo para não usá-las na heurística A *.

Finalmente, você está confundindo a localização do caminho com o caminho a seguir no final da sua pergunta. A descoberta de caminhos não se importa com a gravidade, a menos que você a adicione como heurística e, como você está na superfície de um planeta, a gravidade será essencialmente a mesma em toda a superfície. Muitos jogos têm gravidade junto com o movimento, não vejo razão para que você não consiga.

Basicamente, queremos mapear o vermelho para o azul, para ser o mesmo em uma esfera e em um cubo.

insira a descrição da imagem aqui

Como A * está frequentemente recebendo vizinhos para seu nó atual, você pode criar facilmente um conjunto de funções para obter nós adjacentes. Por exemplo, getXPlus(), getXMinus(), getZPlus()e assim por diante. Essas funções pegam o nó atual e retornam o nó na direção especificada pelo nome da função.

Na maioria das vezes, essas funções podem apenas incrementar um valor e, no entanto, nas bordas, isso muda.

Você deseja mapear a superfície do seu cubo para um sistema de coordenadas 2D. Como você decide, eles não precisam se alinhar, apenas dê a cada espaço da grade uma coordenada X, Y exclusiva.

Agora, quando estiver em uma aresta, e obtendo o espaço da grade adjacente, não será necessariamente apenas incrementar as coordenadas. Temos que descobrir para qual face estamos nos movendo e mudar para as coordenadas dessa face.

Por exemplo, obter a coordenada XPlus aqui alterará as coordenadas X e Y porque estamos mudando para um novo espaço de grade em uma nova face. A linha verde representa uma aresta entre duas faces.

insira a descrição da imagem aqui

Agora, essas são apenas coordenadas globais; pode ser mais fácil usar um sistema de coordenadas local interno, com uma terceira dimensão que representa a face do cubo em que você está atualmente.

De qualquer forma, você precisa ter uma coordenada exclusiva para cada espaço da grade na face do cubo. A travessia entre eles dependerá de como você implementa o sistema de coordenadas. Você também precisa saber onde essa coordenada é mapeada para a superfície da esfera.

Tudo isso deve ser abstraído para que você nem saiba.

MichaelHouse
fonte
Felicidades pela resposta. Acho que estou lutando com cada avião sendo uma grade isolada. Você tem alguma sugestão (ou leitura adicional) sobre como lidar com as costuras, acho que estarei desdobrando matematicamente meu "cubo", combinando todas as grades e calculando o caminho usando esse conjunto de dados?
Caio Eugene
Realmente, são apenas as arestas que você precisa se preocupar. Isso é facilmente resolvido por uma função de invólucro (envolvendo seu cubo em uma função de invólucro, que envolve seu mundo ...). Você pode abstrair o cubo em uma superfície plana que envolva. Crie funções para obter o espaço da grade adjacente, getXPlus () obterá a grade na direção do XPlus, não importa se está no limite entre as faces, a função apenas alternará as faces e retornará as informações apropriadas da grade.
MichaelHouse
A única imprecisão na localização do caminho no cubo dobrado é que os vértices são inclinados e, portanto, as arestas têm comprimentos diferentes. É possível que isso não faça uma diferença perceptível nos caminhos resultantes, caso contrário você pode simplesmente levar em consideração os comprimentos.
danijar
1
O importante a entender aqui é que A * não opera necessariamente em um avião; opera em um gráfico. Embora dentro de cada face do cubo, os nós estejam organizados e conectados em uma grade, também existem conexões de nós nas bordas do cubo.
precisa saber é o seguinte
1
@ Byte56 Obrigado pela ótima resposta, eu comecei a implantar uma solução, no entanto, encontrei um obstáculo. Talvez eu tenha entendido errado. Eu postei uma pergunta sobre a stackoverflow como eu senti o seu mais de um math / programação problema stackoverflow.com/questions/16089074/...
Caio Eugene