1 /** 2 This module provides behavior tree operations inspired by 3 4 A. Marzinotto and M. Colledanchise and C. Smith and P. Ögren, Towards a unified behavior trees framework for robot 5 control, 6 7 and 8 9 Colledanchise, M; Ögren, P, How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior 10 Compositions, the Subsumption Architecture, and Decision Trees 11 12 The behavior tree simplifies and modularize complex state machine description by redefining nodes as tasks. Doing 13 so, the representation becomes a tree, whereas the state machine is generally a more complex graph. 14 15 The basic idea is the following: 16 There is a predefined well-known tree-internal ternary language. The decisions inside behavior tree are based on 17 this language. As a consequence, the importer of this package has to adopt the Ternary type inside his own code. 18 19 There are three kinds of nodes: root, intermediates, leafs. 20 A rooted, directed tree is defined, where the root has only one child. 21 Leaf nodes have no children but the user objects. User objects overload the function call operator. During the call 22 of the root, all inputs are passed down to the leaves of the tree and then further on, to the user defined objects 23 as input params of the opCall method. 24 25 The result of the opCall method is of Ternary type, analogue to the cited papers. 26 27 */ 28 29 /** Authors: Alexander Orlov */ 30 /** Copyright: Copyright (c) 2016- Alexander Orlov. All rights reserved. */ 31 /** License: https://opensource.org/licenses/MIT, MIT License. */ 32 module behaviortree; 33 import std.typecons; 34 import std.functional; 35 36 /// 37 debug 38 { 39 void process(T, U...)(auto ref T a, auto ref U args) @nogc 40 { 41 args[0] *= 10; 42 } 43 44 struct Functor 45 { 46 size_t value; 47 alias value this; 48 auto opCall(U, T...)(auto ref U callable, auto ref T args) @nogc 49 { 50 return callable(this, forward!(input[1..$])); 51 } 52 } 53 54 struct Leaf(T) 55 { 56 auto funn(U, V...)(auto ref U value, auto ref V args) @nogc 57 { 58 foreach(ref a; args) 59 value += a; 60 } 61 62 T opCall(U, A...)(auto ref U F, auto ref A args) @nogc 63 { 64 funn(forward!F, forward!args); 65 static assert(is(T == bool) || is(T == Ternary)); 66 static if(is(T == bool)) 67 { 68 if(F < 50) 69 return false; 70 else 71 return true; 72 } 73 else 74 { 75 if(F < 50) 76 return Ternary.no; 77 else if(F == 50) 78 return Ternary.unknown; 79 else 80 return Ternary.yes; 81 } 82 } 83 } 84 85 auto Not(T)(auto ref T input) @nogc 86 { 87 static if(is(T == Ternary)) 88 { 89 if(input == Ternary.no) 90 return Ternary.yes; 91 else if(input == Ternary.yes) 92 return Ternary.no; 93 else 94 return input; 95 } 96 else 97 { 98 return !input; 99 } 100 } 101 } 102 103 /** 104 The action node. Executes T with provided arguments, reports the result. If the result is neither true or false, 105 proc is executed with the instance of T and arguments provided. 106 */ 107 struct Action(T, alias proc) 108 { 109 T member; 110 111 /// the (...) serves as the tick method of the node 112 auto opCall(U...)(auto ref U args) 113 { 114 import std.meta; 115 auto res = member(forward!args); 116 if(res == Ternary.unknown) 117 proc(member, forward!args); 118 119 return res; 120 } 121 } 122 123 /// 124 @nogc 125 @system unittest 126 { 127 Functor v; 128 Action!(Leaf!Ternary, process) a; 129 assert(v == 0); 130 auto res = a(v); 131 assert(v == 0); 132 assert(res == Ternary.no); 133 v = 5; 134 res = a(v, 5); 135 assert(v == 10); 136 assert(res == Ternary.no); 137 res = a(v, 20, 20, 20); 138 assert(v == 70); 139 assert(res == Ternary.yes); 140 141 v = 10; 142 res = a(v, 40); 143 assert(v == 500); 144 assert(res == Ternary.unknown); 145 } 146 147 /** 148 The condition node. Executes T with provided arguments, reports the result. The result follows the principle of 149 excluded middle. 150 */ 151 struct Condition(T) 152 { 153 T member; 154 155 auto opCall(U...)(auto ref U args) 156 { 157 bool res = member(forward!args); 158 return Ternary(res); 159 } 160 } 161 162 /// 163 @nogc 164 @system unittest 165 { 166 167 Condition!(Leaf!bool) c; 168 169 assert(c(42) == Ternary.no); 170 assert(c(73) == Ternary.yes); 171 } 172 173 /// The selector node. Tries to tick all of its children until one delivers an answer inequal to false. 174 struct Selector(T...) 175 { 176 T members; 177 this(T...)(auto ref T m) 178 { 179 foreach(i, t; T) 180 { 181 members[i] = m[i]; 182 } 183 } 184 auto opCall(U...)(auto ref U args) 185 { 186 foreach(t; members) 187 { 188 auto res = t(forward!args); 189 if(res != Ternary.no) 190 return res; 191 } 192 return Ternary.no; 193 } 194 } 195 196 /// 197 @nogc 198 @system unittest 199 { 200 Selector!( 201 Condition!(Leaf!bool), 202 Action!(Leaf!Ternary, process) 203 ) sel; 204 205 Functor v; 206 v = 10; 207 auto res = sel(v, 30, 40); 208 assert(v == 80); 209 assert(res == Ternary.yes); 210 211 v = 10; 212 res = sel(v, 20); 213 assert(v == 500); 214 assert(res == Ternary.unknown); 215 216 217 v = 10; 218 res = sel(v, 10); 219 assert(v == 30); 220 assert(res == Ternary.no); 221 } 222 223 /// The sequence node. Tries to tick all of its children until one delivers an answer equal to false. 224 struct Sequence(T...) 225 { 226 T members; 227 this(T...)(auto ref T m) 228 { 229 foreach(i, t; T) 230 { 231 members[i] = m[i]; 232 } 233 } 234 auto opCall(U...)(auto ref U args) 235 { 236 foreach(t; members) 237 { 238 auto res = t(forward!args); 239 if(res != Ternary.yes) 240 return res; 241 } 242 return Ternary.yes; 243 } 244 } 245 246 /// 247 @nogc 248 @system unittest 249 { 250 Sequence!( 251 Condition!(Leaf!bool), 252 Action!(Leaf!Ternary, process) 253 ) sel; 254 255 Functor v; 256 v = 10; 257 auto res = sel(v, 30, 40); 258 assert(v == 150); 259 assert(res == Ternary.yes); 260 261 v = 10; 262 res = sel(v, 20); 263 assert(v == 30); 264 assert(res == Ternary.no); 265 266 v = 50; 267 res = sel(v); 268 assert(v == 500); 269 assert(res == Ternary.unknown); 270 } 271 272 /** 273 The parallel node. Tries to tick all of its children in parallel. Returns true if and only if there were more then 274 Y successful ticks. If there were less successful ticks, returns false, if there were more then N failure ticks. 275 Otherwise returns running. 276 */ 277 struct Parallel(T...) 278 { 279 import std.parallelism : parallel; 280 import std.algorithm : filter, count; 281 282 T members; 283 size_t S; 284 size_t F; 285 286 Ternary[T.length] states; 287 288 this(size_t s, size_t f) 289 { 290 S = s; 291 F = f; 292 } 293 this(T...)(size_t s, size_t f, auto ref T m) 294 { 295 S = s; 296 F = f; 297 foreach(i, t; T) 298 { 299 members[i] = m[i]; 300 } 301 } 302 auto opCall(U...)(auto ref U args) 303 { 304 foreach(i, t; parallel([members])) 305 states[i] = t(forward!args); 306 if(states[].filter!(a => a == Ternary.yes).count >= S) 307 return Ternary.yes; 308 if(states[].filter!(a => a == Ternary.no).count >= F) 309 return Ternary.no; 310 return Ternary.unknown; 311 } 312 } 313 314 /// 315 @nogc 316 @system unittest 317 { 318 Functor v; 319 320 size_t successes = 1; 321 size_t failures = 4; 322 323 auto p = Parallel!( 324 Action!(Leaf!Ternary, process), 325 Action!(Leaf!Ternary, process), 326 Action!(Leaf!Ternary, process), 327 Action!(Leaf!Ternary, process) 328 )(successes,failures); 329 330 assert(p.S == successes); 331 assert(p.F == failures); 332 333 v = 10; 334 auto res = p(v, 0); 335 assert(v == 10); 336 assert(res == Ternary.no); 337 338 v = 10; 339 res = p(v, 10); 340 assert(v == 500); 341 assert(res == Ternary.unknown); 342 343 failures = 3; 344 p = Parallel!( 345 Action!(Leaf!Ternary, process), 346 Action!(Leaf!Ternary, process), 347 Action!(Leaf!Ternary, process), 348 Action!(Leaf!Ternary, process) 349 )(successes,failures); 350 assert(p.S == successes); 351 assert(p.F == failures); 352 v = 10; 353 res = p(v, 10); 354 assert(v == 500); 355 assert(res == Ternary.no); 356 357 v = 10; 358 res = p(v, 15); 359 assert(v == 70); 360 assert(res == Ternary.yes); 361 } 362 363 /// Decorator node. Reseives the child and its args for fine granular adjustments. 364 struct Decorator(T, alias dec) 365 { 366 T member; 367 this(T)(auto ref T t) 368 { 369 member = t; 370 } 371 auto opCall(U...)(auto ref U args) 372 { 373 return Ternary(dec(member(forward!args))); //dec(res); 374 } 375 } 376 377 /// 378 @nogc 379 @system unittest 380 { 381 Action!(Leaf!Ternary, process) a; 382 Decorator!(Action!(Leaf!Ternary, process), Not) d1; 383 384 Functor v; 385 v = 0; 386 auto res = a(v, 10); 387 assert(v == 10); 388 assert(res == Ternary.no); 389 v = 0; 390 res = d1(v, 10); 391 assert(v == 10); 392 assert(res == Ternary.yes); 393 394 v = 50; 395 res = a(v); 396 assert(v == 500); 397 assert(res == Ternary.unknown); 398 v = 50; 399 res = d1(v); 400 assert(v == 500); 401 assert(res == Ternary.unknown); 402 403 v = 5; 404 res = a(v, 10, 10, 10, 10, 10); 405 assert(v == 55); 406 assert(res == Ternary.yes); 407 v = 5; 408 res = d1(v, 10, 10, 10, 10, 10); 409 assert(v == 55); 410 assert(res == Ternary.no); 411 412 Condition!(Leaf!bool) c; 413 Decorator!(Condition!(Leaf!bool), Not) d2; 414 v = 0; 415 res = c(v, 10); 416 assert(v == 10); 417 assert(res == Ternary.no); 418 v = 0; 419 res = d2(v, 10); 420 assert(v == 10); 421 assert(res == Ternary.yes); 422 423 v = 5; 424 res = c(v, 10, 10, 10, 10, 10); 425 assert(v == 55); 426 assert(res == Ternary.yes); 427 v = 5; 428 res = d2(v, 10, 10, 10, 10, 10); 429 assert(v == 55); 430 assert(res == Ternary.no); 431 432 } 433 434 /// The root node. 435 struct Root(T) 436 { 437 T member; 438 this(T)(auto ref T t) 439 { 440 member = t; 441 } 442 auto opCall(U...)(auto ref U args) 443 { 444 return member(forward!args); 445 } 446 } 447 448 /// 449 @nogc 450 @system unittest 451 { 452 static assert( 453 __traits( 454 compiles, Root!( 455 Sequence!( 456 Action!((Leaf!Ternary), process), 457 Condition!(Leaf!bool), 458 Selector!( 459 Decorator!(Condition!(Leaf!bool), Not), 460 Action!((Leaf!Ternary), process) 461 ) 462 ) 463 ) 464 ) 465 ); 466 }