incl/BrainTree.h

   1 // BrainTree - A C++ behavior tree single header library.
   2 // Copyright 2015-2018 Par Arvidsson. All rights reserved.
   3 // Licensed under the MIT license (https://github.com/arvidsson/BrainTree/blob/master/LICENSE).
   4
   5 #pragma once
   6
   7 #include <memory>
   8 #include <vector>
   9 #include <string>
  10 #include <unordered_map>
  11 #include <cassert>
  12
  13 namespace BrainTree
  14 {
  15
  16 class Node
  17 {
  18 public:
  19     enum class Status
  20     {
  21         Invalid,
  22         Success,
  23         Failure,
  24         Running,
  25     };
  26
  27     virtual ~Node() {}
  28
  29     virtual Status update() = 0;
  30     virtual void initialize() {}
  31     virtual void terminate(Status s) {}
  32
  33     Status tick()
  34     {
  35         if (status != Status::Running) {
  36             initialize();
  37         }
  38
  39         status = update();
  40
  41         if (status != Status::Running) {
  42             terminate(status);
  43         }
  44
  45         return status;
  46     }
  47
  48     bool isSuccess() const { return status == Status::Success; }
  49     bool isFailure() const { return status == Status::Failure; }
  50     bool isRunning() const { return status == Status::Running; }
  51     bool isTerminated() const { return isSuccess() || isFailure(); }
  52
  53     void reset() { status = Status::Invalid; }
  54
  55     using Ptr = std::shared_ptr<Node>;
  56
  57 protected:
  58     Status status = Status::Invalid;
  59 };
  60
  61 class Composite : public Node
  62 {
  63 public:
  64     Composite() : it(children.begin()) {}
  65     virtual ~Composite() {}
  66
  67     void addChild(Node::Ptr child) { children.push_back(child); }
  68     bool hasChildren() const { return !children.empty(); }
  69
  70 protected:
  71     std::vector<Node::Ptr> children;
  72     std::vector<Node::Ptr>::iterator it;
  73 };
  74
  75 class Decorator : public Node
  76 {
  77 public:
  78     virtual ~Decorator() {}
  79
  80     void setChild(Node::Ptr node) { child = node; }
  81     bool hasChild() const { return child != nullptr; }
  82
  83 protected:
  84     Node::Ptr child = nullptr;
  85 };
  86
  87 class Blackboard
  88 {
  89 public:
  90     void setBool(std::string key, bool value) { bools[key] = value; }
  91     bool getBool(std::string key)
  92     {
  93         if (bools.find(key) == bools.end()) {
  94             bools[key] = false;
  95         }
  96         return bools[key];
  97     }
  98     bool hasBool(std::string key) const { return bools.find(key) != bools.end(); }
  99
 100     void setInt(std::string key, int value)  { ints[key] = value; }
 101     int getInt(std::string key)
 102     {
 103         if (ints.find(key) == ints.end()) {
 104             ints[key] = 0;
 105         }
 106         return ints[key];
 107     }
 108     bool hasInt(std::string key) const  { return ints.find(key) != ints.end(); }
 109
 110     void setFloat(std::string key, float value)  { floats[key] = value; }
 111     float getFloat(std::string key)
 112     {
 113         if (floats.find(key) == floats.end()) {
 114             floats[key] = 0.0f;
 115         }
 116         return floats[key];
 117     }
 118     bool hasFloat(std::string key) const  { return floats.find(key) != floats.end(); }
 119
 120     void setDouble(std::string key, double value)  { doubles[key] = value; }
 121     double getDouble(std::string key)
 122     {
 123         if (doubles.find(key) == doubles.end()) {
 124             doubles[key] = 0.0f;
 125         }
 126         return doubles[key];
 127     }
 128     bool hasDouble(std::string key) const  { return doubles.find(key) != doubles.end(); }
 129
 130     void setString(std::string key, std::string value)  { strings[key] = value; }
 131     std::string getString(std::string key)
 132     {
 133         if (strings.find(key) == strings.end()) {
 134             strings[key] = "";
 135         }
 136         return strings[key];
 137     }
 138     bool hasString(std::string key) const  { return strings.find(key) != strings.end(); }
 139
 140     using Ptr = std::shared_ptr<Blackboard>;
 141
 142 protected:
 143     std::unordered_map<std::string, bool> bools;
 144     std::unordered_map<std::string, int> ints;
 145     std::unordered_map<std::string, float> floats;
 146     std::unordered_map<std::string, double> doubles;
 147     std::unordered_map<std::string, std::string> strings;
 148 };
 149
 150 class Leaf : public Node
 151 {
 152 public:
 153     Leaf() {}
 154     virtual ~Leaf() {}
 155     Leaf(Blackboard::Ptr blackboard) : blackboard(blackboard) {}
 156
 157     virtual Status update() = 0;
 158
 159 protected:
 160     Blackboard::Ptr blackboard;
 161 };
 162
 163 class BehaviorTree : public Node
 164 {
 165 public:
 166     BehaviorTree() : blackboard(std::make_shared<Blackboard>()) {}
 167     BehaviorTree(const Node::Ptr &rootNode) : BehaviorTree() { root = rootNode; }
 168
 169     Status update() { return root->tick(); }
 170
 171     void setRoot(const Node::Ptr &node) { root = node; }
 172     Blackboard::Ptr getBlackboard() const { return blackboard; }
 173
 174 private:
 175     Node::Ptr root = nullptr;
 176     Blackboard::Ptr blackboard = nullptr;
 177 };
 178
 179 template <class Parent>
 180 class DecoratorBuilder;
 181
 182 template <class Parent>
 183 class CompositeBuilder
 184 {
 185 public:
 186     CompositeBuilder(Parent* parent, Composite* node) : parent(parent), node(node) {}
 187
 188     template <class NodeType, typename... Args>
 189     CompositeBuilder<Parent> leaf(Args... args)
 190     {
 191         auto child = std::make_shared<NodeType>((args)...);
 192         node->addChild(child);
 193         return *this;
 194     }
 195
 196     template <class CompositeType, typename... Args>
 197     CompositeBuilder<CompositeBuilder<Parent>> composite(Args... args)
 198     {
 199         auto child = std::make_shared<CompositeType>((args)...);
 200         node->addChild(child);
 201         return CompositeBuilder<CompositeBuilder<Parent>>(this, (CompositeType*)child.get());
 202     }
 203
 204     template <class DecoratorType, typename... Args>
 205     DecoratorBuilder<CompositeBuilder<Parent>> decorator(Args... args)
 206     {
 207         auto child = std::make_shared<DecoratorType>((args)...);
 208         node->addChild(child);
 209         return DecoratorBuilder<CompositeBuilder<Parent>>(this, (DecoratorType*)child.get());
 210     }
 211
 212     Parent& end()
 213     {
 214         return *parent;
 215     }
 216
 217 private:
 218     Parent * parent;
 219     Composite* node;
 220 };
 221
 222 template <class Parent>
 223 class DecoratorBuilder
 224 {
 225 public:
 226     DecoratorBuilder(Parent* parent, Decorator* node) : parent(parent), node(node) {}
 227
 228     template <class NodeType, typename... Args>
 229     DecoratorBuilder<Parent> leaf(Args... args)
 230     {
 231         auto child = std::make_shared<NodeType>((args)...);
 232         node->setChild(child);
 233         return *this;
 234     }
 235
 236     template <class CompositeType, typename... Args>
 237     CompositeBuilder<DecoratorBuilder<Parent>> composite(Args... args)
 238     {
 239         auto child = std::make_shared<CompositeType>((args)...);
 240         node->setChild(child);
 241         return CompositeBuilder<DecoratorBuilder<Parent>>(this, (CompositeType*)child.get());
 242     }
 243
 244     template <class DecoratorType, typename... Args>
 245     DecoratorBuilder<DecoratorBuilder<Parent>> decorator(Args... args)
 246     {
 247         auto child = std::make_shared<DecoratorType>((args)...);
 248         node->setChild(child);
 249         return DecoratorBuilder<DecoratorBuilder<Parent>>(this, (DecoratorType*)child.get());
 250     }
 251
 252     Parent& end()
 253     {
 254         return *parent;
 255     }
 256
 257 private:
 258     Parent * parent;
 259     Decorator* node;
 260 };
 261
 262 class Builder
 263 {
 264 public:
 265     template <class NodeType, typename... Args>
 266     Builder leaf(Args... args)
 267     {
 268         root = std::make_shared<NodeType>((args)...);
 269         return *this;
 270     }
 271
 272     template <class CompositeType, typename... Args>
 273     CompositeBuilder<Builder> composite(Args... args)
 274     {
 275         root = std::make_shared<CompositeType>((args)...);
 276         return CompositeBuilder<Builder>(this, (CompositeType*)root.get());
 277     }
 278
 279     template <class DecoratorType, typename... Args>
 280     DecoratorBuilder<Builder> decorator(Args... args)
 281     {
 282         root = std::make_shared<DecoratorType>((args)...);
 283         return DecoratorBuilder<Builder>(this, (DecoratorType*)root.get());
 284     }
 285
 286     Node::Ptr build()
 287     {
 288         assert(root != nullptr && "The Behavior Tree is empty!");
 289         auto tree = std::make_shared<BehaviorTree>();
 290         tree->setRoot(root);
 291         return tree;
 292     }
 293
 294 private:
 295     Node::Ptr root;
 296 };
 297
 298 // The Selector composite ticks each child node in order.
 299 // If a child succeeds or runs, the selector returns the same status.
 300 // In the next tick, it will try to run each child in order again.
 301 // If all children fails, only then does the selector fail.
 302 class Selector : public Composite
 303 {
 304 public:
 305     void initialize() override
 306     {
 307         it = children.begin();
 308     }
 309
 310     Status update() override
 311     {
 312         assert(hasChildren() && "Composite has no children");
 313
 314         while (it != children.end()) {
 315             auto status = (*it)->tick();
 316
 317             if (status != Status::Failure) {
 318                 return status;
 319             }
 320
 321             it++;
 322         }
 323
 324         return Status::Failure;
 325     }
 326 };
 327
 328 // The Sequence composite ticks each child node in order.
 329 // If a child fails or runs, the sequence returns the same status.
 330 // In the next tick, it will try to run each child in order again.
 331 // If all children succeeds, only then does the sequence succeed.
 332 class Sequence : public Composite
 333 {
 334 public:
 335     void initialize() override
 336     {
 337         it = children.begin();
 338     }
 339
 340     Status update() override
 341     {
 342         assert(hasChildren() && "Composite has no children");
 343
 344         while (it != children.end()) {
 345             auto status = (*it)->tick();
 346
 347             if (status != Status::Success) {
 348                 return status;
 349             }
 350
 351             it++;
 352         }
 353
 354         return Status::Success;
 355     }
 356 };
 357
 358 // The StatefulSelector composite ticks each child node in order, and remembers what child it prevously tried to tick.
 359 // If a child succeeds or runs, the stateful selector returns the same status.
 360 // In the next tick, it will try to run the next child or start from the beginning again.
 361 // If all children fails, only then does the stateful selector fail.
 362 class StatefulSelector : public Composite
 363 {
 364 public:
 365     Status update() override
 366     {
 367         assert(hasChildren() && "Composite has no children");
 368
 369         while (it != children.end()) {
 370             auto status = (*it)->tick();
 371
 372             if (status != Status::Failure) {
 373                 return status;
 374             }
 375
 376             it++;
 377         }
 378
 379         it = children.begin();
 380         return Status::Failure;
 381     }
 382 };
 383
 384 // The StatefulSequence composite ticks each child node in order, and remembers what child it prevously tried to tick.
 385 // If a child fails or runs, the stateful sequence returns the same status.
 386 // In the next tick, it will try to run the next child or start from the beginning again.
 387 // If all children succeeds, only then does the stateful sequence succeed.
 388 class MemSequence : public Composite
 389 {
 390 public:
 391     Status update() override
 392     {
 393         assert(hasChildren() && "Composite has no children");
 394
 395         while (it != children.end()) {
 396             auto status = (*it)->tick();
 397
 398             if (status != Status::Success) {
 399                 return status;
 400             }
 401
 402             it++;
 403         }
 404
 405         it = children.begin();
 406         return Status::Success;
 407     }
 408 };
 409
 410 class ParallelSequence : public Composite
 411 {
 412 public:
 413     ParallelSequence(bool successOnAll = true, bool failOnAll = true) : useSuccessFailPolicy(true), successOnAll(successOnAll), failOnAll(failOnAll) {}
 414     ParallelSequence(int minSuccess, int minFail) : minSuccess(minSuccess), minFail(minFail) {}
 415
 416     Status update() override
 417     {
 418         assert(hasChildren() && "Composite has no children");
 419
 420         int minimumSuccess = minSuccess;
 421         int minimumFail = minFail;
 422
 423         if (useSuccessFailPolicy) {
 424             if (successOnAll) {
 425                 minimumSuccess = children.size();
 426             }
 427             else {
 428                 minimumSuccess = 1;
 429             }
 430
 431             if (failOnAll) {
 432                 minimumFail = children.size();
 433             }
 434             else {
 435                 minimumFail = 1;
 436             }
 437         }
 438
 439         int total_success = 0;
 440         int total_fail = 0;
 441
 442         for (auto &child : children) {
 443             auto status = child->tick();
 444             if (status == Status::Success) {
 445                 total_success++;
 446             }
 447             if (status == Status::Failure) {
 448                 total_fail++;
 449             }
 450         }
 451
 452         if (total_success >= minimumSuccess) {
 453             return Status::Success;
 454         }
 455         if (total_fail >= minimumFail) {
 456             return Status::Failure;
 457         }
 458
 459         return Status::Running;
 460     }
 461
 462 private:
 463     bool useSuccessFailPolicy = false;
 464     bool successOnAll = true;
 465     bool failOnAll = true;
 466     int minSuccess = 0;
 467     int minFail = 0;
 468 };
 469
 470 // The Succeeder decorator returns success, regardless of what happens to the child.
 471 class Succeeder : public Decorator
 472 {
 473 public:
 474     Status update() override
 475     {
 476         child->tick();
 477         return Status::Success;
 478     }
 479 };
 480
 481 // The Failer decorator returns failure, regardless of what happens to the child.
 482 class Failer : public Decorator
 483 {
 484 public:
 485     Status update() override
 486     {
 487         child->tick();
 488         return Status::Failure;
 489     }
 490 };
 491
 492 // The Inverter decorator inverts the child node's status, i.e. failure becomes success and success becomes failure.
 493 // If the child runs, the Inverter returns the status that it is running too.
 494 class Inverter : public Decorator
 495 {
 496 public:
 497     Status update() override
 498     {
 499         auto s = child->tick();
 500
 501         if (s == Status::Success) {
 502             return Status::Failure;
 503         }
 504         else if (s == Status::Failure) {
 505             return Status::Success;
 506         }
 507
 508         return s;
 509     }
 510 };
 511
 512 // The Repeater decorator repeats infinitely or to a limit until the child returns success.
 513 class Repeater : public Decorator
 514 {
 515 public:
 516     Repeater(int limit = 0) : limit(limit) {}
 517
 518     void initialize() override
 519     {
 520         counter = 0;
 521     }
 522
 523     Status update() override
 524     {
 525         child->tick();
 526
 527         if (limit > 0 && ++counter == limit) {
 528             return Status::Success;
 529         }
 530
 531         return Status::Running;
 532     }
 533
 534 protected:
 535     int limit;
 536     int counter = 0;
 537 };
 538
 539 // The UntilSuccess decorator repeats until the child returns success and then returns success.
 540 class UntilSuccess : public Decorator
 541 {
 542 public:
 543     Status update() override
 544     {
 545         while (1) {
 546             auto status = child->tick();
 547
 548             if (status == Status::Success) {
 549                 return Status::Success;
 550             }
 551         }
 552     }
 553 };
 554
 555 // The UntilFailure decorator repeats until the child returns fail and then returns success.
 556 class UntilFailure : public Decorator
 557 {
 558 public:
 559     Status update() override
 560     {
 561         while (1) {
 562             auto status = child->tick();
 563
 564             if (status == Status::Failure) {
 565                 return Status::Success;
 566             }
 567         }
 568     }
 569 };
 570
 571 } // namespace BrainTree