Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 9 down vote favorite

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.

share|improve this question
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
2  
Have a look at graph data structures and algorithms: en.wikipedia.org/wiki/Graph_%28data_structure%29 – FrustratedWithFormsDesigner Apr 1 '11 at 17:50
1  
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

migrated from programmers.stackexchange.com Apr 2 '11 at 2:32

3 Answers

up vote 13 down vote accepted

Sound like a Graph and a Shortest path Algorithm

share|improve this answer
up vote 6 down vote

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.

share|improve this answer
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
up vote 2 down vote

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.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.