Table of Contents
Readers who enjoy this issue of Exercises in Game AI Programming are encouraged to:
Check out chapters 11 and 12 of my book, AI Game Development.
Send me comments and suggestions at <feedback at AiGameDev>.
Sign up for updates via the AiGameDev.com mailing list.
This tutorial covers the background details first, introducting the RBS technology available and the desired behaviours for Breaker. Then, we'll look into the methodology used to design the system, and we'll analyse the implementation in depth. Finally, the results are analysed and discussed.
Breaker should be capable of accomplishing the following:
Low-level movement behaviors such as obstacle avoidance, chasing and evading,
Weapon selection based on the current spacial position and situation of the game,
Attacking the enemy using prediction of movement, basic aiming and firing,
Tactical reasoning and selection of the right action in the current context.
These are problems that fall into two categories: problem solving and control. By design, these can be mostly solved with reactive techniques that map inputs to outputs, or stimulus to response.
The implementation used for the AI is based on a second generation rule-based system. It allows the rules to be stored in a declarative fashion in a simple XML format. The if-then rules may have arbitrary number of antecedant and consequent clauses. The representation of the rules is based on boolean symbols only. The conflict resolution strategy uses priorities derived from the order of the rules to decide which rule to execute if multiple ones are applicable.
The interpreter is coded in C++, in a data-driven fashion. The rules are loaded with a lightweight XML parser, and converted to a more efficient internal format. The implementation makes heavy use of the C++ STL to reduce the amount of code required. The vector and map template classes are used the most, and so the core implementation fits in around 100 lines.
![[Note]](/images/note.png) | Note |
|---|---|
Many of the conclusions drawn from this tutorial should be applied to RBS of this type only. There are are a wide variety of extensions, each with their own set of advantages and pitfalls. | |
The purpose of this exercise is to push our implementation of a rule-based systems to the limit and find its weaknesses. The system therefore includes as little as possible C++ code. It's surprisingly easy to improve the capabilities of the system by pre- and post-processing data exchanged with the rule-based system, but this reveals more about the capabilities of the native language than the AI technique itself.
Many AI techniques can emulate others. In this case, a rule-based system can emulate a finite state machine for example. We'll make a point of not using design practices assocated with other techniques to build our RBS. Specifically, we won't sketch directed graphs to define conditional control sequences, like FSM but expressed as a set of rules.
The most important observation to make is that the rule-based system is responsible for controlling many parts of the animat, including setting the direction of travel and orientation, choosing and controlling the weapon… Many of these abilities are supposed to be executed in parrallel, so the AI can control the orientation of the body while still moving around. Yet, if we chose to execute a standard RBS at each frame of the AI, only one rule would be executed. Since having the animat control only one body part at a time is not acceptable, we have three choices:
Allow the interpreter to execute all the rules that match during one cycle.
With priority-based conflict resolution, each rule can consider false all conditions of rules with higher priority (otherwise the interpreter would pick that rule instead). Allowing all the rules to execute thereby increases the complexity of the conditions in most rules. Indeed, since interpreter won't stop once it finds a match, no preconditions of execution can be assumed. So the assumptions need to be made explicit in each rule condition.
Make the system use effectors that have a persistent effect over time, rather than instantaneous actions.
The major problem with this approach is that it reduces responsiveness of the system. Due to rule priorities, there is a hierarchy in the parts of the body; when one gets control, the others must wait until the next cycle (similarly to a subsumption architecture). Also, keeping track of the state of effectors involves using techniques that a finite state machine would be better suited to.
Separate the rulebase into chunks, each responsible for controlling one part of the body.
This solution is called a decomposition by control. In our case, it has only technical drawbacks; what's the best way to split up the rulebase such that it is simple to manage?
The remainder of this tutorial implements the third option as it creates the most manageable and responsive system, while at the same time using principles that are typical of RBS. To create the rule chunks, special symbols are used as an additional clause in the condition. During execution, the interpreter only considers chunks with their corresponding symbol set to true; other chunks are ignored. This option causes no changes in the interpreter, and the execution time can be kept to a minimum. Using a tree-like structure to store the rules means only the rules in active chunks are considered.
![[Tip]](/images/tip.png) | Tip |
|---|---|
An intuitive approach to create the system is to write down many rules in one creative burst based on the goals listed, without thinking about implications. Then, it's often necessary to reorder the rules and adjust incrementally them so they function effectively as a whole. | |
This section describes the result of incrementally refining the rules and testing the behaviors in the game. The implementation is available as part of the FEAR SDK, which can be found on SourceForge.net:
Download the FEAR
Development Kit
The code for Breaker can be found in #/demos/tutorial/01-Breaker/. See the FEAR User Guide to get started.
The senses are used to gather information from the environment at the request of the RBS. Specific functions need to be implemented to retrieve the data via the world interfaces and convert them into boolean truths. These values are then stored as symbols stored in the working memory, then processed by the interpreter.
Most sensor functions have one line implementation in C++ defined in the file Brain.h in the source archive. Let's run through the different types of sensors used by the AI.
Range sensors are used to determine the distance of the closest obstacles. The default parameters check the space within three steps of the animat's position, returning true if the area is clear. The sensors are placed at -45°, 0° and +45°.
Checks the physical state to see if there's was a collision. The function returns true when another object occupies the space where the animat wanted to move.
These queries are based on the presence of objects within the field of view. The symbols are defined if there's another player present, or if objects that regenerate the animat's health or armor are visible.
These symbols relate to the distance of the enemy. Another player is close within 10 steps of the animat, and far beyond 20 steps.
These are queries of the animat's personal state. Full values correspond to 100% and low values are less than 30%.
Most of the queries do little processing. Only the obstacle sensors do local processing of the terrain structure to ingore small ledges and identify steep ridges as hazards just like walls.
The actions allow the RBS to apply its decision in practice by controlling the body. Most actions too are mostly implemented in one line, and can be found in Brain.h. There's only one more complex function, which is placed in Brain.cpp. The actions are grouped into chunks according to the part of the body they control.
Forward — Move in the direction the body is facing.
Seek — Head towards the enemy.
Flee — Move away from the enemy.
Side — Take a lateral step as a strafing motion.
Avoid — Moves away from the obstacle that was hit, in the direction of the normal of the collision.
Look Left — Rotate the view by -30°.
Look Right — Rotate the view by +30°
Look Behind — Turn the view sharply by over 90° left or right.
Look to Enemy/Health/Armor — Turn to face this entity in the field of view.
Look Around — Gaze around by rotating the view parametrically.
Use Weapon — Four commands to select the most popular weapons: rocket launcher, railgun, chaingun and hyperblaster.
Fire — Pull the trigger on the current weapon.
The actions for looking around and avoiding obstacles by bouncing off them are non-trivial. They cannot be implemented with a symbolic rule-based system as they involve doing integer math and 3D algebra. These functions improve the behaviors, but should be disabled to evaluate the AI technique on its own.
The production rules express the knowledge of the human expert, so the RBS can solve problems of the same type on its own.
This first chunk of if-then rules is responsable for action selection at a high-level. The rules use features of the situation and personal status to determine if a behavior is applicable. With three symbols in their conditions, the first two rules are relatively specific and never conflict. This means that the order of the first two rules is irrelevant. Additional rules could take into account other factors to suggest the same behaviour in other contexts.
As a result of this tactical decision making, internal symbols are set so that other rules can check them to decide what to do. In this case, there are two symbols used: retreat, pursue and dodge. Because of the conflict resolution strategy of the interpreter, the third rule is only executed if the first two are not applicable, which essentially resets both symbols.
IF enemy AND health_low THEN retreat IF enemy AND NOT distance_close THEN pursue IF enemy THEN dodge IF true THEN NOT retreat AND NOT pursue AND NOT dodge
The second chunk of production rules deal with low-level movement. The order of the rules is much more important in this chunk. The obstacle avoidance behavior has the highest priority, although it is only applied when the enemy is present. This is because it's one of the few cases where the animat is not necessarily moving in the direction of travel — focusing on the enemy instead. When looking forwards, the collision prevention behavior does a better job of getting out of trouble instead.
The other behaviors are applied directly according to the tactical decisions that were already made by the first chunk. By default, the animat moves forwards so the travel in determined by the view control in the next chunk.
IF collision AND enemy THEN move_avoid IF retreat THEN move_flee IF pursue THEN move_seek IF dodge THEN move_side IF true THEN move_forward
The third chunk is used for weapon selection. The decisions are very simple, based on distance only. Each rule has two symbols in its body so that there's a backup weapon if one is out of ammo. If both weapons are fully loaded, there is an implicit rank in the choice. The weapons whose C++ effectors are declared last are used in priority over the previous ones.
IF enemy AND distance_far THEN use_rocketlauncher AND use_railgun IF enemy AND NOT distance_far THEN use_chaingun AND use_hyperblaster
The fourth chunk of production rules tackles view control. This is more complex than other chunks because it's implicitly responsible for controlling movement in most cases. (When the movement chunk specifies a forward move, the animat goes wherever it's looking.)
The first rule forces the animat to turn towards the enemy and fire whenever possible. In combat, this is has the highest priority. The next three rules are for collision prevention. If there's an obstacle in front, turn around/left/right depending on the presence of other obstacles on the side. The following two rules are for gathering armor and health items if they are required, and the final rule causes the animat to wander around.
IF enemy THEN look_enemy AND fire IF obstacle_front AND obstacle_left AND obstacle_right THEN look_behind IF obstacle_front AND obstacle_left THEN look_right IF obstacle_front AND obstacle_right THEN look_left IF NOT health_full AND health_item THEN look_health IF NOT armor_full AND armor_item THEN look_armor IF true THEN look_around
The rules printed here are pretty-printed versions of the source XML file. This is done with a XSLT stylesheet. The process of converting these rules back to XML is merely an exercise in syntax.
This section presents some of the problems with the implementation. Some are trivial to fix, and are left to the reader to change. Other issues have much deeper consequences, and require a major redesign.
| Tip |
|---|---|
A great way to test the behaviors is to disable weapons, as fights finish very quickly when death is an option. To do that, we can remove part of the rule body that orders the animat to fire (in Knowledge.xml) or editing the C++ code. | |
The weapon selection policy is satisfactory, but often happens very erratically. As two players get closer, the conditions change so the RBS suggests a different weapon. There is no concept of time stored within the working memory, so the new weapon gets selected immediately.
There are some cases where the collision detection does not work perfectly, notably when the animats hit small ledges and inclined ceilings at the same time. This could be considered as a bug, but a better approach would use a backup strategy. Instead of relying on collision feedback, the physics interface can be used to track relative movement (aka. dead reckoning). When this no movement is detected and a request was made, then a collision must have occured. A suitable response would be to jump (assuming it's a ledge that wasn't detected) and move in a different direction.
The obstacle distance sensors are capable of detecting ledges. This is very useful for preventing animats from falling off. However, they occasionally do fall off because they only check a few steps ahead, and they travel at full speed. When this happens, the sensors detect a gap and all return obstacles. This causes the bot to turn around to avoid them, thereby spinning in the fall. A solution to this would check the state interface to determine if the animat is in the air. In that case, no turning would be suggested.
With the rules listed, the animat only tries to collect health and armor. It turns out that most good deathmatch levels have lots of ammo and weapons, so the animats collect them by chance when wandering around. The AI could easily be extended to include collecting behaviours for these other objects too.
The working memory stores boolean symbols only. Using booleans to store data is somewhat limiting (our RBS can't count for example). Firstly, using a large array of symbols isn't particuraly organised. There are extensions to rule-based systems that use the object-attribute-value paradigm, which provides a more object oriented structure. Using other types of values like integers, strings and floats also extends the knowledge representation.
A consequence of extending the knowledge representation is that more complex operators are required. Currently, arbitrary boolean statements can be expressed using conjunction (AND), negation (NOT) and, indirectly, disjunction (OR) between rules. Different representations in the working memory would require integer or floating point algebra. This makes the RBS more powerful at the cost of complexity of implementation and intuitiveness.
In more practical terms, the implementation is not ideally suited to deal with separate code blocks. The rule matching phase is also linear, executing in O(n) instead of O(log n). And finally, the implementation requires that all symbols be declared before the rules are loaded and the so that the strings can be optimised out. These issues are subject to change in future releases.
RBS are extremely flexible techniques, capable of performing low-level control as well as decision making. Once the rulebase is in place, adding new behaviors is relatively easy as rules are modular. RBS are very simple to implement and understand, which makes them easy to extend and customize according to the problem at hand. They are also data-driven (declarative knowledge), which makes them an ideal lightweight alternative for scripting languages — as long as not too many language feature are not required. (RBS are at their best when they retain syntactic and semantic simplicity.)
In the next issue, we'll be looking at applying neural networks to this very same problem. Be sure to sign up to the mailing list to be notified in advance of its publication:
Be sure to check out chapters 11 and 12 of the book AI Game Development: Synthetic Creatures with Learning and Reactive Behaviors for more in depth theory, and tips on using RBS in practice.
Happy AI coding!
