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.
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:
Respostas:
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.
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.
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.
fonte