The State of Game AI
I’ve been exploring game AI for a private project. (Perhaps something I can announce at a later date.)
Read the full post for a partial breakdown of current game AI and some interesting tidbits.
AI is probably the piece of game design with the most room for improvement. According to this excellent article, “[s]urveys indicate that the percentage of CPU (central processing unit) cycles that developers are allowed to burn on AI computations is steadily growing.” This provides opportunities for more advanced and thorough game AIs.
Figuring out how to transfer AI from academia, where reliability and reproducibility are less important than theoretical correctness, is a significant challenge. Game AI differs from academic AI in that the goal is fun play, not necessarily realistic behavior. Additionally, working with standard interfaces is critical. Such interfaces are currently under development by the AIIS. A list of current game AI toolkits.
AI is primarily used for controlling None Player Characters, or NPCs. AI systems are used to let NPCs perform tasks, do combat, etc. Some components of current game AIs include:
- Path finding. This seems easy, but has not been solved sufficiently. In games, it is challenging due to CPU limitations and changing environments. For various factors that influence path finding, see ‘Finding a Pathfinder’, AICG99, by Bjorn Reese and Bryan Stout.
- For path finding, A* is typically used. See this tutorial. Issues: deciding the layout of waypoints (nodes), working on multiple hierarchical resolutions for coarse vs. fine pathfinding, memory management.
- To navigate between waypoints, short-term steering behaviors and obstacle avoidance are used. See this paper/site on steering behaviors, and be sure to check out the demonstration applets.
- Finite State Machines (hierarchical, non-deterministic) — see this illustration — and decision trees can be used to let an NPC decide on appropriate actions. In Halo 2, internal nodes make decisions and leaf nodes enact actions. You can either have custom code in the internal nodes, or let the children compete and the parent decide which child to call. See Handling Complexity in the Halo 2 AI for a good read.
- Rule Based Systems, or RBS. In RBS, one uses knowledge engineering to produce Production Rules defining actions the NPC should take. See this tutorial for a good example of hierarchical Production Rules. See also the AIISC workgroup report on RPS.
AI is also used for crowd simulation, procedural animations like flocks of birds, and procedurally generated textures/landscapes/models (which I wrote about earlier). See also Artificial Life research, although besides the venerable Black & White, I don’t think much of this has ended up in games as of yet. It has applications to MMOGs, though.
Useful sites to look at:
- Game Research and Technology
- CGF-AI
- gameai.com
- ai-blog
- John Laird’s Artificial Intelligence & Computer Games Research
- gamedev.net
- Amit’s Game Programming Information
- Adaptive Constraint-Based Agents in Artificial Environments
Tidbits of interest: (I have added links and some formatting.)
From CGDC 05 Observations:
“Later that day I went to a big presentation about the HALO 2 AI [use BugMeNot to bypass registration], and it was pretty neat. They used a rules-based system which added or removed rules dynamically in a manner similar to SOAR, but more flexible. Using this approach there were around 130 behaviors in total with any one AI accessing about 80 or so. They weighted behavior with relevancy to the situation and chose from them dynamically based on the activation criteria registered by each behavior when it was loaded. Individual behaviors were marked as to whether or not they could be interrupted so that AIs didn’t flail around between behaviors, and some had higher priorities if they were urgent (like returning fire or getting under cover).”
[…]“It was really more about the AI design for SWAT 4 and Tribes Vengeance than anything else and I learned a lot. I didn’t know for example that these two games used the exact same AI engine at their core, something called Tyrion. It was another well-designed goals/action/resources kind of engine, with goals selected by the AIs and resources claimed to achieve those goals. Actions resulted in behaviors and particular ways to go about making things happen. Much like with HALO 2, the AI agents could swap in new goals as they went and discard obsolete ones. The whole system was message-based (which the developer highly recommended) and goals were prioritized. They stressed that the various agents at each level of the game — team, squad, vehicles, drivers/gunners — didn’t have different AI levels, just different suites of goals they could chose from. It took them about 16 months to develop Tyrion and they ended up with around 50 behaviors overall. It was pretty neat.”
[…]
“The last AI session I went to (besides my roundtables) was what they were calling a “Poster Session” on the subject of State Estimation for Game AI. It was basically the work of a college student wherein he proposed using a particle filter to estimate where enemies might be in a first person shooter … a single particle was placed in each location where an enemy (now out of sight) might have moved to. The spacing was increased over time if the AI didn’t get updates or check a given area out, and particles were “released” for placement elsewhere as potential areas were checked out. You could increase or decrease the “smarts” of the AI by modifying the number of particles he had available to “speculate” with. Very interesting stuff, and fairly impressive speeds for his calculations … he seemed very pleased when I told him, “Good work” after the presentation.”
Finally, this useful gem:
“I mentioned earlier something about AI designs that I noted at the GDC and I wanted to get into it more here. I was struck by how the major talks I attended had all essentially boiled down their AI designs to the same basic structure:
- Message-based;
- Dynamically assigned pointers to groups/lists of behaviors that defined specific actions;
- Modules describing behaviors and their triggering conditions;
- A prioritization method (cost, base priority, etc.) to allow a given agent to select actions from their possible list;
- A strictly enforced mechanism for inter-agent communication using some form of messages.
I think this is a positive indicator of a growing maturity in AI design. There simply wasn’t any talk of pathfinding, or the benefits of agents, or FSMs vs. FuSMs…all of the talk was about building a good AI engine that would provide value over several game iterations. I think this might be the kind of stability that is needed for AI middleware to have a chance of catching on as well. There’s simply no point in looking at such tools if you’re constantly designing a new engine. On the other hand if you’ve got an engine you like and plan to use over several projects, this automatically brings with it engineers dedicated to this software package and makes them more inclined towards looking at outside sources for enhancements. I think this explains what I was seeing as a slowdown in game AI development…in retrospect I think it’s more of a “maturing” than anything else.”