Localização de caminhos entre vários mapas

7

Estou interessado em encontrar caminhos entre vários mapas - podem ser mapas internos / externos, diferentes níveis em um edifício, etc., mas a principal restrição é a existência de um (ou mais) pontos de entrada / saída entre os diferentes mapas. Procurei e não consegui encontrar boas soluções, mas conheço vários jogos que usam sistemas semelhantes.

Eu encontrei este artigo - Descobrimento hierárquico do caminho mais curto aplicado ao planejamento de rotas para usuários de cadeira de rodas que parece abordar um problema semelhante, mas é puramente teórico.

Alguém fez algo semelhante com alguma experiência que eles poderiam compartilhar, ou com algumas dicas?

path-finding Martyn
fonte
Não vou dar uma resposta, já que nunca tive que implementar um caso que torne essa afirmação especulativa, mas duvido que exista uma solução além da óbvia que você precisa carregar seus nós, mesmo em mapas que ainda não foram carregados (o que não deve causar problemas, pois os dados do ponto de passagem ou da malha de navegação são talvez alguns kilobytes, mesmo para mapas grandes). Sem os nós, não há informações que seus algoritmos possam usar. Fora isso, deve ser bem simples - carregue todos os gráficos e conecte-os nos pontos de cruzamento (portas etc.). edit: oh e +1
TravisG 12/08
Concordei com isso - eu não acho que o problema é carregar os nós - é mais um pouco mais inteligente sobre como os diferentes mapas estão juntos. Como você diz, talvez seja um caso simples de usar um algoritmo padrão (A *?), Carregando todos os mapas em questão e depois conectando-os artificialmente. Se houvesse mais de dois níveis múltiplos, talvez eu devesse usar dois conjuntos de localização de caminhos, pois provavelmente não precisarei de todo o caminho - apenas o caminho fora do mapa atual?
Martyn
Exatamente. Provavelmente é mais rápido se você representar um "mapa" (o prédio ou o que o seu A * precisa encontrar) como um grande nó até que sua IA realmente esteja na frente dele, encontre o caminho mais curto em direção a esse grande nó e, depois que você carregamos o gráfico inteiro desse submapa e calculamos o caminho mais preciso. Calcular tudo de uma só vez no começo é um desperdício, já que muita coisa pode acontecer entre esse cálculo e sua IA se movendo para lá.
TravisG 12/08

Respostas:

5

Eu fiz algo parecido há vários anos para uma demonstração de maquete do clone "Jagged Alliance", com tema de cyberpunk, que deveria ter grandes mapas cheios de arranha-céus. Foi uma ideia estúpida, aparentemente os mapas para combate tático devem ser arrumados e facilmente compreensíveis :)

Para ter um caminho mais rápido, um mapa global foi dividido em várias áreas discretas em forma de quadrado. Depois de termos critérios para as áreas, é hora de encontrar possíveis "entradas" entre cada par de áreas adjacentes. "Entrada" é um ponto de transição que mostra que este agente pode entrar nesta área neste momento.

No seu exemplo com a construção de vários andares, cada andar seria uma área com bordas definidas pelo piso, teto e paredes externas; e vários buracos na parede ou no chão, ou escadas seriam entradas, poderia haver muitos deles. Portanto, as entradas basicamente vinculam nós de caminho de uma área para nós de caminho na outra área.

Depois de identificar as entradas, você precisará encontrar todas as maneiras possíveis de percorrer cada área, resultando em um "mapa das entradas da área para as entradas da área adjacente", com as bordas entre as entradas mostrando o comprimento desse caminho pela área.

Se tudo der certo, o seu agente no 1º andar poderá encontrar rapidamente o caminho para a caixa especial no 4º andar. Talvez algo semelhante possa ser usado no seu problema de vários mapas, então espero que ajude.

EnoughTea
fonte
1

Acredito que você esteja procurando por uma estrela hierárquica de localização de caminhos, como descrito aqui:

HPA- *

Pieter Geerkens
fonte