Behaviour Tree

[prestokeys]

Behaviour trees are only about 10 years old. I was disappointed that not one single example code in C++ could be googled up. A whole bunch of theory and diagrams, but no fully compiling codes. So here I present some examples in C++ so that anyone who tries to google up a behaviour tree C++ example can stumble upon this thread. If my design is not proper, please let me know.

// Behaviour tree that models the behaviour of a person whose goal is to open a door.

#include <iostream>
#include <list>

/*

	    Root
             |
             |
  Selector (only one of these children need to succeed)  
       /             \
      /               \
     /                 \
Door is open?      Sequence (all of these children need to succeed)
(if door is                /           \
already open,             /             \
we are done)             /               \
                   Approach door      Open the door
                  (if this fails
                  then the door
                  cannot be opened)
*/

class Node {  // This class represents each node in the behaviour tree.
	public:
		virtual bool run() = 0;
};

class CompositeNode : public Node {  //  This type of Node follows the Composite Pattern, containing a list of other Nodes.
	private:
		std::list<Node*> children;
	public:
		const std::list<Node*>& getChildren() const {return children;}
		void addChild (Node* child) {children.emplace_back(child);}
};

class Selector : public CompositeNode {
	public:
		virtual bool run() override {
			for (Node* child : getChildren()) {  // The generic Selector implementation
				if (child->run())  // If one child succeeds, the entire operation run() succeeds.  Failure only results if all children fail.
					return true;
			}
			return false;  // All children failed so the entire run() operation fails.
		}
};

class Sequence : public CompositeNode {
	public:
		virtual bool run() override {
			for (Node* child : getChildren()) {  // The generic Sequence implementation.
				if (!child->run())  // If one child fails, then enter operation run() fails.  Success only results if all children succeed.
					return false;
			}
			return true;  // All children suceeded, so the entire run() operation succeeds.
		}
};

struct DoorStatus {
	bool doorIsOpen;
	int distanceToDoor;
};

class CheckIfDoorIsOpenTask : public Node {  // Each task will be a class (derived from Node of course).
	private:
		DoorStatus* status;
	public:
		CheckIfDoorIsOpenTask (DoorStatus* status) : status(status) {}
		virtual bool run() override {
			if (status->doorIsOpen == true)
				std::cout << "The person sees that the door is open." << std::endl;  // will return true
			else
				std::cout << "The person sees that the door is closed." << std::endl;  // will return false
			return status->doorIsOpen;
		}
};

class ApproachDoorTask : public Node {
	private:
		DoorStatus* status;
		bool obstructed;
	public:
		ApproachDoorTask (DoorStatus* status, bool obstructed) : status(status), obstructed(obstructed) {}
		virtual bool run() override {
			if (obstructed)
				return false;
			if (status->distanceToDoor > 0) {
				std::cout << "The person approaches the door." << std::endl;
				status->distanceToDoor--;  // thus run() is not a const function
				if (status->distanceToDoor > 1)
					std::cout << "The person is now " << status->distanceToDoor << " meters from the door." << std::endl;
				else if (status->distanceToDoor == 1)
					std::cout << "The person is now only one meter away from the door." << std::endl;
				else
					std::cout << "The person is at the door." << std::endl;
			}
			return true;
		}
};

class OpenDoorTask : public Node {
	private:
		DoorStatus* status;
	public:
		OpenDoorTask (DoorStatus* status) : status(status) {}
		virtual bool run() override {
			if (status->distanceToDoor > 0) {
				std::cout << "The person is still too far away from the door.  He cannot open the door." << std::endl;
				return false;	
			}
			status->doorIsOpen = true;  // run() not const because of this too
			std::cout << "The person opens the door." << std::endl;
			return true;
		}
};

int main() {
	Sequence *root = new Sequence, *sequence1 = new Sequence;  // Note that root can be either a Sequence or a Selector, since it has only one child.
	Selector* selector1 = new Selector;  // In general there will be several nodes that are Sequence or Selector, so they should be suffixed by an integer to distinguish between them.
	DoorStatus* doorStatus = new DoorStatus {false, 5};  // The door is initially closed and 5 meters away.
	CheckIfDoorIsOpenTask* checkOpen = new CheckIfDoorIsOpenTask (doorStatus);
	ApproachDoorTask* approach = new ApproachDoorTask (doorStatus, false);
	OpenDoorTask* open = new OpenDoorTask (doorStatus);
	
	root->addChild (selector1);
	
	selector1->addChild (checkOpen);
	selector1->addChild (sequence1);
	
	sequence1->addChild (approach);
	sequence1->addChild (open);
	
	while (!root->run())  // If the operation starting from the root fails, keep trying until it succeeds.
		std::cout << "--------------------" << std::endl;
	std::cout << std::endl << "Operation complete.  Behaviour tree exited." << std::endl;
	std::cin.get();
}

/*
Output:
The person sees that the door is closed.
The person approaches the door.
The person is now 4 meters from the door.
The person is still too far away from the door.  He cannot open the door.
--------------------
The person sees that the door is closed.
The person approaches the door.
The person is now 3 meters from the door.
The person is still too far away from the door.  He cannot open the door.
--------------------
The person sees that the door is closed.
The person approaches the door.
The person is now 2 meters from the door.
The person is still too far away from the door.  He cannot open the door.
--------------------
The person sees that the door is closed.
The person approaches the door.
The person is now only one meter away from the door.
The person is still too far away from the door.  He cannot open the door.
--------------------
The person sees that the door is closed.
The person approaches the door.
The person is at the door.
The person opens the door.

Operation complete.  Behaviour tree exited.
*/

[prestokeys]

"http://imagizer.imageshack.us/v2/150x100q90/540/BTUdjJ.jpg"

Here the behaviour tree simulates a person trying to escape a room. The tree is much bigger and deeper this time, so for brevity we will make the determination of success or failure simpler.
Note: The tree diagram picture above is too small to see. You can find it in the 7th picture in this website:
http://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

#include <iostream>
#include <list>
#include <vector>
#include <stack>
#include <initializer_list>
#include <string>
#include <cstdlib>
#include <ctime>
#include <algorithm>

class BehaviourTree {  // Note:  A proper copy constructor and assignment operator should be defined, since the implicit ones use shallow copies only.
	public:
		class Node {  // This class represents each node in the behaviour tree.
			public:
				virtual bool run() = 0;
		};
		
		class CompositeNode : public Node {  //  This type of Node follows the Composite Pattern, containing a list of other Nodes.
			private:
				std::vector<Node*> children;
			public:
				const std::vector<Node*>& getChildren() const {return children;}
				void addChild (Node* child) {children.emplace_back(child);}
				void addChildren (std::initializer_list<Node*>&& newChildren) {for (Node* child : newChildren) addChild(child);}
				template <typename CONTAINER>
				void addChildren (const CONTAINER& newChildren) {for (Node* child : newChildren) addChild(child);}
			protected:
				std::vector<Node*> childrenShuffled() const {std::vector<Node*> temp = children;  std::random_shuffle (temp.begin(), temp.end());  return temp;}
		};
		
		class Selector : public CompositeNode {
			public:
				virtual bool run() override {
					for (Node* child : getChildren()) {  // The generic Selector implementation
						if (child->run())  // If one child succeeds, the entire operation run() succeeds.  Failure only results if all children fail.
							return true;
					}
					return false;  // All children failed so the entire run() operation fails.
				}
		};
		
		class RandomSelector : public CompositeNode {  // RandomSelector operates as a Selector, but in a random order instead of from first child to last child.
			public:
				virtual bool run() override {
					for (Node* child : childrenShuffled()) {  // The order is shuffled
						if (child->run())
							return true;
					}
					return false;
				}
		};

		class Sequence : public CompositeNode {
			public:
				virtual bool run() override {
					for (Node* child : getChildren()) {  // The generic Sequence implementation.
						if (!child->run())  // If one child fails, then enter operation run() fails.  Success only results if all children succeed.
							return false;
					}
					return true;  // All children suceeded, so the entire run() operation succeeds.
				}
		};

		class Root : public Node {
			private:
				Node* child;
				friend class BehaviourTree;
				void setChild (Node* newChild) {child = newChild;}
				virtual bool run() override {return child->run();}
		};
	private:
		Root* root;
	public:
		BehaviourTree() : root(new Root) {}
		void setRootChild (Node* rootChild) const {root->setChild (rootChild);}
		bool run() const {return root->run();}
};

class Action : public BehaviourTree::Node {
	private:
		std::string name;
		int probabilityOfSuccess;
	public:
		Action (const std::string newName, int prob) : name(newName), probabilityOfSuccess(prob) {}
	private:
		virtual bool run() override {
			if (std::rand() % 100 < probabilityOfSuccess) {
				std::cout << name << " succeeded." << std::endl;
				return true;
			}
			std::cout << name << " failed." << std::endl;
			return false;
		}
};

int main() {
	std::srand(std::time(nullptr));
	BehaviourTree behaviorTree;
	BehaviourTree::Selector selector[3];
	BehaviourTree::Sequence sequence[4];
	Action walkToDoor ("Walk to door", 99), openDoor1 ("Open door", 15), unlockDoor ("Unlock door", 25), openDoor2 ("Open door after unlocking it", 99), smashDoor ("Smash door", 60), 
		walkThroughDoor ("Walk through door", 60), closeDoor ("Close door", 100), walkToWindow ("Walk to Window", 99), openWindow1 ("Open window", 70), unlockWindow ("Unlock window", 65),
		openWindow2 ("Open window after unlocking it", 85), smashWindow ("Smash window", 95), climbThroughWindow ("Climb through window", 85), closeWindow ("Close window", 100);
	
	behaviorTree.setRootChild (&selector[0]);
	selector[0].addChildren ({&sequence[0],&sequence[2]});
	sequence[0].addChildren ({&walkToDoor, &selector[1], &walkThroughDoor, &closeDoor});
	selector[1].addChildren ({&openDoor1, &sequence[1], &smashDoor});
	sequence[1].addChildren ({&unlockDoor, &openDoor2});
	sequence[2].addChildren ({&walkToWindow, &selector[2], &climbThroughWindow, &closeWindow});
	const std::list<BehaviourTree::Node*> nodes = {&openWindow1, &sequence[3], &smashWindow};
	selector[2].addChildren(nodes);
	sequence[3].addChildren ({&unlockWindow, &openWindow2});
	
	if (behaviorTree.run())
		std::cout << "Congratulations!  You made it out!" << std::endl;
	else
		std::cout << "Sorry.  You are trapped here for life." << std::endl;
}
/*
Possible outcome:

Walk to door succeeded.
Open door failed.
Unlock door failed.
Smash door failed.
Walk to Window succeeded.
Open window failed.
Unlock window failed.
Smash window succeeded.
Climb through window succeeded.
Close window succeeded.
Congratulations!  You made it out!
*/	

[prestokeys]

Last example. Tree diagram is the last one here: http://www.gamasutra.com/blogs/ChrisSimpson/20140717/221339/Behavior_trees_for_AI_How_they_work.php

#include <iostream>
#include <list>
#include <vector>
#include <stack>
#include <initializer_list>
#include <string>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <sstream>

class BehaviourTree {
	public:
		class Node {  // This class represents each node in the behaviour tree.
			public:
				virtual bool run() = 0;
		};
		
		class CompositeNode : public Node {  //  This type of Node follows the Composite Pattern, containing a list of other Nodes.
			private:
				std::vector<Node*> children;
			public:
				const std::vector<Node*>& getChildren() const {return children;}
				void addChild (Node* child) {children.emplace_back(child);}
				void addChildren (std::initializer_list<Node*>&& newChildren) {for (Node* child : newChildren) addChild(child);}
				template <typename CONTAINER>
				void addChildren (const CONTAINER& newChildren) {for (Node* child : newChildren) addChild(child);}
			protected:
				std::vector<Node*> childrenShuffled() const {std::vector<Node*> temp = children;  std::random_shuffle (temp.begin(), temp.end());  return temp;}
		};
		
		class Selector : public CompositeNode {
			public:
				virtual bool run() override {
					for (Node* child : getChildren()) {  // The generic Selector implementation
						if (child->run())  // If one child succeeds, the entire operation run() succeeds.  Failure only results if all children fail.
							return true;
					}
					return false;  // All children failed so the entire run() operation fails.
				}
		};
		
		class RandomSelector : public CompositeNode {  // RandomSelector operates as a Selector, but in a random order instead of from first child to last child (adds more unpredictability to the behaviour when a there is no clear preferred order of execution).
			public:
				virtual bool run() override {
					for (Node* child : childrenShuffled()) {  // The order is shuffled
						if (child->run())
							return true;
					}
					return false;
				}
		};

		class Sequence : public CompositeNode {
			public:
				virtual bool run() override {
					for (Node* child : getChildren()) {  // The generic Sequence implementation.
						if (!child->run())  // If one child fails, then enter operation run() fails.  Success only results if all children succeed.
							return false;
					}
					return true;  // All children suceeded, so the entire run() operation succeeds.
				}
		};
		
		class DecoratorNode : public Node {  // Function is either to transform the result it receives from its child node's status, to terminate the child, or repeat processing of the child, depending on the type of decorator node.
			private:
				Node* child;  // Only one child allowed
			protected:
				Node* getChild() const {return child;}
			public:
				void setChild (Node* newChild) {child = newChild;}
		};
		
		class Root : public DecoratorNode {
			private:
				friend class BehaviourTree;
				virtual bool run() override {return getChild()->run();}
		};

		class Inverter : public DecoratorNode {  // Inverts the result of the child. A child fails and it will return success to its parent, or a child succeeds and it will return failure to the parent.
			private:
				virtual bool run() override {return !getChild()->run();}
		};
		
		class Succeeder : public DecoratorNode {  // A succeeder will always return success, irrespective of what the child node actually returned. These are useful in cases where you want to process a branch of a tree where a failure is expected or anticipated, but you don’t want to abandon processing of a sequence that branch sits on.
			private:
				virtual bool run() override {getChild()->run();  return true;}
		};
		
		class Failer : public DecoratorNode {  // The opposite of a Succeeder, always returning fail.  Note that this can be achieved also by using an Inverter and setting its child to a Succeeder.
			private:
				virtual bool run() override {getChild()->run();  return false;}
		};
		
		class Repeater : public DecoratorNode {  // A repeater will reprocess its child node each time its child returns a result. These are often used at the very base of the tree, to make the tree to run continuously. Repeaters may optionally run their children a set number of times before returning to their parent.
			private:
				int numRepeats;
				static const int NOT_FOUND = -1;
				Repeater (int num = NOT_FOUND) : numRepeats(num) {}  // By default, never terminate.
				virtual bool run() override {
					if (numRepeats == NOT_FOUND)
						while (true) getChild()->run();
					else {
						for (int i = 0; i < numRepeats - 1; i++)
							getChild()->run();
						return getChild()->run();
					}
				}
		};
		
		class RepeatUntilFail : public DecoratorNode {  // Like a repeater, these decorators will continue to reprocess their child. That is until the child finally returns a failure, at which point the repeater will return success to its parent.
			private:
				virtual bool run() override {
					while (getChild()->run()) {}
						return true;
				}
		};
		
		template <typename T>
		class StackNode : public Node {
			protected:
				std::stack<T*>& stack;  // Must be reference to a stack to work.
				StackNode (std::stack<T*>& s) : stack(s) {}
		};
		
		template <typename T>
		class PushToStack : public StackNode<T> {  // Specific type of leaf (hence has no child).
			private:
				T*& item;
			public:
				PushToStack (T*& t, std::stack<T*>& s) : StackNode<T>(s), item(t) {}
			private:
				virtual bool run() override {
					this->stack.push(item);
					return true;
				}
		};
		
		template <typename T>
		class GetStack : public StackNode<T> {  // Specific type of leaf (hence has no child).
			private:
				const std::stack<T*>& obtainedStack;
				T* object;
			public:
				GetStack (std::stack<T*>& s, const std::stack<T*>& o, T* t = nullptr) : StackNode<T>(s), obtainedStack(o), object(t) {}
			private:
				virtual bool run() override {
					this->stack = obtainedStack;
					if (object)
						this->stack.push(object);
					return true;
				}	
		};

		template <typename T>
		class PopFromStack : public StackNode<T> {  // Specific type of leaf (hence has no child).
			private:
				T*& item;
			public:
				PopFromStack (T*& t, std::stack<T*>& s) : StackNode<T>(s), item(t) {}
			private:
				virtual bool run() override {
					if (this->stack.empty())
						return false;
					item = this->stack.top();
					std::cout << "Trying to get through door #" << item->doorNumber << "." << std::endl;  // template specialization with T = Door needed for this line actually
					this->stack.pop();
					return true;
				}
		};
		
		template <typename T>
		class StackIsEmpty : public StackNode<T> {  // Specific type of leaf (hence has no child).
			public:
				StackIsEmpty (std::stack<T*>& s) : StackNode<T>(s) {}
			private:
				virtual bool run() override {
					return this->stack.empty();
				}		
		};
		
		template <typename T>
		class SetVariable : public BehaviourTree::Node {  // Specific type of leaf (hence has no child).
			private:
				T *&variable, *&object;  // Must use reference to pointer to work correctly.
			public:
				SetVariable (T*& t, T*& obj) : variable(t), object(obj) {}
				virtual bool run() override {
					variable = object;
					std::cout << "The door that was used to get in is door #" << variable->doorNumber << "." << std::endl;  // template specialization with T = Door needed for this line actually
					return true;
				};
		};
		
		template <typename T>
		class IsNull : public BehaviourTree::Node {  // Specific type of leaf (hence has no child).
			private:
				T*& object;  // Must use reference to pointer to work correctly.
			public:
				IsNull (T*& t) : object(t) {}
				virtual bool run() override {return !object;}				
		};
	private:
		Root* root;
	public:
		BehaviourTree() : root(new Root) {}
		void setRootChild (Node* rootChild) const {root->setChild (rootChild);}
		bool run() const {return root->run();}
};

[prestokeys]

There are decorator nodes and a bunch of special leaf nodes that manipulates stacks. Here is the test of the class:

struct Door {
	int doorNumber;
};

class Building {
	private:
		std::stack<Door*> doors;
	public:
		Building (int numDoors) {initializeBuilding(numDoors);}
		const std::stack<Door*>& getDoors() const {return doors;}
	private:
		void initializeBuilding (int numDoors) {
			for (int i = 0; i < numDoors; i++)
				doors.push (new Door{numDoors - i});
		}
};

struct DataContext {  // Acts as a storage for arbitrary variables that are interpreted and altered by the nodes.
	std::stack<Door*> doors;
	Door* currentDoor;
	Door* usedDoor = nullptr;
};

class DoorAction : public BehaviourTree::Node {
	private:
		std::string name;
		int probabilityOfSuccess;
	public:
		DoorAction (const std::string newName, int prob) : name(newName), probabilityOfSuccess(prob) {}
	private:
		virtual bool run() override {
			if (std::rand() % 100 < probabilityOfSuccess) {
				std::cout << name << " succeeded." << std::endl;
				return true;
			}
			std::cout << name << " failed." << std::endl;
			return false;
		}
};

int main() {
	std::srand(std::time(nullptr));

	BehaviourTree behaviorTree;
	DataContext data;
	Building building(5);  // Building with 5 doors to get in.
	BehaviourTree::Sequence sequence[3];
	BehaviourTree::Selector selector;
	BehaviourTree::Inverter inverter[2];
	BehaviourTree::Succeeder succeeder;
	BehaviourTree::RepeatUntilFail untilFail;
	BehaviourTree::GetStack<Door> getDoorStackFromBuilding (data.doors, building.getDoors());
	BehaviourTree::PopFromStack<Door> popFromStack (data.currentDoor, data.doors);
	BehaviourTree::SetVariable<Door> setVariable (data.usedDoor, data.currentDoor);
	BehaviourTree::IsNull<Door> isNull (data.usedDoor);
	DoorAction walkToDoor ("Walk to door", 99), openDoor ("Open door", 15), unlockDoor ("Unlock door", 25), smashDoor ("Smash door", 60), walkThroughDoor ("Walk through door", 60), closeDoor ("Close door", 100);

	behaviorTree.setRootChild (&sequence[0]);
	sequence[0].addChildren ({&getDoorStackFromBuilding, &untilFail, &inverter[0]});
	untilFail.setChild (&sequence[1]);
	inverter[0].setChild (&isNull);
	sequence[1].addChildren ({&popFromStack, &inverter[1]});
	inverter[1].setChild (&sequence[2]);
	sequence[2].addChildren ({&walkToDoor, &selector, &walkThroughDoor, &succeeder, &setVariable});
	selector.addChildren ({&openDoor, &unlockDoor, &smashDoor});
	succeeder.setChild (&closeDoor);

	if (behaviorTree.run())
		std::cout << "Congratulations!  You made it into the building!" << std::endl;
	else
		std::cout << "Sorry.  You have failed to enter the building." << std::endl;
}

/*
Possible outcome:

Trying to get through door #1.
Walk to door succeeded.
Open door failed.
Unlock door failed.
Smash door succeeded.
Walk through door failed.
Trying to get through door #2.
Walk to door succeeded.
Open door succeeded.
Walk through door failed.
Trying to get through door #3.
Walk to door succeeded.
Open door failed.
Unlock door failed.
Smash door succeeded.
Walk through door succeeded.
Close door succeeded.
The door that was used to get in is door #3.
Congratulations!  You made it into the building!
*/

[jasonwynn10]

why is this a topic and not an article?

[prestokeys]

Because I'm not a professional programmer. I posted these examples only because no professional programmer has given any full code examples of behaviour trees, instead only explaining the diagrams and concepts since it is language-independent. So someone has to give examples in code for others to read. It is your choice whether to trust my examples or not, but they do at least compile and carry out the referred tree diagrams correctly. I also don't have my own website or blog. Others are welcome to give their own versions, because I don't think there is a fixed standard way to write the code. It's up to each individual to write up their versions to carry out the diagrams.

[jasonwynn10]

oh...ok but you don't have to be a pro to create an article.