Author: by Gary Chambers

[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.

Dynamic Targets

Up until this point, the AITarget network had been static; it had been generated once at the start of the level and remained that way for the entire match, but this way no longer adequate – we needed a way for targets to move, and to appear and disappear from the network during the game.

At first we tried to manually link new targets (or re-link moving targets) to the other nearby AITargets, but this proved unreliable and in the end we settled with simply regenerating the network whenever an AITarget was changed, added or removed.

There were concerns that this might cause an unacceptable hit to performance, but after a little optimisation these fears proved to be unfounded, and this method was far more reliable as it was the same function that generated the network originally.

The AI was now able to capture power-ups (and even use them fairly well after some simple rules governing the use of each specific power-up were added -- issues involving the ‘accidental' nuking of an ally's Spawn Points were quickly resolved) and could now correctly play the Capture the Statue mode. The biggest challenge was yet to come, though.

Storm the Beach

One of the earlier game modes that was planned, but scrapped after we couldn't get it to work, made a sudden resurgence after some inspiration from the development team. It was called Assault, and was based on the idea of the beach landing scene in Saving Private Ryan – waves of men storming a heavily fortified enemy base.

On each map is a massive WMD set to go off after a certain amount of time, wiping out the attacking force (and conveniently leaving the defending team untouched), and the attackers are tasked with disarming it by capturing various points across the map. Obstacles such as walls, laser fences and gun turrets blocked the attacker advance, and would have to be bypassed in order to get to the objective. And there-in lay the problem.

With the current system, there was no way for us to tell the AI that it had to send Darwinians to a bank of Solar Panels in order to shut off a laser fence before trying to rush a bank of gun turrets. In fact, there was no way for us to tell it to do anything in any kind of order at all, and no simple fix was going to change that.

After a little brainstorming, we came up with a flexible objective system. Each specific goal on the map would be given an associated Objective, and each objective would be linked with a number of Markers that pointed out the specifics of that objective.

For example, the first objective on a number of maps is to capture a number of Solar Panels that are providing power to a Laser Fence, in order to lower the fence so that you can advance onwards. So the first Objective item on the map would have (for example) four markers associated with it, each one placed on top of one of these Solar Panels.

These markers would then manipulate the AITarget network, giving nearby targets a high priority so that the attacking army would march directly towards it. Once each one of these Solar Panels belonged to the attacking team at the same time, the objective would become complete, and the next Objective item would become active.

Objectives also work for the defending team, although instead of telling the AI which targets need attacking next, they specify where the defenders should fall back to. So once the aforementioned Solar Panels had been captured, the defending AI's objectives would tell it to abandon the Solar Panels, and fall back to the choke point at the recently lowered Laser Fence.

Objective Markers

The Objective Markers were also made context sensitive, and given a number of options. So if there was a marker in an open space, the objective for that specific marker would be to clear out the nearby area of enemy Darwinians. If the marker was placed on top of a Gun Turret, the objective would be to capture or destroy the Gun Turret.

They could also be flagged as pick-up/drop-off points for Armour units (fast moving Armoured Personnel Carriers that can ferry up to 100 Darwinians across the oceans between islands), allowing the AI to safely drop off groups of Darwinians at a sufficient distance from dangerous Gun Turrets, or giving them a single point to ease pick-ups.

A similar setup is also used for the Rocket Riot game mode, where teams have to capture groups of Solar Panels in order to power fuel pumps, to supply fuel to a rocket which must then be boarded and launched.

The result is a system which allows the AI to complete objectives in a linear order, even if they aren't placed in a linear order on the actual map.

Conclusion

The entire AI system in Darwinia+ is one that has evolved over the course of its seven-plus years of development (work on the first version of Darwinia started in 2002), instead of a system that was designed with a final end goal in mind. The result is a system that is flexible, and works, but far from perfect.

The problem of creating an AI that manages hundreds of individual units divided up into a dozen or more lose combat groups, whilst being challenging to play against without breaking the game rules (the AI absolutely cannot do anything the player can't) was certainly a challenge, but it's one that I think we have ended up managing quite well.