Methods for Combining Autonomous Steering Behaviours

“Autonomous Steering Behaviours”, as first defined by Craig Reynolds in his presentation at the 1999 Game Developer’s Conference, are a simple yet effective method of creating realistic movement in computer-controlled characters. As such, they are often considered an important part of “Game A.I.”, despite not really having any relation to traditional A.I. techniques.

Using Reynolds’ model, the movement behaviour of an autonomous character can be described using active verbs that represent certain desires:

• A homing missile seeks its target
• A police car pursues a fleeing criminal
• A hoard of orc minions follow their orc leader
• An outlaw evades the sheriff’s bullets
• A convict may hide from the prison warden
• etc. etc.

Although they represent a range of different movements, each of these behaviours can be implemented following the same basic pattern, which can be summarised as follows:

1. Determine the desired target location.
2. Calculate the desired velocity vector, which points from the character in the direction of the target,  truncated to the maximum allowed speed of the character (assuming that the character wants to reach the target location as quickly as possible)
3. Compare the desired velocity to the current velocity, and calculate the acceleration required as the difference between them.
4. Apply a steering force to the character, in the direction of the desired acceleration, truncated to the maximum allowed force produced by the character.

This is illustrated below, for the example of a car seeking a target (notice how the steering force is parallel to the vector of desired velocity – current velocity)

There are plenty of good online demonstrations of different individual steering behaviours (such as here or here), and, at some point, I’ll probably get round to writing up my own examples. However, for this post, I’m going to look at different methods to handle situations in which there may be two or more competing behaviours – you want to flee from an attacker but also avoid obstacles in your path, or you want to stay close to your teammates, but not so close that you’re stepping on their toes: how should we resolve these conflicting desires to come up with a single steering force in a given situation?

As an example for the methods discussed below, consider the steering forces shown in the following diagram generated by three different behaviours, named simply as A, B, and C, representing the vectors (1,4), (3,2), and (1,-2), respectively:

 

1. Priority Arbitration

Under this scheme, the various enabled steering behaviours are assigned a priority and, at any given time, only the behaviour with the highest priority is given control over the character’s movement.  Priorities can be set dynamically based on the current environment so that, for example, when a character’s health is low, the desire to seek for a health pack may have greater priority than the desire to steer for cover, but, at other times, the desire to steer into cover has greater priority and is therefore given control. To be more specific, arbitration should choose the highest priority non-zero steering behaviour. “Obstacle avoidance” behaviour, for example, might always be given top priority but only needs to produce a steering force in situations when a collision would otherwise occur. If no corrective action needs to be taken, obstacle avoidance produces zero force, and arbitration should continue to consider the next highest priority behaviour and so on.

For the example above, assuming that behaviour A has highest priority, the resulting steering force is therefore (1,4):

There are some limitations to this approach: if the “avoid collisions” behaviour only kicks in when it is given top priority, say, it’s probably at the point when the character is facing an imminent collision that could have been avoided earlier and more gracefully if that behaviour were allowed to have taken some slight corrective action a bit earlier (but it was never given priority to do so). Priority arbitration also does not allow for opportunistic behaviour so that, for example, when the current priority is to seek to a target, the character will not make a slight detour suggested by one of the other behaviours to pick up a great power-up along the way, which a human player would probably have done in the same situation.

 

2. Weighted Blending

In contrast to arbitration, “blending” involves considering all of the competing desires acting upon the character, weighting them, and adding them together to create a combined force suggesting the appropriate steering direction. This can result in smoother behaviour than arbitration, since every desire is considered at every step, rather than the character switching abruptly from one steering behaviour to the next. Weighted blending is often used in flocking behaviours, where the desires for separation, cohesion, and alignment with other members of the flock are blended together.

For the preceding example, if the behaviours were weighted (A:0.25, B:0.5, C:0.25), the resulting force would then (1*0.25 + 3*0.5 + 1*0.25 , 4*0.25 + 2*0.5 – 2*0.25 ) = (2, 1.5):

The problem with blending is that you can end up with a compromise that suits nobody. Suppose you were trying to seek towards a target, but evade an enemy that stands directly in the way. At some point, the sum of the weighted force assigned to these two actions would cancel each other out into an equilibrium, so that the character would remain motionless, torn between the desires to reach the goal but not wanting to get any closer to the enemy. Blending can also be computationally expensive, as every force must be calculated on every frame.

 

3. Prioritised Dithering

This approach combines elements of the above two, while also involving an element of random chance. Under prioritised dithering, the various behaviours are once again assigned a priority, but they are also given a probability, expressed as a value between 0 and 1. In any given step, a random number is generated between 0 and 1. If the probability assigned to the top priority behaviour exceeds the random number generated (and, when executed, the behaviour generates a non-zero force), then that behaviour is given control and no other behaviours are considered. Otherwise, if the probability of the top priority behaviour is less than the random number, or if the resulting action generated no force, then a new random number is generated and used to test against the probability of the next-highest priority behaviour being executed. This continues down the behaviours in descending order of priority, until a non-zero force is generated by some behaviour.

The result of the previous example, if we assume that behaviour A is not chosen by random selection, and then behaviour B is selected, is (3, 2):

This is an interesting approach, which solves some of the problems of the previous two. Because only one steering behaviour actually gets given control, it is relatively cheap on CPU, whilst still giving every behaviour some opportunity to influence movement at every step. However, tweaking the appropriate values of probability and priority for each behaviour can take some work.

 

4. Weighted Prioritised Truncated Sum

Apart from having a silly name, this is my favoured approach, as it is a nice balanced hybrid method that makes use of both weight and priority assigned to each behaviour. Once again, behaviours are considered in priority order, with the highest priority behaviour being considered first. Any steering force generated by this behaviour is multiplied by its assigned weight and added to a running total. Then, the total (weighted) force accumulated so far is compared to the maximum allowed force on the character. If the maximum allowed force has not yet been reached, the next highest priority behaviour is considered, the steering force it generates is weighted, and then this is added onto the cumulative total. And so on, until either all of the steering behaviours have been considered, or the total maximum steering force has been assigned, whichever occurs first. If at any point there is still some surplus steering force left, but not enough to allocate the whole of the desired steering force from the next highest-priority behaviour, the extra force is truncated and what can be accommodated is added to the total (hence the weighted prioritised truncated sum).

When applied to the example using the same weights as before, and, assuming that the maximum force is exceeded after the steering force from behaviour B has been applied, the result is (1*0.25 +  3*0.5, 4*0.25 + 2*0.5)  = (1.75, 2):

 

So there you have it – four different methods, producing four different results. They each have their own strengths and weaknesses, so there’s no “correct” answer, but it’s worth considering the different options available when deciding how to adjust an autonomous character’s movement behaviour.

Artificial Immune Systems and Adaptive Strategies in Game A.I.

A.I., perhaps unsurprisingly, often borrows inspiration, language, and models from the world of biology. Two common examples are Artificial Neural Networks (ANNs) – based on a model of the brain, and Genetic Algorithms (GAs) - based on a model of evolution.

There are plenty of case studies of these biologically-inspired systems being used to develop “intelligent” computer-controlled videogame characters, and there are implementation examples in many game AI textbooks. However, I’ve never heard of an example of a game that makes use of an Artificial Immune System (AIS), i.e. a system based on the structure and processes of the human immune system. In fact, I could barely find any material on it at all, save a few articles in academic journals.

I find this a bit surprising because I can imagine several scenarios in which, following an initial exposure to a player’s actions, an A.I. system could develop an “immunity” to further situations in which the player plays that same action, which I’ll attempt to describe here.

The Scenario : a Simple RTS

Consider a simple Real-Time Strategy game in which two players each build up an army containing a maximum of 60 units chosen from three different unit types. As is common, each unit type is strong against one of the other types, but weak against the other, as follows:

• Type A beats Type C, but is beaten by Type B (i.e. B > A > C)
• Type B beats Type A, but is beaten by Type C (i.e. C > B > A)
• Type C beats Type B, but is beaten by Type A (i.e. A > C > B)

Depending on your gaming preferences, you might prefer to substitute “A”, “B”, and “C” with:

• A:“Scissors”, B:“Rock”, C:“Paper”
• A:“Archers”, B:“Cavalry”, C:“Pikemen”
• A:“Cockroach”, B:“Foot”, C:“Armageddon”…

However, I’ll just stick with A, B, and C for now.

Over the course of the game, a number of encounters take place. In an encounter, one unit is randomly chosen from each player’s army and they do battle. The unit who wins the battle is decided based on the precedence rules above. In a battle between two units of the same type, the winner is decided randomly with 50:50 chance.

Following a battle, the victorious unit survives and returns to the winning player’s army, while the defeated unit is destroyed.

Let’s now assume that both players always maintain their army at maximum strength. In other words, as soon as a unit is defeated in combat, the losing player always build a new unit to replenish their army back to full capacity of 60 units. The strategy of the game therefore comes in deciding which unit types to initially build, and which types to replace them with when they are defeated following an encounter.

 

#1: Balanced Mixed Strategy

In this simple strategy, each player initially builds their army to consist equally of one third each of the different unit types.

When a unit is defeated, the player builds another unit of the same type to replace it, maintaining the same ratio of unit types in their army throughout the entire game.

Player 1’s Army

Player 2’s Army

As you’d probably expect, after simulating 1,000 battle encounters under this balanced mixed strategy, the win ratio between the players averages out to be 50:50:

In this type of simple 2-player, zero-sum game, both players randomising between the three unit types is a Nash Equilibrium and, if both players were rational, their optimum strategy would always be to ensure their army consisted of one third each of the different unit types. Anything other than this could be exploited profitably by the opponent, as we’ll see shortly.

 

#2: Unbalanced Mixed Strategy

Real players aren’t rational, and different people’s play styles often choose them to favour one unit type over another. Suppose Player 1 has a preference to playing with Unit A, and they don’t really like Unit C much at all. So, they build up their army as follows:

• Unit A: 35
• Unit B: 20
• Unit C: 5

Player 2 (the computer-controlled player) has no knowledge of Player 1’s strategy, so starts as before with a balanced army of each type:

• Unit A: 20
• Unit B: 20
• Unit C: 20

Once again, whenever a unit is defeated, the losing player chooses to replace it with a unit of the same type as that just defeated to maintain their chosen ratios, so the makeup of each player’s army over the course of the game remains constant, as follows:

Player 1’s Army

Player 2’s Army

It might not be as apparently obvious as in the first example, but the win ratio between players using these strategies after a series of encounters still converges to 50:50. Even though it is more likely that Unit A will be chosen from Player 1’s army, there is an equal chance of Unit A, B, or C being chosen from Player 2, so it is still equally likely that either player will win a random encounter (this would still be the case even if Player 1 built only one type of unit):

But, is there are a way that Player 2 could exploit the fact that Player 1’s army is now unbalanced? Obviously, computer-controlled A.I. can always “cheat” and simply build the appropriate unit types to defeat the unit types it knows the player is building, but that is a little unfair. Instead, let’s see if we can develop a kind of “Artificial Immunity” through nothing more than knowledge of the unit types encountered in battle, and whether they were defeated or not.

 

#3: Adaptive Strategy using Artificial Immunity

Suppose that, once again, Player 1 favours an unbalanced mix of unit types as in the last example:

• Unit A: 35
• Unit B: 20
• Unit C: 5

And, as before, Player 2 starts with a balanced army of each type:

• Unit A: 20
• Unit B: 20
• Unit C: 20

However, in this example, we’ll attempt to model the idea of Player 2 developing an artificial immunity to Player 1’s actions by changing the strategies regarding unit replacement:

• If Player 1 wins, their successful unit survives while Player 2’s unit is destroyed. Player 2 is no longer constrained to maintain the same ratio of unit types in their army, but is none the wiser about how to defeat this type of opponent, so they build a replacement unit of a randomly chosen type.
• If Player 2 wins, their successful unit survives while Player 1’s unit is destroyed. Player 1 builds a replacement unit of the same type that was defeated (in order to maintain their preferred 35:20:5 ratio of unit types). BUT, Player 2 also chooses to replace one of the existing units of their army (chosen at random) with another unit of the type that just succeeded in battle.

You can consider this second rule to mimic the immune response – having encountered a hostile antigen (Player 1’s unit), and successfully neutralised it, the Artificial Immune System generates more of the appropriate antibodies (the unit type that dominated it) to respond if the same antigen is found in the future. (This at least concurs with my GCSE biology understanding of the immune system!)

So, how does it perform in practice? First, let’s see how the composition of Player 2’s army changes over the course of the game using this strategy:

Player 1’s Army

Player 2’s Army

Player 2’s army starts, as in all the previous examples, equally composed of A:20, B:20, C:20. However, rather than being fixed, notice how the composition of Player 2’s army changes to approximate A:5, B:35, C:20, which best responds to the composition of Player 1’s army of A:35, B:20, C:5. If you prefer to think in colours, notice that the green band of Player 2’s graph approximates the red section of Player 1’s, the red section of Player 2 approximates the blue section of Player 1, and the blue section of Player 2 approximates the green section of Player 1.

And the effect on the average win rate clearly shows that this “immunity” that has developed over the course of previous encounters gives Player 2 the competitive edge, with an average win rate of over 70% after 1,000 encounters :

At this point, it seems reasonable to expect Player 1 to notice that things aren’t going as well as they’d hoped, and to try changing their strategy. Let’s suppose that, after 1,000 encounters, they change the composition of their army, dropping unit A entirely and instead forming their army equally from unit types B and C (i.e. A:0, B:30, C:30). Player 2 continues to play the same adaptive immunity strategy:

Player 1’s Army – switching after 1,000 encounters

Player 2’s Army adapting to change

Notice how Player 2’s strategy quickly adapts to the change in Player 1’s strategy: after 1,000 battles, Player 2 no longer encounters any further Type A units from Player1 (as there are none in her army), so Player’ 2’s own production of Type B units (green) drops accordingly. Likewise, Player 2’s production of Type A units (red) increases to reflect the increased number of encounters with Player 1’s Type C units (blue).

Note that, even after 1,000 iterations with no encounter of a Type A unit, Player 2’s army still contains a residual reserve of Type B units generated by random chance following a defeat, ready to be activated should Player 1’s strategy change again.

This is only a very simple model of how game A.I. could be modelled based on an artificial immune system response, but I think it shows that it’s definitely a technique worth investigating further.

Useful Online Game A.I. Resources

Besides the books listed in my previous post, there’s a stack of other useful resources available on the ‘net for game A.I. Here’s some of my favourites:

 

Websites

http://natureofcode.com/book/

Entire free online ebook (also available to purchase in paper form) covering a variety of interesting algorithms based on the natural world – chaos, genetics, forces, fractals, neural networks and more. Contains good online code examples written in processing.

http://www.red3d.com/cwr/steer/

Craig Reynolds’ original description of the popular “Steering Behaviours for Autonomous Characters”, which have been re-used in many forms since their first introduction. Perhaps the most famous is his boids flocking algorithm, but be sure to check out the other behaviours, such as queueing and collision avoidance.

http://aigamedev.com

Some good, up-to-date articles and videos. You can register for free to get access to the “insider” content, but for the really good “premium” content, you’ll need a paid registration.

 

Forums / Q+A sites

The following two sites have dedicated tags for game AI questions, and are fairly active and helpful:

http://gamedev.stackexchange.com/questions/tagged/ai

http://www.gamedev.net/forum/9-artificial-intelligence

 

Papers / Presentations

The best place to look for state-of-the-art AI examples is the papers presented at the GDC AI Summit each year. A catalogue of presentations from every previous conference is listed at http://www.gameai.com/papers.php and these are generally available for viewing on the GDC website at http://www.gdcvault.com/ , but only if you’ve got a paid membership

However, here’s some other interesting papers that are freely-available:

Killzone’s AI: Dynamic Procedural Tactics

Next-gen content creation for next-gen AI

A list of presentations and articles by Damian Isla, former AI and Gameplay engineering lead at Bungie.

HTN Planning and Game State Management in Warcraft II

 

Courses

There are no game-AI specific online courses that I am aware of. However, there are several excellent general A.I. courses, and these cover many relevant techniques such as A* and other searches, task planning, dealing with sensor data etc. There’s also courses on subjects allied to game development such as game theory and gamification. They’re all free and from top universities, so lap them up!

Intro to Artificial Intelligence (Udacity)

Artificial Intelligence for Robotics (Udacity)

CS188.1x Artificial Intelligence (University of Berkeley, California via edX)

Artificial Intelligence Planning (University of Edinburgh via Coursera)

Neural Networks for Machine Learning (University of Toronto via Coursera)

Machine Learning (Stanford University via Coursera)

Game Theory (Stanford University via Coursera)

Gamification (University of Pennsylvania via Coursera)

Good Books for Game A.I.

I had a great time last night hosting a presentation on Artificial Intelligence for the Norfolk Indie Game Developers group. Expect to see a series of blog posts on each of the topics appearing here in the near future.

In the meantime, a few people asked me for recommendations of good books on the subject, so here goes:

 

"Programming Game AI By Example" (Buckland)

http://www.amazon.co.uk/Programming-Game-Example-Mat-Buckland/dp/1556220782

This is an easy-to-read, often humorous, introductory-level AI book that covers much of the same material I did last night, including Steering Behaviours, Finite State Machines, Pathfinding, and Scripting (in fact, I based some of the logic for my 5-a-side football simulator from the "Simple Soccer" example in this book). However, it does not cover Neural Networks or Genetic Algorithms. My biggest criticism is that it’s quite old now (published in 2004) so doesn’t exactly cover any cutting-edge stuff, but what’s there is still very relevant.

Code samples are provided in C++ and can be downloaded from the publisher’s website: http://samples.jbpub.com/9781556220784/Buckland_SourceCode.zip

My Rating: 4.00/5.00

 

"Artificial Intelligence for Games" (2nd ed. Millington and Funge)

http://www.amazon.co.uk/Artificial-Intelligence-Games-Ian-Millington/dp/0123747317

At nearly 900 pages long, this book provides a comprehensive coverage of the full range of Game AI – certainly everything I talked about and more – and the second edition (published 2009) was updated to include more recent AI techniques. The authors have lots of practical experience and not only discuss theory but also share their experience and advice on issues such as performance optimisation in real-life production environments. It’s fairly thorough and generally well-written, although I find the writing style drier and more technical than Buckland. It’s certainly a good reference to have by your desk, but not necessarily a book that you’d sit down and read casually by the beach.

Code samples are in C++ on GitHub: https://github.com/idmillington/aicore

My Rating: 4.00/5.00

 

"AI Techniques for Game Programming" (Buckland)

http://www.amazon.co.uk/AI-Techniques-Game-Programming-Development/dp/193184108X

Buckland’s first book (from 2002) has, unfortunately, aged quite badly. This is evident in the first part of the book, which describes how to set up a windows development environment in “the latest” Windows XP and drawing graphics using Win32 GDI – you won’t find any DirectX or OpenGL here.

It does have good explanations and examples of genetic algorithms and neural networks, which are missing from his later “Programming Game AI by Example” book, but it doesn’t include any other topics, and I wouldn’t say that these two topics alone justify the price tag.

My Rating: 2.00/5.00

 

“AI for Game Developers” (Bourg)

http://www.amazon.co.uk/AI-Game-Developers-Creating-Intelligent/dp/0596005555

This is a disappointing book. While the table of contents is encouraging – apparently covering most of the core areas of game AI – the writing style is often clumsy and unclear, and explanations often skim over important details in a manner that makes you wonder whether the authors themselves really understood what they were trying to explain. Add to that fact that the code samples are poorly written (unused global variables, anyone?), and sometimes simply don’t work, and the whole thing is now outdated, so I really can’t recommend this.

My Rating: 1.00/5.00

 

 

“AI Game Programming Wisdom” series (Various)

http://www.amazon.co.uk/AI-Game-Programming-Wisdom-CD/dp/1584505230

This is a four-part collection of short journal-style articles that generally represent state-of-the-art in AI programming written by industry professionals, and edited by Steve Rabin (Principal Software Engineer, Nintendo of America Inc. ). The problem is that, as they are really only marketed at A.I. professionals, they are expensive and only produced in limited numbers so it’s hard to get hold of a copy.

If you go to http://www.aiwisdom.com/index.html you can find an index of each of the articles and the collection it appeared in (some also appear in the related “Game Programming Gems” collection). If you’re lucky, you’ll find that the authors have also published that some article for free somewhere else, such as if they presented it at a conference.

My Rating: If you’ve got the $$$ and you want to learn the latest innovations in AI, 5.00/5.00. Otherwise, don’t bother.