Estrutura de dados para representar conexões entre países em um mapa

9

Em um jogo que estou desenvolvendo para um cliente, um conceito-chave de jogo envolve mover-se em um mapa. Nesse caso, os tamanhos e as formas e os de vários países são irrelevantes: a mudança de um país para um país adjacente conta como uma única etapa.

Estou tentando descobrir a melhor estrutura de dados para representar internamente as conexões entre os países. Para um determinado país, o jogo precisa saber quais países são adjacentes, para saber de que maneira os jogadores podem se mover e também para permitir que a IA do jogo traçar rotas, determinando possíveis caminhos de um país para outro. A AI também precisa avaliar o quão bem conectado um país está, não apenas com seus vizinhos imediatamente adjacentes, mas também com os vizinhos desses países, etc.

Eu descobri algumas possibilidades, mas elas parecem desajeitadas e ineficientes. Como a IA precisará calcular várias rotas possíveis para tomar boas decisões sobre seu movimento, "ineficiente" é altamente problemático.

Suspeito que esse seja um quebra-cabeça comum do CS e que exista uma solução comum, mas não consegui encontrar muita coisa pesquisando. Todas as sugestões são bem-vindas.

maps efficiency Matthew Frederick
fonte
Se eu perguntar isso no GameDev.StackExchange, é só me avisar. Estou perguntando aqui, porque tenho certeza de que esse tipo de coisa é necessária para todos os tipos de problemas de desenvolvimento e não preciso de ajuda com o lado "jogo", por si só, apenas a parte do planejamento de rotas.
21411 Matthew
Você precisa de um gráfico ou de uma matriz de conectividade (o que é útil, porque o fechamento é fácil de calcular). Talvez você precise dos dois. Procure-os.
2
Ter um olhar para as estruturas de dados do gráfico e algoritmos: en.wikipedia.org/wiki/Graph_%28data_structure%29
11
Isso não parece tópico para mim. Ele deve estar no GameDev ou no Stack Overflow, pois é um tópico muito objetivo para aqui.

Respostas:

6

Definitivamente um gráfico. Confira aqui a Teoria dos Gráficos , basicamente você tem nós e arestas. Um nó pode conter 0 ou mais arestas para outros nós.

Existem muitos algoritmos para calcular o caminho mais curto (saltos ou distância), verificar se há ciclos (mais de uma maneira de alcançar um eu), etc.

Agora, para poder implementar soluções eficientes, isso é um pouco mais complexo, mas, como sempre, existem maneiras.


fonte
Excelente, obrigado. Você tem alguma sugestão de onde encontrar esses algoritmos? Não preciso tanto do caminho mais curto, mas coisas como procurar círculos etc. seriam muito úteis.
Matthew Frederick
2

Como já mencionado, você precisaria de um gráfico representando todas as conexões possíveis entre países. Cada conexão também manteria a distância entre dois países.

Em seguida, um algoritmo de localização de caminhos como A * pode ser usado para determinar o caminho mais curto entre dois países.

Existem também alguns bons livros sobre o jogo ai: Game AI, por exemplo, por Mat Buckland http://www.ai-junkie.com/books/toc_pgaibe.html

ou a série AI Game Programming Wisdom. http://www.aiwisdom.com/ O primeiro livro possui vários capítulos sobre busca de caminhos.

Stephen
fonte
Excelente, obrigado pelos ponteiros do livro. Parece haver uma tonelada de livros de IA e recomendações pessoais são muito melhores do que os amplos resultados que tenho obtido com a pesquisa.
Matthew Frederick