# Data Structure to Represent Connections Between Countries on a Map

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.

-

## migrated from programmers.stackexchange.comApr 2 '11 at 2:32

This question came from our site for professional programmers interested in conceptual questions about software development.

If I should ask this on GameDev.StackExchange just let me know. I'm asking here because I'm sure this kind of thing is needed for all kinds of development problems and I don't need help with the "game" side of it, per se, just the route-planning part. – Matthew Frederick Apr 1 '11 at 17:44
You need either a graph or a connectivity matrix (which is handy, because closure is easy to compute). Perhaps you need both. Look them up. – Job Apr 1 '11 at 17:50
Have a look at graph data structures and algorithms: en.wikipedia.org/wiki/Graph_%28data_structure%29 – FrustratedWithFormsDesigner Apr 1 '11 at 17:50
This doesn't look on-topic to me. It should either be on GameDev or Stack Overflow, as it's too objective a topic for here. – David Thornley Apr 1 '11 at 17:54

Sound like a Graph and a Shortest path Algorithm

-

Definitly a Graph. Check it out here Graph Theory, basically you got nodes and edges. A node may contain 0 or more edges to other nodes.

There are lots of algorithms to calculate the shortest path (hops or distance) , check for cicles (more than one way to reach one self), etc.

Now, to be able to implement efficient solutions, that's a little more complex, but as always, there are ways.

-
Excellent, thank you. Do you have any suggestions for where to find such algorithms? I don't need shortest path so much, but things like checking for circles, etc. would be very handy. – Matthew Frederick Apr 2 '11 at 18:20

As already mentioned you would need a graph representing all possible connections between countries. Each connections would also hold the distance between two countries.

Then a path-finding algorithm like A* can be used to determine the shortest path between two countries.

There are also some good books about game ai: Game AI by example by Mat Buckland http://www.ai-junkie.com/books/toc_pgaibe.html

or the AI Game Programming Wisdom series. http://www.aiwisdom.com/ The first book has several chapters about pathfinding.

-
Excellent, thank you for the book pointers. There seem to be a ton of AI books and personal recommendations are much better than the broad results I've been getting from searching. – Matthew Frederick Apr 2 '11 at 18:22