Structure de données pour représenter les connexions entre les pays sur une carte

9

Dans un jeu que je développe pour un client, un concept de jeu clé consiste à se déplacer sur une carte. Dans ce cas, les tailles et les formes et celles des différents pays ne sont pas pertinentes: passer d'un pays à un pays adjacent compte comme une seule étape.

J'essaie de trouver la meilleure structure de données pour représenter en interne les connexions entre les pays. Pour un pays donné, le jeu doit savoir quels pays sont adjacents, à la fois pour savoir de quelle manière les joueurs peuvent se déplacer et pour permettre à l'IA du jeu de tracer des itinéraires, en déterminant les chemins possibles d'un pays à l'autre. L'IA doit également évaluer dans quelle mesure un pays est bien connecté, non seulement à ses voisins immédiatement adjacents, mais aussi aux voisins de ces pays, etc.

J'ai trouvé quelques possibilités mais elles semblent disgracieuses et inefficaces. Parce que l'IA devra calculer un tas d'itinéraires possibles afin de prendre de bonnes décisions concernant son mouvement, "inefficace" est très problématique.

Je soupçonne qu'il s'agit d'un casse-tête CS quelque peu courant et qu'il existe une solution commune, mais je n'ai pas pu trouver grand-chose en cherchant. Toutes suggestions sont les bienvenues.

maps efficiency Matthew Frederick
la source
Si je devais le demander sur GameDev.StackExchange, faites le moi savoir. Je demande ici parce que je suis sûr que ce genre de chose est nécessaire pour toutes sortes de problèmes de développement et je n'ai pas besoin d'aide avec le côté "jeu", en soi, juste la partie planification d'itinéraire.
Matthew Frederick
Vous avez besoin d'un graphique ou d'une matrice de connectivité (ce qui est pratique, car la fermeture est facile à calculer). Vous avez peut-être besoin des deux. Recherches-les.
2
Jetez un œil aux structures et algorithmes de données des graphes: en.wikipedia.org/wiki/Graph_%28data_structure%29
1
Cela ne me regarde pas comme un sujet. Cela devrait être sur GameDev ou Stack Overflow, car c'est un sujet trop objectif pour ici.

Réponses:

6

Certainement un graphique. Vérifiez ici la théorie des graphes , en gros vous avez des nœuds et des arêtes. Un nœud peut contenir 0 ou plusieurs arêtes vers d'autres nœuds.

Il existe de nombreux algorithmes pour calculer le chemin le plus court (sauts ou distance), vérifier les cicles (plus d'une façon de se rejoindre), etc.

Maintenant, pour pouvoir mettre en œuvre des solutions efficaces, c'est un peu plus complexe, mais comme toujours, il existe des moyens.


la source
Excellent merci. Avez-vous des suggestions pour savoir où trouver de tels algorithmes? Je n'ai pas tellement besoin du chemin le plus court, mais des choses comme la vérification des cercles, etc. seraient très utiles.
Matthew Frederick
2

Comme déjà mentionné, vous auriez besoin d'un graphique représentant toutes les connexions possibles entre les pays. Chaque connexion détiendrait également la distance entre deux pays.

Ensuite, un algorithme de recherche de chemin comme A * peut être utilisé pour déterminer le chemin le plus court entre deux pays.

Il y a aussi de bons livres sur le jeu ai: Game AI par exemple par Mat Buckland http://www.ai-junkie.com/books/toc_pgaibe.html

ou la série AI Game Programming Wisdom. http://www.aiwisdom.com/ Le premier livre contient plusieurs chapitres sur la recherche de chemin.

Stephen
la source
Excellent, merci pour les pointeurs de livres. Il semble y avoir une tonne de livres sur l'IA et les recommandations personnelles sont bien meilleures que les résultats généraux que j'ai obtenus en recherchant.
Matthew Frederick