To build AI logic, game developers use a variety of different techniques depending on their preferences and the problem at hand. It’s interesting to note, however, that the overall architecture and methodology they use is often similar. Indeed, good techniques are often reinvented and great ideas spread fast in the games industry.
This week’s Thursday Theory article looks into a white paper that may never have been revolutionary, but documents many different techniques and methodologies that have been used in the animat and virtual agent communities as well as in game development. The underlying methodology is called Behavior-Oriented Design (BOD) as developed by Joanna Bryson from the University of Bath. The ideas presented here are related, and applicable to the increasingly popular behavior trees.
Building complete, complex agents that can work on their own and manage conflicting goals and multiple mutually-exclusive means of achieving those goals is a hard problem. BOD is designed to help by providing a methodology and a basic architecture for dealing with this.
In particular, the paper covers three major aspects of the problem:
Of course modularity is good for game AI, but how do you make it shine? Modules of behavior are often difficult to define. What part of the behavior should be separate module? It can take time to figure out effective behavior modules.
In practice, behaviors often need a certain level of autonomy to deal with problems, while at the same time solving specific problems in the game. Designing such behaviors can be a challenge too.
In the agent community (and certain games), AI is increasingly built as a three-layer architectures of behavior-based AI, reactive planning and deliberative planning. Although it has its advantages, this hybrid approach can take much longer to implement.
The paper addresses these problems by unifying the different layers in the architecture, thereby making it easier to build behaviors that plug together.
Figure 1: An Insect-like robot with no long range sensors using feelers to find its way around a box
BOD, as an entire design methodology, advocates a combination of principles that are very reminiscent of agile development applied to AI. Specifically, the following principles:
Iterative design is used along with rapid prototyping to develop the behaviors.
Changes in architecture, if improvements can be made, are encouraged since they should be simple to do.
The use of the fundamental design principle: when in doubt, favor simplicity.
Self documentation of code and code reuse are covered.
From a technical perspective, the system is based on hierarchical reactive plans which are very similar to behavior trees as used in the games industry for a few years, and by robotics labs for decades before. In particular, the paper advocates:
Encapsulating perception, action, learning and memory as behavior modules, implemented by programmers in a traditional object oriented language.
Letting designers work with a data-driven layer on top, built up of combinations of the low-level modules. This includes action patterns (a.k.a. sequences) and competences (a.k.a. selectors).
Adding in some learning in certain parts of the tree, when losing some control in the process is acceptable.
Using “drive collections” as the highest layer in the architecture to decide which arbitrate between the different goals that can compete for attention.
The paper also contains many nuggets about using reactive hierarchies to solve many problems from the low-level to the high-level. In many aspects of game logic, it helps to have things like “behavior trees” in place since they provide goal-directed behaviors (with optional memory/state) to solve the problem at hand effectively.
Figure 2: A competence reactive plan consisting of several actions that need to be completed to fulfil a goal. The arrow on the left is the rising priority.
Abstract & References
Here’s the abstract for the paper itself:
Behavior-Oriented Design (BOD) is a development methodology for creating complex, complete agents such as virtual-reality characters, autonomous robots, intelligent tutors or intelligent environments. BOD agents are modular, but not multi-agent systems. They use hierarchical reactive plans to perform arbitration between their component modules. BOD provides not only architectural specifications for modules and plans, but a methodology for building them. The BOD methodology is cyclic, consisting of rules for an initial decomposition and heuristics for revising the specification over the process of development.
You can download the paper from the website:
The Behavior-Oriented Design of Modular Agent Intelligence Joanna J. Bryson Agent Technology and Software Engineering 2002. Download PDF (74 KB)
It’s hard to separate ideas in this paper from ones that are generally accepted as good practice already in industry, as well as many opinions you’ll hear on this blog too. So if this paper scores highly, it’s mainly because it documents and unifies techniques from various different places.
- Applicability to games: 10/10
- The modular approach advocated by BOD is not only useful, but practically a requirement for game developers who want to build simple and scalable designs. Additionally, the reactive hierarchy is by far the most computationally effective way of creating intelligent and responsive logic for a game.
- Usefulness for character AI: 9/10
- It’s feasible to build most types of NPCs using techniques similar to behavior trees. The approach is a great way to combine designer control with logic and automation. However, this approach doesn’t natively support the rating and comparison of behaviors based on a heuristic (except at the top-level) so it’s requires a certain skillset to scale this up.
- Simplicity to implement: 10/10
- The methodology itself will appeal to the common sense of the new wave of agile developers, as well as the veterans who prefer to play it by ear! The reactive hierarchy and modular behaviors also require little work, no more than a HFSM.
Another paper inspired by this research is called Behavior Orientated Design of an Unreal Tournament Character. It will be featured in the future on AiGameDev.com, but in the meantime you can sign-up to the forums to find it in the section on White Papers.
You’d be hard pressed to find developers not using these ideas in some way. Likewise, if you take the time to read this paper you’ll most likely find a trick or two that you can use directly within your system.
One idea in particular is the concept of competences, which are at the heart of Halo 2’s AI and very useful in robotic teleo-reactive programs. A second idea is also using drive collections at the top of the tree to work out which “goals” and subtrees to activate in a fuzzy fashion.
What’s particularly fascinating about this paper is that it starts to tie together these reactive hierarchies, or behavior trees, with machine learning. Indeed, combining these two techniques may well be The Secret to Building Game AI that Learns Realistically. It combines a structure that the designer has control over, along with statistical learning.
What do you think about Behavior-Oriented Design and its application to game AI? Post a comment below.