How to find planets to colonize

I’ve been working on making the Beserkers play more efficiently and one area that I’ve been focusing on is colonization. Determining which planet to colonize is normally a easy process for a human player. Do a scan. See if you like the planet then set a TaskForce to move there, easy right?
Having the AI make those same determinations is not always as easy. Since the player can not see the entire galaxy map, shouldn’t the AI be limited as well? Players have the expectation that the AI will play fair or as close a normal player would play.

I been investigating ways to find planets (or targets) that would make the AI easier to program. Currently I’m using a graph with all the planets as nodes with the distances between the planets as edges. This approach works, however is very slow as each planet the AI owns has to seed the graph in order to find the next planet or target. I’ve tried to save the graph in the database, but that doesn’t appear to help.

So, my investigation has lead me to exploring new options for finding planets around the current planet. A common way to do this is to use the A* pathfinding algorithm. Here are a few reference sites (Policy Almanac’s AStar Tutorial and Amit’s AStar Intoduction). Now those explain very well how to find the path to the target, when you know what the target is. What if you don’t?

Normally the A* will find the shortest path to the target, selecting a path that will move around any obstacles in the way. In the case of Beserkers, the galaxy map doesn’t have obstacles (at least at this time), and perhaps the only worthy ‘target’ would be the player’s homeworld. Granted eventually this should be the target, but the AI needs to explore to find it first!

I’m thinking of using the A* to find planets that the AI should colonize. First, the AI must scan the planets to determine if the planet should be colonized. An advanced AI level might not want to colonize all the planets, only those that will support it’s goals. Once a planet has been determined to be colonizable, that planet could then be a target.

Another thing to consider is hidden movement. Should the AI always try to hide its movement from the player? In this case the planets are obstacles that will actually become the path to take! That’s an interesting thought. As a player, I’ve played game like VGAPlanets in the past, were I always wanted to hide my ship movements from other players. There would be times that I wouldn’t move the full distance possible in a turn, just to avoid being seen in space.

Future posts will detail more of the actual implementation, stay turned.