Game/AI

How to Become a Game AI Developer

The industry always needs more talented AI developers, and I thought I should post some thoughts here to share my own perception of the best strategies for picking up the skills the industry needs and getting into a game AI development role.

I'd originally written up this post months ago, but in light of Dave Mark's recent article on aigamedev.com, I thought it was time to post my 2 cents.

First and foremost, focus on developing the skills you need to become a solid, well-rounded game developer before you try to specialize.

#1: Generalize, Then Specialize

Game studios are generally not interested in hiring entry-level engineers as AI specialists right off the bat. We need engineers who have a broad understanding of all the different parts of a game's source code, and this means that it takes a few years to gain enough understanding of game development to be able to branch off into any particular area. In some cases, new hires will be asked to help fill in the gaps on a project that's rushing headlong toward its ship date. New engineers are often expected or to do work that no one else on the team has time to handle (or interest in doing).

It's fine to explain to a potential employer that you're interested in game AI engineering as a long-term goal, but you should expect that your first few years in the industry will not involve a lot of specialization.

It's important to keep in mind that becoming a generalist first is a good thing. An AI developer needs a solid understanding of the fundamentals of game development, a broad understanding of all the components of a modern game engine, and the irreplaceable experience you gain from shipping an actual product.

So first and foremost, gain the skills you need to become a great engineer. To most developers, that includes:

* A broad knowledge of C++ and the STL
* An ability to wrote code that's robust and readable
* A solid understanding of algorithms and data structures
* A good understanding of object-oriented programming practices
* A pragmatic attitude towards development and a willingness to take a "bottom-up" approach to solving problems
* An understanding of how to test code and how to code defensively (i.e. using the language features of C++ to minimize the possibility of defects and force the compiler and linker to tell you when certain classes of problems occur)
* A willingness to let the profiler drive performance optimizations, to find out where optimization is really necessary before attempting to optimize, and to look at big-picture algorithmic optimizations before trying to resort to fancy tricks and hand-coded assembly
* An understanding of how to use memory resources efficiently
* A broad understanding of the overall architecture of a modern game engine
* A solid understanding of the 3D math techniques needed in all areas of game engineering
* An ability to communicate and to work well on a team

EDIT: Here's a quick list of the most recommended books on my bookshelf for the kinds of general engineering skills I'm referring to: [Effective C++, More Effective C++, C++ Coding Standards, Code Complete, The C++ Programming Language, 3D Math Primer for Graphics and Game Development]

EDIT: [jorkin] Additional useful books here: The AI Programmer's Bookshelf - game AI programming book list.

#2: Write a Sample Program

The single best way to impress a company is to write a sample program in C++ (yes, you could use Java or C#, but the industry tends to use C++ exclusively on the game side, and Java and C# are only used on the tools side). Your program doesn't need to be anything graphically impressive, but do something that shows how you work and how you think. Don't use a group project from school -- make it something you wrote yourself and that you can take full credit for.

More importantly, you definitely want to be able to provide the source code as well, so you can give a potential employer a demo along with the sample code that was used to create it. Make your code as solid, readable, and bug-free as possible, and be prepared to answer questions about the choices you made when writing the code.

#3: Be Persistent

Once you have a solid background as an engineer and a good sample program to show potential employers, talk to as many companies as you can. The programming tests alone are worth the effort, and they'll do a lot to improve your skills no matter how long you've been in the industry.

When someone throws you a tough interview question, be sure to keep attacking the problem as vigorously as you can, and don't be afraid to ask the interviewer for help with it -- the interview is partly a test of how you handle pressure, how determined you are to solve a problem, and whether you can communicate when you're stuck in a corner or if you "lock up."

#4: Be Pragmatic

Finally, if you do discuss AI with a potential employer, make sure you approach it with a pragmatic attitude. Be aware that there's a world of difference between what "artificial intelligence" means in an academic setting and what we mean by "game AI." Also be aware that there are many in the industry who feel (often correctly) that game AI hasn't always lived up to its promises.

If you start talking to potential employers about neural networks or other machine learning techniques, you should expect that the hairs on the back of their necks will stand up, and you'll want to be able to explain exactly how it's relevant to game AI (which can be a tall order, given that there are still a few developers out there who think that any AI is too much).

Employers are very leery of hiring anyone who seems to have their head in the clouds, and you need to bend over backwards to prove that you're pragmatic. It's important to understand exactly what the challenges are with regard to game AI and where it fits into the overall process -- see my recent post on this blog for a list of the kinds of problems AI developers confront on a daily basis.

AI development can be very rewarding if you find the right company and the right project.

Good luck!

Fairy Magic Explained

It turns out that my original hypothesis regarding Spore's animation system -- a hypothesis that involved the use of fairy magic, or possibly that of leprechauns -- turned out to be slightly off the mark. Who knew!

Happily, the authors have published the paper I'd hoped for. Many thanks to Alex Champandard for the link!

UPDATE: Despite my best efforts, I'm unable to get the Spore Creature Creator to perform any locomotion based on rolling, no matter how similar my creature may be to M.C. Escher's "curl-up" bug.

I expect to see this functionality in Spore 2 ... Get on it!

Interviewing AI Developers

I left Retro Studios a few weeks ago, and I've been talking to a lot of developers in the meantime. It's been a really fun process.

However, it's also reminded me that when it comes to AI development, our industry is all over the map.

So I thought it would be a good idea to make a big list of AI interview questions ... some that I've asked, some that I've been asked, and others that I think are worth asking. I left the answers blank, since plenty of good answers to all of these questions are easily accessible in all sorts of places (and if you're the one giving the interview, you should already know the answers!)

If you think of any good ones I missed, go ahead and add them in the Comments section below.

And if you happen to be interviewing me, of course, feel free to ask me any of these!

AI Developer Interview Questions

Behavioral AI

-What's the difference between a finite state machine (FSM) and a hierarchical finite state machine (HFSM)? Give an example of a hierarchical state machine with functionality that you could not easily replicate in a non-hierarchical FSM.

-What are some of the limitations of state machines? When is the use of state machines appropriate, and when are they insufficient to generate the kinds of behaviors you need in a game?

-What is a decision tree? When would you want to use one? What are its performance characteristics? How can you generate a decision tree automatically from a pre-existing data set? Is it feasible to do this at runtime, and has it been done in a commercial game before? When and why would you want to do this, and how would the data need to be organized to make this possible?

-You're developing a boss encounter in a 3D platformer game, and the boss has 15 different attacks. The game designers have asked you to make sure that the player sees as many of those 15 attacks as possible during the encounter, and that he seldom or never sees the same attack twice in a row. What are some ways you can do this? What does the attack selection algorithm look like in this case? Keep in mind that not all attacks are possible all the time -- for example, the boss has a melee attack that he can only do when the player is very close, and a bombardment attack he can only do when the player is far away.

-In one room in your game, there's an elevator that AIs will need to use to escape from the player. In order to use the elevator, they have to walk over to a special button on the wall, press it to summon the elevator, then walk into the elevator and press another button to tell it to ascend. How would you design a system to make sure AIs can do all of these things in the proper order? If you have 3 AIs in the room, how would you design the system to make sure they can all escape in the elevator at the same time? What happens if one of them dies while they're trying to do this, and how do you make sure the other AIs don't get stuck waiting for that dead AI?

-You're in charge of implementing a stealth game similar to Thief: The Dark Project, and you need guards in your game that have imperfect vision and hearing and inhabit dimly-lit castles, and they can search the area for the player if they think there's an intruder around. How do you model the sensory systems of these guards, and how do you aggregate auditory, visual, and other kinds of stimuli in this system? How do you implement the various alert states for the guards, and why?

-What is planning? How is it used, and what are its advantages? Is it feasible to use planning in real-time games? If so, name any titles where planning has been used for any part of the AI. Describe the architecture of a planning-based AI system for any genre of game.

-You're working on a game that involves enemy wizards dueling each other. Each wizard has at least a dozen different spells at his disposal -- some of them simply inflict damage, while others will temporarily stun or immobilize an enemy, slow him, prevent him from casting spells for a brief duration, teleport the caster a short distance, or give the caster a temporary shield. A wizard can only cast one spell at a time, but each spell has a fixed cooldown (time before it can be cast again) and an associated mana cost (assume no mana regeneration). Describe some ways you might implement a competent AI system for a wizard.

Spatial Reasoning

-Using the example of the Thief-like AI system in the previous section, how do you implement the 'search for player' behavior for the guards, and get them to search an area in a believable fashion? How do you make sure this searching behavior isn't too challenging for players, and ensure that it's usually possible for the player to escape the search if he plays the game well?

-You're tasked with implementing a computer player for a real-time strategy (RTS) game. Assuming that there is no fog-of-war, how do you implement a system to allow the computer player to determine what parts of the map are controlled by enemy players, and which parts are open to easy exploitation? How do you identify the choke points on the map? How do you find the boundary between the parts of the map under your control and the parts of the map controlled by enemy players? How do you detect an impending enemy attack or a change in an enemy's offensive posture?

-You have an AI player in an RTS game that occasionally needs to send scouts out onto the map to perform reconaissance. Designers want each scout to move around semi-randomly, exploring various parts of the map, particularly those that have been seen the least recently. Assume that the game is grid-based and has a fog-of-war feature. Also assume that the scouts are very cheap and dispensable, and it's OK for them to walk into the enemy base or other dangerous areas. How would you implement the system to decide where the scouts should go? What sort of data structure do you need to support this? How can you ensure that the scouts do a good job of exploring the map thoroughly? What are the performance characteristics of your approach? Is there any risk of scouts getting stuck trying to go somewhere that isn't even accessible?

Steering

-How does a flocking-based steering system work? What are the components of a flocking-based steering system, and how are they combined? When does flocking-based steering break down or produce undesirable results? Are there any performance implications of the standard flocking model as described by Craig Reynolds, and if so, what are some ways to address them?

-What are attractors and repulsors? How do they interact with a steering system? When are they useful, and what are their limitations? When can they be used for obstacle avoidance, and when are they insufficient?

-As you're starting work on your game, one of your colleagues suggests avoiding pathfinding completely, and just using potential fields for pathfinding and navigation. He suggests that you just overlay a big 2D grid over the world, with each cell indicating the distance to the nearest obstacle. Is his idea feasible? Why or why not? When would it cause problems? Regardless of the answer to that question, what are some of the other ways that such a system could be used?

-You're implementing a medieval strategy game in which pikemen should always walk in front of archers, and catapults should always be behind the archers. Explain how you could implement the movement system to ensure that you keep pikemen in front and catapults in the rear as much as possible. Explain how your answer might be different depending on whether or not the units simply need to end up in that configuration when they reach that destination, or if they need to maintain that formation while moving.

-You're tasked with implementing a crowd that walks around the streets of a city. Describe some ways you could implement this in a fast and efficient manner. How do you ensure that crowd members don't touch each other while moving? How do you get crowd members to get out of each others way, and ensure that no two crowd members can get stuck trying to get around each other?

-Imagine that you need to extend the previous example so that the crowd runs away when any sort of combat incident occurs. How do you get them to run away from the violence? How do you make sure the crowd doesn't immediately fill in this area again? How do you ensure that the crowd does eventually "forget" about this incident and return to fill the area?

-There's a hovercraft in your game, and the designers want the hovercraft to move along a linear sequence of connected waypoints. It should move to a waypoint, stop, fire at the player for a few seconds, and then randomly move to either the next or previous point in the sequence, taking 4 or 5 seconds to reach the waypoint it's selected. How do you control the movement of the hovercraft to make its movement as natural and believable as possible? Is it necessary to use physics to implement this, and if so, why?

Pathfinding and Navigation

-Explain the A* algorithm. How does it compare to other search algorithms, and why is it usually preferred in real-time games? When does A* give poor performance?

-Name at least 3 different ways of representing a search space so that you can perform pathfinding on it. What are the strengths and weaknesses of these approaches, and when would you want to use each one?

-List as many ways as you can think of to optimize pathfinding without sacrificing the quality of the generated paths. Be sure to explain any additional costs (such as increased memory usage) of each of these optimizations.

-Your pathfinding system was written with a normal human soldier in mind, and it does exactly what's needed for normal human soldiers. Halfway through development, the designers decide to add 3 new units: a 15-foot-tall space alien that can't fit through a lot of the doorways in the game, a very wide hovercraft unit that can't go through tight corridors or small doorways, and a soldier on a motorcycle that can only turn relatively slowly (say, 15 degrees left or right per second at any speed). How do you tweak your AI system to accommodate all of them?

-You have a pathfinding system that does a great job of finding a path across the world, but it does not take dynamic obstacles (such as crates, barrels, vehicles, and other AIs) into account. The player is playing a superhero, and he uses his super-strength to drop a soda machine in the AI's path. The AI doesn't have any way to move or destroy the soda machine. Once the AI sees the soda machine blocking his path, what are some different ways he can pathfind around it while ensuring that he eventually returns to his original path and reaches his initial destination? What happens if the soda machine is on top of his destination? What if the soda machine is right in front of a doorway the AI needs to walk through as part of his initial path?

-You're working on a first-person action game set in a 3D world. The game's pathfinding system is built on a navigation mesh. Suddenly, the designers decide that they want the AIs in the game to be able to use ladders to climb up walls, jump up or down small ledges, and leap across small chasms, and they should be able to use all of thse abilities as part of their normal pathfinding. Explain how you would implement such a system and how it would relate to the existing navigation mesh system. Also describe what sort of tools you would provide to the designers (if any) to add this support.

-You're making a WWII shooter with fighting in the streets of Berlin. Your designer wants to ensure that at certain points during the game, the AI-controlled Nazi units will flank the player, with small squads of Nazis approaching from different directions and side streets and alleyways. We assume that cheating is not allowed (i.e. we may not simply teleport units where we want them to go), and we assume that telling the designers to do it with scripting isn't feasible. Describe at least 2 different ways to implement such a system.

-Your designer just played a game where he saw a squad of AIs "leapfrogging" each other -- in other words, proceeding down a corridor in such a way as to ensure that only 1 AI unit is actually moving forward at a time, with the rest providing cover (i.e. the rear unit always moves forward, presumably to the front). He was very impressed and he wants you to implement the same thing. Describe some ways to implement such a system. How do the AIs know when to move, and where to stop and provide covering fire?

Scripting

-How does scripting fit in with AI development? Under what circumstances should AIs be controlled by scripting rather than AI? When designers use scripting to control AI agents, at what level should the scripting interact with the AI?

-Discuss a few of the different scripting systems you've worked with or seen used in games. What are the advantages and disadvantages of different ways of implementing scripting?

-What are the strengths and weaknesses of scripting in general? When should scripting not be used?

-Pick a sample game, and describe the best way to design a scripting system to allow designers a certain level of control over the AI in that game. Also describe the ideal tools for debugging the scripting system you propose.

General

-How should an AI system interact with an animation system? What are the problems with a 1-to-1 mapping between behaviors and animations? Describe some examples of when AIs need to take explicit control over parts of a character's body beyond simply playing a full-body animation, and describe how you would implement this in each case.

-How should an AI system select animations for playback? In other words, what should the interface for the code and data look like, and how should the data be abstracted to allow the AI system to access the animations as simply as possible? Describe the advantages and disadvantages of various ways of different approaches to describing and accessing the animation data.

-What's the coolest AI system you've seen in a game? What impressed you about it, and how do you think it was implemented? What are the runtime performance implications of that kind of a system?

-What are some uses of machine learning (ML) in games? What problems does ML help you solve? What are the strengths and weakenesses of different approaches? What are the performance characteristics of different ML approaches? Which ML techniques can be executed at runtime, and which are more suited to an offline context? Give some examples of where ML has been used in games, whether or not it was successful, and why.

-You have a game in which 1000 NPCs all have to find their way around a complex game level, and each NPC has its own goals and behavioral system. Assume for the sake of this example that these are enemy soldiers and officers patrolling and guarding a base in a first-person shooter. What are some of the ways you could optimize the AI for your NPCs to improve performance? [Thanks to Ian Millington for this question]