[In a detailed AI-focused postmortem, Introversion's Gary Chambers discusses the challenges and successes of creating the AI system for Darwinia and its multiplayer counterpart Multiwinia.]

In this article, I want to discuss the various systems that drive the AI in Darwinia+, and explore how they have evolved over the course of the game's development.

For those not aware, Darwinia+ is actually a package containing two games -- Darwinia, which was released for the PC in early 2005, and Multiwinia, which was released in 2008 -- due to be released on the Xbox 360 via Xbox Live later this year. As a result, this article will largely be covering the PC development that occurred on Multiwinia between 2005 and 2008.

In the Beginning

When work first began on Multiwinia, it was intended to be little more than a multiplayer addition to Darwinia, and as a result of this we were content to simply make use of the existing AI structure that was already there.

This consisted of a single AI entity which moved Darwinians in groups between two points on a network of nodes called AITargets. These AITargets were hand placed in the level, and automatically linked to each other depending on their distance apart, and the steepness of the terrain. AITargets did not connect across mountains or terrain that had a steep angle at some point along the line between two points.

The AI would then assign a priority to each of these AITargets based on the current activity at that point, with values ranging between 0.0 and 1.0. Sometimes the assigned priority would be a fixed value, for example, an unoccupied area would be given a priority of 0.95, to ensure that the AI sent Darwinians to capture it quickly, but in most other circumstances the priority would be determined by the average priority of all the adjacent nodes.

This way, priority values would propagate across the network of AITargets, allowing the AI to lead its idle Darwinians from a lower priority area to a high priority area, simply by sending them to the next node with the highest priority.

Introversion's Multiwinia

In order to stop large groups of Darwinians moving to a single point and then doing nothing (which could happen on islands fully controlled by that AI) an element of randomness was also introduced – every time the AI sent a group of Darwinians to the next node, there was a 25% chance that it would simply pick randomly from the list of adjacent nodes, rather than picking the highest priority.

For the most part, this system was sufficient for the original designs of Multiwinia, and indeed a very similar system is still used for the two simplest game modes, Domination and King of the Hill.

Changing Requirements

As the scope and complexity of Multiwinia increased, it soon became apparent that the existing AI was no longer sufficient to provide a player with a fun, challenging game. Even in Domination and King of the Hill, which simply involves capturing and holding points around the map -- the exact purpose for which the original AI was designed -- a number of problems arose.

In Darwinia, each of the levels in which this AI was actually used (enemy Darwinians only appear in 2 or 3 levels later in the game), the islands were small enough that each AITarget placed on the map represented an actual objective.

Maps in Multiwinia tend to have much more open area however, and so some AITargets had to be placed to serve as ‘connectors', simply filling open space in the network to allow the AI to properly navigate a level. The result of this was that groups of Darwinians would often be found standing around in the middle of nowhere, basically wasted.

This was solved by introducing the concept of ‘importance' to the AITarget. An AITarget is deemed important if it is placed near some other building of interest -- a Spawn Point, or a Hill zone in King of the Hill, for example -- and unimportant otherwise.

This simple solution solved a number of problems with the basic AI. When a group of Darwinians now arrived at an AITarget that was not important, they could simply continue straight on to the next target, and conversely, the AI knew to defend AITargets it already had control of if they were important.

This means that, not only did the AI stop leaving Darwinians milling around in the middle of nowhere, doing nothing, but because they are able to move straight over these unimportant targets, the AI was able to much more efficiently supply reinforcements to important targets that needed a boost.

Of course, this only helped the basic AI, and only on these simple game modes, and our requirements were soon about to change again.

Player Simulation

After running a number of test sessions with players outside of the company, it was decided that the AI should play the game in as close a manner to a human player as possible.

Players are able to create Officer units by promoting Darwinians, in order to set up standing orders so that they don't have to constantly move every group that spawns by hand -- a task which would quickly become overwhelming on larger maps, but something which would obviously never be an issue for an AI player.

So now, instead of directly moving its newly created Darwinians across the map, the AI would create an Officer outside the Spawn Point instead, and then tell that Officer to order the Darwinians to move to the relevant AITarget.

The net result is the same -- Darwinians are moved from A to B, based on the priorities of the AITarget network, but now the player is able to visualise the enemy's (or ally's, in a co-op game) actions in the same way as they would a human player.

As the game developed, the requirements placed on the AI grew beyond the scope of what could be accomplished with the current system. Temporary 'objectives' that would appear and disappear during the course of a match, such as power-up crates and deployable Gun Turrets, would be completely ignored.

Objectives which moved, such as the giant statues in Capture the Statue (a CTF-style game mode where groups of Darwinians must carry a heavy statue back to their base) would basically fall off of the AI's grid as soon as they began to move away from their start point. Again, the solution was simple, yet effective.