In a game I'm developing for a client a key game concept involves moving around on a map. In this case the sizes and shapes and such of the various countries are irrelevant: moving from one country to an adjacent country counts as a single step.
I'm trying to figure out the best data structure for internally representing the connections between the countries. For a given country the game needs to know which countries are adjacent, both to know which ways the players can move as well as for allowing the game's AI to plot out routes, determining possible paths from one country to another. The AI also needs to evaluate how well-connected a country is, not just to its immediately-adjacent neighbors but to the neighbors of those countries, etc.
I've figured out a couple of possibilities but they seem ungainly and inefficient. Because the AI will need to calculate a bunch of possible routes in order to make good decisions about its movement, "inefficient" is highly problematic.
I suspect that this is a somewhat common CS puzzle and that there's a common solution, but I've not been able to find much by searching. Any suggestions are welcome.