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.

At-a-glance functions for modelling utility-based game AI

One of my current projects involves developing a decision-making AI for autonomous characters (i.e. NPCs) in a computer game.

The idea is pretty straightforward – instead of switching between a set of finite states based on simple triggers (i.e. if Pacman has eaten power pill then “run away”, else “chase”), each character constantly assesses the actions available to them in their current environment, and assigns a utility (i.e. the benefit) from each of those actions on a continuous scale. Then, being rational agents, each character simply chooses to perform the action that provides them with the greatest utility. I’m no psychologist, but that seems like a reasonable model of human behaviour to me.

For example, when a character is already at full health, the utility from picking up a health-giving medikit is zero, so you’d never expect the character to perform that action. As the character’s health diminishes, the relative utility of the medikit increases, but in what way? Is it a linear scale?

Or, would a character remain relatively content with 90%, 80%, or 70% health, but then feel increasing urgency to look for medikits when their energy drops under 30%, say? More like this:

Likewise, consider how the utility of searching for an ammo box changes depending on how many bullets the player already has, or the utility of running away varies on the relative strength of an opponent’s weapon.

When deciding how to assign utility to different actions, I find it helpful to refer to the following graphs to consider what function might best describe how I think a rational human player would determine the utility of that action, based on different environment variables (remember, because this is artificial intelligence, there are no “correct” answers – what’s nice is that you can swap in and out different models until you find something that looks right, without worrying about whether it has sound psychological reasoning)

 

Step Function

If x > 0.5 then y = 1, else y = 0.

This is the equivalent to the simple Boolean trigger logic that the Pacman ghosts use – “Has Pacman eaten a power pill? Then definitely run away!”. Note however that the utility assigned to this action when the condition is true doesn’t have to be 100% – it’s possible to step up in stages, or to only step up a certain amount, so that other actions may still have greater utility, even when the condition is true.

 

Linear Function

y = mx + c

Remember that you can change both the gradient (m) and the intercept (c), but any increase in the underlying variable will always lead to a constant proportional increase in utility. To give the gradient a downwards slope, set m to be less than 0.

 

Increasing rate of increase (i.e. exponential increase)

y = x^a where a>1

As the independent variable increases, the marginal utility increases more dramatically.

 

Decreasing rate of increase (i.e. logarithmic increase)

y = x^a where 0 < a < 1

When the independent variable is small, a little increase leads to a big increase in utility from that action. As the independent variable gets larger, the marginal utility increase becomes less and less.

 

Exponential Decay

y = a^x where 0 < a < 1

When the independent variable is small, a little increase leads to a substantial decrease in marginal utility. As the independent variable increases, the marginal utility decrease diminishes.

 

Sigmoid  curve

y = 1/(1+e^x) (or y = 1/1+e^-x for reverse)

This gives an S-shaped curve that, as defined above, is centred about x=0, but is easy to shift to make the middle of the curve (where the gradient is steepest) lie wherever is appropriate.

 

Frequently, the utility of an action (y) varies not only with a single variable (x) as shown here, but with multiple variables – the utility of attacking another character may increase linearly with the value of the prize if successful, but decrease exponentially with the relative strength of that character. That’s no problem – just combine the utilities as:

Utility from attacking = w₁(prize to be won) – w₂(relative strength^2)

By changing the functions used to calculate the utility of each action, and adjusting the weights (w₁ and w₂ above), you can create surprisingly sophisticated AI decision-making behaviour using only the handful of functions above.

 

Choosing the Action with the Greatest Utility

As an example, suppose that your computer-controlled agent was capable of three actions: attack, heal, or reload, and that you had chosen utility curves for those actions based, respectively, on the perceived enemy strength, current health, and number of bullets held, as follows:

We can now determine what the “best” course of action would be for the character at any point in time by plugging in the current values of strength, health, and bullets and reading off the associated utility of each action. For example, starting from this situation:

• Enemy Strength = 6   ==> Utility of Attacking = 40
• Health = 70                ==> Utility of Healing = 14
• Bullets = 5                ==> Utility of Reloading = 30

The action with the greatest utility is to attack. So, the character starts to attack, and fires off a few bullets. The situation now becomes:

• Enemy Strength = 6   ==> Utility of Attacking = 40
• Health = 70                ==> Utility of Healing = 14
• Bullets = 3                ==> Utility of Reloading = 50

Now, the greatest utility comes from reloading. So the player refills the chamber of their gun. Unfortunately, in doing so they take a few hits, damaging their health:

• Enemy Strength = 6   ==> Utility of Attacking = 40
• Health = 50                ==> Utility of Healing = 50
• Bullets = 20                ==> Utility of Reloading = 0

At this point, health has become an issue, and the greatest utility now comes from healing.

By tweaking the utility curves, you can create differences in character’s personalities – for example, a “brave” character would derive greater utility from attacking than a more cowardly character would, so the attacking utility curve for the brave character would be higher than the cowardly one. Likewise, a cautious character might place greater emphasis on reloading and healing than on attacking.