Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Gamasutra: The Art & Business of Making Gamesspacer
Designing AI Algorithms For Turn-Based Strategy Games
View All     RSS
January 16, 2021
arrowPress Releases
January 16, 2021
Games Press
View All     RSS

If you enjoy reading this site, you might also want to check out these UBM Tech sites:


Designing AI Algorithms For Turn-Based Strategy Games

July 27, 2007 Article Start Previous Page 3 of 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++)



public void PossibleAssignment::assign()

if (task.isAssigned()) return;

public void Ship::assign(PossibleAssignment possAssign) {
if (task != null) return;
task = possAssign.getTask();

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.

Article Start Previous Page 3 of 3

Related Jobs

Square Enix, Inc.
Square Enix, Inc. — El Segundo, California, United States

Senior Web Developer
Gunfire Games
Gunfire Games — Austin, Texas, United States

Senior Boss Designer
innogames — Hamburg, Germany

Game Designer - Forge of Empires
Airship Syndicate
Airship Syndicate — Austin, Texas, United States

Mid to Senior Worldbuilder - Unreal Engine

Loading Comments

loader image