Short Analysis on Behavior Trees, and some Potential Solutions
I wrote this in response to a question on Twitter about behavior trees and my AI implementation in Voxel Quest.
There can be many potential implementations of behavior trees that address various problems, but for the sake of argument I am addressing the general/naive implementations.
From a strictly language-oriented standpoint, many behavior trees are similar to finite state machines, which, while computationally effective, are not the most expressive method available. Assuming your behavior tree is actually a tree and not a graph (child nodes never connect to parents/siblings/cousins/etc), your state is determined by a linear traversal from a root node to some leaf node.
For simple games, this is not a problem and a quite elegant solution. You only begin to see problems when your state is determined by many different quantities, and when these quantities change over time or have differing priorities based on the state of other variables.
Imagine a few states, all binary (yes/no):
This is only 8 binary states — assuming each state had a unique result, there are 256 possible combinations of states for which you must specify a resulting action (2 to the power of 8 == 256).
Maybe thats workable, but what happens when you add just 8 more states? You now have 65,536 states to specify. What happens when the states are not binary, but have weighted results based on different actions (i.e. you are only a little bit hungry, or your hunger takes a back seat when you are in danger). In the end, with a naive implementation, you are going to end up specifying many states and even then it ultimately might not seem all that intelligent.
In order to do anything that weights solutions based on changing circumstances, you are going to need score maximization, as used in pathfinding (such as A*), only in this case you are evaluating the cost of various actions and the ultimate resulting score of achieving those actions. Instead of finding the best path, you are determining the best course of actions (part of which is likely computing the cost of walking a given path).
I am using A* for this purpose and there is nothing novel there. But this is only one part of it. The other part is logic programming, something that is mostly ignored in games. I won’t go into too much detail explaining how logic programming works, but if you are interested a good starting point is learning about Prolog; here is a free book on it:
Facts, Rules, and Queries Unification and Proof Search Recursion Lists Arithmetic More Lists Definite Clause Grammars…www.learnprolognow.org
The beauty of logic programming is that you need not explicitly define everything. It can make logical inferences on its own, using a technique borrowed from lambda calculus called “unification.” In this way, much of the logic is implicitly definied. For example, you can specify (using pseudo code here):
- apple is fruit
- apple is red
- orange is fruit
- if (is fruit and is red) then (is delicious)
Given this knowledge base, you can then pose queries such as
- apple is delicious?
and it will respond “true.” Note that we never explicitly specified that apples are delicious, we only stated apples were fruit and that they are red. The rest was inferred from the last rule in the knowledge base. This is the most trivial example of logic programming, and it can actually get much more complex and interesting than this, but this will give you a taste. I will also be demoing this in the coming weeks on voxelquest.com as I am actively working on this part of the AI right now.
The interesting thing about logic programming is that you can specify arbitrary predicates (relations between nouns or other terminals like numbers) and it deduces the meaning based on the context. This is somewhat mind-blowing because it is the same way that humans learn any language — we only learn what words mean based on context. Our brains form syntax and grammars based on how we are taught to order verbs and nouns and so forth, and we deduce meaning based on these things. The computer has no idea what these “words” mean — they are just symbols, and can reside in memory as unique integers for each word, just as you would use a symbol table in a compiler.
Logic programming on its own is not entirely useful, but when combined with score maximization and planning/goals I think it might yield interesting results. I can’t say whether or not my attempts here will be successful, so this is by no means advice on how you should code your game AI. I am only trying something a bit different from what has been used in gaming so far, albeit using techniques that have been around a long time in the field of general AI.