Gamasutra: The Art & Business of Making Gamesspacer
Designing AI Algorithms For Turn-Based Strategy Games
View All     RSS
July 29, 2014
arrowPress Releases
July 29, 2014
PR Newswire
View All





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++)
{

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.


Article Start Previous Page 3 of 3

Related Jobs

Big Fish Games
Big Fish Games — Seattle, Washington, United States
[07.29.14]

Game Engineer
Treyarch / Activision
Treyarch / Activision — Santa Monica, California, United States
[07.29.14]

Associate Cinematic Animator (temporary) - Treyarch
Treyarch / Activision
Treyarch / Activision — Santa Monica, California, United States
[07.29.14]

Senior Environment Concept Artist - Treyarch (temporary)
Wargaming.net
Wargaming.net — Chicago, Illinois, United States
[07.28.14]

User Experience Lead






Comments


James O'Neill
profile image
hi, i am currently working on a turnbased stratagy on mobile device. it has all the functionality that i would like apart from the ai aspects for a single player. this is the first ai document i have read that actualy made some sense to me. i would just like to ask a few questions. could you please elaborate on the modifyers for me? can these be completly random or are you calculating them based on the objectives of the game? should they be high or low numbers or does it even matter?



or is it possible to point me in the direction of some reading material that will expand on what you have talked about here.



as you can tell this is the first peice of ai programming i have ever had to do. i have never had a lesson in the subject because my course took me in a diffrent direction. saying this i still have part of my final project in the area so some help would be much appriciated.


none
 
Comment: