Researching Different AI Techniques - Behaviour Trees (Part 3)
When designing AI for video games, they must act in an intelligent way while carrying out their tasks and behaviours. Originally the way this was done was using finite-state machines (FSMs) which are an “architectural structure used to encapsulate the behaviour of discrete states” (Graham, 2017). FSMs are still widely used within the games industry but are suited towards games that have less intensive AI. This is because as an FSM grows they begin to become unmanageable as each state needs to be able to transition with all other states, and if another state is added later into production, or one is removed the state transitions would need to be adjusted across the project. Although this problem can be slightly mitigated with the use of a hierarchal finite-state machine (HFSM) Which allow you to create transitions “once to super-states rather than each state individually.” (Champandard, 1, 2007) Helping to reduce the amount of redundant transitions.
Behaviour Trees (BTs) have become widely used across the games industry, this is due to their “modularity, reactiveness and scalability” (Zhang et al., 2018). Unlike FSMs to modify a BT it is as simple as adjusting the order of nodes or adding in a new parent node rather than having to adjust all the transitions and states as in an FSM.
There are four main types of nodes in a BT these are the Root Node which is a node that has no parents and is ticked at each update step of the game engine. Once the root node is ticked it will search through all the children nodes in a depth-first search method until it reaches a leaf node that returns success all the way up the tree. Another type of node is a Selector Node returns true upon the first child that returns a success, the selector nodes counterpart is the Sequence Node which will only return a success if all its children succeed. The final main node is the Leaf / Action node this is where behaviours are executed, such as playing animations, moving the agent or performing conditional checks.
The above images depicts a simple behaviour tree, this tree has a root node, shown as a ?, two selector nodes shown as a à and four leaf nodes (with no children). A tree searches in order of child addition (except in the case of a random selector and sequence nodes). When shown visually as in the above image, this is from left to right. This example will first check “Is door open?”. If this returns a success, then the agent will attempt “Move into room”. If this is deemed a success then the whole tree is a success, if either of these actions return a failure the next sequence is tried.
There are more types of nodes that can be used within a behaviour tree such as a Decorator Node which has only one child and acts depending on the result. Common uses for a decorator node are an Inverter Node which will flip the result return by its child node, and a Repeater Node which will recall its child nodes by a specified X amount of times.
There are many ways to extend the functionality of BTs to improve them and address any requirements needed for a game.
An example of a BT extension is the Hinted-Execution Behaviour Tree (HeBT). These are used on top of a behaviour tree and do not need much modification to implement. They act by sending information down to the lower levels called hints. HeBTs are layered ontop of the original BT and are controlled by a Behaviour Controller. “HeBTs allow generating low-risk prototypes of behavior trees in a way that allows teams to try new ideas at final stages” (Sekhavat, 2016).
Reference List
[1] Champandard, A. 1. (2007). The Gist of Hierarchical FSM | AiGameDev.com. [online] Aigamedev.com. Available at: http://aigamedev.com/open/article/hfsm-gist/ [Accessed 11 Nov. 2018].
[2] Champandard, A. 2. (2007). Choosing a Hierarchical FSM or a Hierarchy of Nested FSMs? | AiGameDev.com. [online] Aigamedev.com. Available at: http://aigamedev.com/open/article/hierarchical-or-nested-fsm/ [Accessed 15 Nov. 2018].
[3] Graham, D. (2017). “A Reusable, Light-Weight Finite-State Machine” in Game AI Pro 3 ed by S. Rabin. Boca Raton, FL: CRC Press 2017, pp 159-166.
[4] Samek, M. (2016). Introduction to Hierarchical State Machines (HSMs). [online] Barr Group. Available at: https://barrgroup.com/Embedded-Systems/How-To/Introduction-Hierarchical-State-Machines [Accessed 12 Nov. 2018].
[5] Sekhavat, Y. (2016). Behavior Trees for Computer Games. International Journal on Artificial Intelligence Tools, 26(02), pp.1-27.
[6] Zhang, Q., Yao, J., Yin, Q. and Zha, Y. (2018). Learning Behavior Trees for Autonomous Agents with Hybrid Constraints Evolution. Applied Sciences, 8(7), p.1077.
Behaviour Trees (BTs) have become widely used across the games industry, this is due to their “modularity, reactiveness and scalability” (Zhang et al., 2018). Unlike FSMs to modify a BT it is as simple as adjusting the order of nodes or adding in a new parent node rather than having to adjust all the transitions and states as in an FSM.
 |
| (Sekhavat, 2016) |
There are four main types of nodes in a BT these are the Root Node which is a node that has no parents and is ticked at each update step of the game engine. Once the root node is ticked it will search through all the children nodes in a depth-first search method until it reaches a leaf node that returns success all the way up the tree. Another type of node is a Selector Node returns true upon the first child that returns a success, the selector nodes counterpart is the Sequence Node which will only return a success if all its children succeed. The final main node is the Leaf / Action node this is where behaviours are executed, such as playing animations, moving the agent or performing conditional checks.
The above images depicts a simple behaviour tree, this tree has a root node, shown as a ?, two selector nodes shown as a à and four leaf nodes (with no children). A tree searches in order of child addition (except in the case of a random selector and sequence nodes). When shown visually as in the above image, this is from left to right. This example will first check “Is door open?”. If this returns a success, then the agent will attempt “Move into room”. If this is deemed a success then the whole tree is a success, if either of these actions return a failure the next sequence is tried.
There are more types of nodes that can be used within a behaviour tree such as a Decorator Node which has only one child and acts depending on the result. Common uses for a decorator node are an Inverter Node which will flip the result return by its child node, and a Repeater Node which will recall its child nodes by a specified X amount of times.
There are many ways to extend the functionality of BTs to improve them and address any requirements needed for a game.
An example of a BT extension is the Hinted-Execution Behaviour Tree (HeBT). These are used on top of a behaviour tree and do not need much modification to implement. They act by sending information down to the lower levels called hints. HeBTs are layered ontop of the original BT and are controlled by a Behaviour Controller. “HeBTs allow generating low-risk prototypes of behavior trees in a way that allows teams to try new ideas at final stages” (Sekhavat, 2016).
Reference List
[1] Champandard, A. 1. (2007). The Gist of Hierarchical FSM | AiGameDev.com. [online] Aigamedev.com. Available at: http://aigamedev.com/open/article/hfsm-gist/ [Accessed 11 Nov. 2018].
[2] Champandard, A. 2. (2007). Choosing a Hierarchical FSM or a Hierarchy of Nested FSMs? | AiGameDev.com. [online] Aigamedev.com. Available at: http://aigamedev.com/open/article/hierarchical-or-nested-fsm/ [Accessed 15 Nov. 2018].
[3] Graham, D. (2017). “A Reusable, Light-Weight Finite-State Machine” in Game AI Pro 3 ed by S. Rabin. Boca Raton, FL: CRC Press 2017, pp 159-166.
[4] Samek, M. (2016). Introduction to Hierarchical State Machines (HSMs). [online] Barr Group. Available at: https://barrgroup.com/Embedded-Systems/How-To/Introduction-Hierarchical-State-Machines [Accessed 12 Nov. 2018].
[5] Sekhavat, Y. (2016). Behavior Trees for Computer Games. International Journal on Artificial Intelligence Tools, 26(02), pp.1-27.
[6] Zhang, Q., Yao, J., Yin, Q. and Zha, Y. (2018). Learning Behavior Trees for Autonomous Agents with Hybrid Constraints Evolution. Applied Sciences, 8(7), p.1077.