시소당

Designing AI Algorithms For Turn-Based Strategy Games 3

Let's just take a quick look at our class hierarchy to make things clearer: 

We generate a PossibleAssignment object for each combination of "task doer" to task. However, we eliminate impossible combinations. For instance, an unarmed ship cannot carry out an attack task, nor can it do a task if it doesn't have enough fuel to reach it. This is how the code looks:

listAsset contains a list of all assets (for instance ships) 
for (n = 0; n < listTask.size(); n++)
{
for(f = 0; f < listAsset.size(); f++){
if (listAsset[f].isTaskSuitable(listTask[n])){
listPossAssignment.add(new PossibleAssignment(listTaskn]));
}
}
}

Next, we calculate assignment scoring for each PossibleAssignment and sort the list in order, highest scores first. And finally, in the last stage, we physically make the assignments. Because the list has been sorted, the most effective assignments occur first. Once an assignment is made the task doer is marked as busy and also the task is marked as assigned, preventing double assignments.

Here is part of the code:

for (n = 0; n < listPossAssignment.size();n++) 
{ 
listPossAssignment[n].assign(); 
} 
public void PossibleAssignment::assign() 
{ 
if (task.isAssigned()) return; 
possibleTaskDoer.assign(this); 
} 
public void Ship::assign(PossibleAssignment possAssign) { 
if (task != null) return; 
task = possAssign.getTask(); 
possAssign.getTask().assign(this); 
}

Reusing The Algorithm For Planet Production Assignment

The AI should manufacture new star ships if there are any leftover tasks that couldn't be taken care of by the existing fleet. For example, if we have spotted an enemy ship and there are no available warships to attack, then we need to build a new warship. Similarly, if there is a habitable planet and no available colonizers, then we need to build a new colonizer.

In fact, the build priorities for production queues are exactly the same as the task priorities for star ships. As you can see in the class diagram, both the classes Ship and Planet are derived from SpaceObject, so they both can be used in the same algorithm with little modification. This is a good example of code reuse in object oriented design.

The below diagram shows this in action:

Keeping Things Simple: Discarding Old Tasks

As this is a turn based game, at the start of each new turn all the tasks from the last turn become out-of-date. For instance, that enemy frigate that your destroyer was about to attack could suddenly retreat, or you could discover - to your horror - that the planet you were about to colonize has already been occupied by the enemy.

The easiest thing to do is just discard all tasks and call the resource assignment routine at the start of each turn. This may seem inefficient, because not all tasks need to be updated, however it does makes the AI code considerably less complicated, as you don't need to maintain tasks from previous turns.

Keeping the code uncomplicated is especially important in the case of AI algorithms, because these have a tendency grow overly complex very quickly, making debugging and maintenance very difficult. As well as that, all optimization tasks should be done at the final stage, after the algorithm has been completely finished, and then only if there is real evidence that the algorithm is to slow in the first place.

Mid-turn Surprises

During the course of our turn one of our ships may discover a new enemy colony, or ship. We could just assign a new attack task to the ship, but that would cause problems if it already had an existing task that was important. Again, the simplest and most fool-proof thing to do is just run the resource allocation routine again, as this guarantees the most optimal resource assignment.

Conclusion: How Does The Algorithm Work In Real Life?

This AI algorithm was designed during the development of a 4x strategy game (as you may have guessed from the example). In practice one got the impression that there was some sort of real intelligence behind the control of the enemy fleet.

Ships would change tactics unexpectedly. If an enemy ship ran out of ammo, it would suddenly break off battle and go back to base to re-arm. If it didn't have enough fuel to make it to base, then it would try to explore uncharted territory (the only useful task left). As new ships came out of the shipyards, the orders could change for the whole fleet. Some ships would return for repair and leave the fresh warships take up the attack.

Basically the algorithm provides good "bang for buck" ratio, a fairly uncomplicated algorithm that's easy to implement and debug, but yet provides a challenging AI opponent.

Even though, the algorithm was designed for one specific type of game it should be easily adaptable to other types of strategy game.