el muchacho Comfortably Numb | Bon sinon, pour ceux que ça intéresse, une implémentation du BehaviourTree en C++11 (amélioration d'une implémentation trouvée sur le net). WIP vaguement débogué, à utiliser à vos risques et périls : BehaviourTree.h
Code :
- #pragma once
- #include <iostream>
- #include <list>
- #include <vector>
- #include <stack>
- #include <initializer_list>
- #include <string>
- #include <cstdlib>
- #include <chrono>
- #include <algorithm>
- #include <sstream>
- #include <future>
- /// Implementation of the Behavior Tree design pattern
- ///
- /// cf http://www.gamasutra.com/blogs/Chr [...] y_work.php
- /// and http://guineashots.com/2014/07/25/ [...] es-part-1/
- class BehaviourTree {
- public:
- enum Status {
- ERROR = -1,
- FAILURE = 0,
- SUCCESS = 1,
- RUNNING = 2 // not used yet
- };
- // This class represents each node in the behaviour tree.
- class Node {
- public:
- Node() {}
- Node(const std::string name) : _name(name) {}
- virtual Status run() = 0;
- const std::string getName() const { return _name; }
- protected:
- const std::string _name;
- };
- // This type of Node follows the Composite Pattern, containing a list of other Nodes.
- class CompositeNode : public Node {
- 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);
- }
- };
- // The generic Selector implementation
- // If one child succeeds, the Select succeeds and quits immediately.
- // FAILURE only if all children fail. Equivalent of a logical OR
- class Select : public CompositeNode {
- public:
- virtual Status run() override {
- for (Node* child : getChildren()) {
- // If one child succeeds, the entire operation run() succeeds. Failure only if all children fail.
- const Status s = child->run();
- if (s != FAILURE) {
- return s;
- }
- }
- return FAILURE; // All children failed so the entire run() operation fails.
- }
- };
- // The generic Sequence implementation.
- // If one child fails, then the entire sequence fails and quits immediately.
- // SUCCESS only if all children succeed. Equivalent of a logical AND.
- class Sequence : public CompositeNode {
- public:
- virtual Status run() override {
- for (Node* child : getChildren()) {
- // If one child fails, then enter operation run() fails. Success only if all children succeed.
- const Status s = child->run();
- if (s != SUCCESS) {
- return s;
- }
- }
- return SUCCESS; // All children suceeded, so the entire run() operation succeeds.
- }
- };
- // A Decorator adds a functionality to its child node.
- // Function is either to transform the Status it receives from the child,
- // to terminate the child, or repeat the processing of the child, depending on the type of decorator node.
- class DecoratorNode : public Node {
- private:
- Node* child; // Only one child allowed
- protected:
- Node* getChild() const { return child; }
- public:
- void setChild(Node* newChild) { child = newChild; }
- };
- // Root of a BehaviourTree
- class Root : public DecoratorNode {
- private:
- friend class BehaviourTree;
- virtual Status run() override {
- Status s = getChild()->run();
- while (s == RUNNING)
- s = getChild()->run();
- return s;
- }
- };
- // Negates the Status 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.
- class Invert : public DecoratorNode {
- private:
- virtual Status run() override {
- Status s = getChild()->run();
- switch (s)
- {
- case SUCCESS: return FAILURE;
- case FAILURE: return SUCCESS;
- default: return s;
- }
- }
- };
- // 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.
- class Succeed : public DecoratorNode {
- private:
- virtual Status run() override {
- Status s = getChild()->run();
- if (s == ERROR || s == RUNNING)
- return s;
- return SUCCESS;
- }
- };
- // 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.
- class Fail : public DecoratorNode {
- private:
- virtual Status run() override {
- Status s = getChild()->run();
- if (s == ERROR || s == RUNNING)
- return s;
- return FAILURE;
- }
- };
- // A repeater will reprocess its child node each time its child returns a Status.
- // 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.
- class Repeat : public DecoratorNode {
- public:
- Repeat(int num = NOT_FOUND) : numRepeats(num) {} // By default, never terminate.
- private:
- int numRepeats;
- static const int NOT_FOUND = -1;
- virtual Status run() override {
- if (numRepeats == NOT_FOUND)
- while (true) getChild()->run();
- else {
- for (int i = 0; i < numRepeats - 1; i++)
- getChild()->run();
- return getChild()->run();
- }
- }
- };
- // Execute its child in asynchronously (in a separate thread),
- // regularly yielding RUNNNING until it reaches its final Status
- class Async : public DecoratorNode {
- public:
- Async(std::chrono::milliseconds poolTime = std::chrono::milliseconds(10)) : _statusPoolTime(poolTime) {}
- private:
- std::chrono::milliseconds _statusPoolTime;
- virtual Status run() override {
- std::future<Status> fut = std::async(std::launch::async, [&] {
- return getChild()->run();
- });
- // if no answer within time delay
- if (fut.wait_for(_statusPoolTime) == std::future_status::timeout)
- return RUNNING;
- return fut.get();
- }
- };
- // Insert a delay in msec and return SUCCESS
- class Sleep : public DecoratorNode {
- Sleep(const std::chrono::milliseconds msec = std::chrono::milliseconds(0)) : _msec(msec) {}
- private:
- std::chrono::milliseconds _msec;
- virtual Status run() override {
- std::this_thread::sleep_for(_msec);
- return SUCCESS;
- }
- };
- // Like a repeater, these decorators will continue to reprocess their child.
- // That is until the child finally returns the expected status, at which point the repeater will return the status to its parent.
- // The expected status must be either SUCCESS or FAILURE.
- class RepeatUntil : public DecoratorNode {
- public:
- RepeatUntil(Status s) : _exitStatus(s) {}
- private:
- Status _exitStatus;
- virtual Status run() override {
- Status s = getChild()->run();
- while (s != _exitStatus && s != ERROR && s != RUNNING) {
- s = getChild()->run();
- }
- return s;
- }
- };
- /// The following are useful nodes
- // Stack nodes
- 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) {}
- };
- // Specific type of leaf (hence has no child).
- template <typename T>
- class PushToStack : public StackNode<T> {
- private:
- T*& item;
- public:
- PushToStack(T*& t, std::stack<T*>& s) : StackNode<T>(s), item(t) {}
- private:
- virtual Status run() override {
- this->stack.push(item);
- return SUCCESS;
- }
- };
- // Specific type of leaf (hence has no child).
- template <typename T>
- class GetStack : public StackNode<T> {
- 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 Status run() override {
- this->stack = obtainedStack;
- if (object)
- this->stack.push(object);
- return SUCCESS;
- }
- };
- // Specific type of leaf (hence has no child).
- template <typename T>
- class PopFromStack : public StackNode<T> {
- private:
- T*& item;
- public:
- PopFromStack(T*& t, std::stack<T*>& s) : StackNode<T>(s), item(t) {}
- private:
- virtual Status run() override {
- if (this->stack.empty())
- return FAILURE;
- item = this->stack.top();
- // template specialization with T = Door needed for this line actually
- std::cout << "Trying to get through door #" << item->doorNumber << "." << std::endl;
- this->stack.pop();
- return SUCCESS;
- }
- };
- // Specific type of leaf (hence has no child).
- template <typename T>
- class StackIsEmpty : public StackNode<T> {
- public:
- StackIsEmpty(std::stack<T*>& s) : StackNode<T>(s) {}
- private:
- virtual Status run() override {
- if (this->stack.empty())
- return SUCCESS;
- else
- return FAILURE;
- }
- };
- // Specific type of leaf (hence has no child).
- template <typename T>
- class SetVariable : public BehaviourTree::Node {
- private:
- T*& variable, *& object; // Must use reference to pointer to work correctly.
- public:
- SetVariable(T*& t, T*& obj) : variable(t), object(obj) {}
- virtual Status run() override {
- variable = object;
- // template specialization with T = Door needed for this line actually
- std::cout << "The door that was used to get in is door #" << variable->doorNumber << "." << std::endl;
- return SUCCESS;
- };
- };
- // Specific type of leaf (hence has no child).
- template <typename T>
- class IsNull : public BehaviourTree::Node {
- private:
- T*& object; // Must use reference to pointer to work correctly.
- public:
- IsNull(T*& t) : object(t) {}
- virtual Status run() override {
- if (object == nullptr)
- return SUCCESS;
- else
- return FAILURE;
- }
- };
- public:
- BehaviourTree() : root(new Root) {}
- void setRootChild(Node* rootChild) const { root->setChild(rootChild); }
- Status run() const { return root->run(); }
- private:
- Root* root;
- };
| BehaviourTree.cpp
Code :
- // BehaviorTree_test.cpp : Defines the entry point for the console application.
- //
- #include "stdafx.h"
- #include "BehaviourTree.h"
- #include <iostream>
- #include <list>
- #include <vector>
- #include <stack>
- #include <initializer_list>
- #include <string>
- #include <cstdlib>
- #include <ctime>
- #include <algorithm>
- #include <sstream>
- //
- // http://www.gamasutra.com/blogs/Chr [...] y_work.php
- 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 BehaviourTree::Status run() override {
- std::this_thread::sleep_for(std::chrono::milliseconds(500));
- if (std::rand() % 100 < probabilityOfSuccess) {
- std::cout << name << " succeeded." << std::endl;
- return BehaviourTree::SUCCESS;
- }
- std::cout << name << " failed." << std::endl;
- return BehaviourTree::FAILURE;
- }
- };
- 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::Select selector;
- BehaviourTree::Invert inverter[2];
- BehaviourTree::Succeed succeeder;
- BehaviourTree::RepeatUntil untilFail(BehaviourTree::FAILURE);
- 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);
- BehaviourTree::Async async;
- // Probabilities of success
- DoorAction walkToDoor("Walk to door", 99),
- openDoor("Open door", 12),
- unlockDoor("Unlock door", 25),
- smashDoor("Smash door", 60),
- walkThroughDoor("Walk through door", 85),
- closeDoor("Close door", 100);
- // Build the tree (last diagram of
- // http://www.gamasutra.com/blogs/Chr [...] y_work.php )
- 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(&async);
- async.setChild(&sequence[2]);
- sequence[2].addChildren({ &walkToDoor, &selector, &walkThroughDoor, &succeeder, &setVariable });
- selector.addChildren({ &openDoor, &unlockDoor, &smashDoor });
- succeeder.setChild(&closeDoor);
- if (behaviorTree.run() == BehaviourTree::SUCCESS)
- std::cout << "Congratulations! You made it into the building!" << std::endl;
- else
- std::cout << "Sorry. You have failed to enter the building." << std::endl;
- }
| edit: j'ai un bug avec l'asynchronisme, le programme devrait s'arrêter avec "Congratulations" une fois qu'on a fermé la porte, et pas continuer... ça devrait pas être trop difficile à deboguer Message édité par el muchacho le 20-01-2016 à 08:14:19 ---------------
Les aéroports où il fait bon attendre, voila un topic qu'il est bien
|