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 import std.traits; 36 37 /// 38 debug 39 { 40 void process(T, U...)(auto ref T a, auto ref U args) @nogc 41 { 42 args[0] *= 10; 43 } 44 45 struct Functor 46 { 47 size_t value; 48 alias value this; 49 auto opCall(U, T...)(auto ref U callable, auto ref T args) @nogc 50 { 51 return callable(this, forward!(input[1..$])); 52 } 53 } 54 55 struct Leaf(T) 56 { 57 auto funn(U, V...)(auto ref U value, auto ref V args) @nogc 58 { 59 foreach(ref a; args) 60 value += a; 61 } 62 63 T opCall(U, A...)(auto ref U F, auto ref A args) @nogc 64 { 65 funn(forward!F, forward!args); 66 static assert(is(T == bool) || is(T == Ternary)); 67 static if(is(T == bool)) 68 { 69 if(F < 50) 70 return false; 71 else 72 return true; 73 } 74 else 75 { 76 if(F < 50) 77 return Ternary.no; 78 else if(F == 50) 79 return Ternary.unknown; 80 else 81 return Ternary.yes; 82 } 83 } 84 } 85 86 auto Not(T)(auto ref T input) @nogc 87 { 88 static if(is(T == Ternary)) 89 { 90 if(input == Ternary.no) 91 return Ternary.yes; 92 else if(input == Ternary.yes) 93 return Ternary.no; 94 else 95 return input; 96 } 97 else 98 { 99 return !input; 100 } 101 } 102 } 103 104 /** 105 The action node. Executes T with provided arguments, reports the result. If the result is neither true or false, 106 proc is executed with the instance of T and arguments provided. 107 */ 108 struct Action(T, alias proc) 109 { 110 T member; 111 112 /// the (...) serves as the tick method of the node 113 auto opCall(U...)(auto ref U args) 114 { 115 import std.meta; 116 auto res = member(forward!args); 117 if(res == Ternary.unknown) 118 { 119 static if(isCallable!proc) 120 { 121 proc(member, forward!args); 122 } 123 else 124 { 125 proc!(T, U)(member, forward!args); 126 } 127 128 } 129 return res; 130 } 131 } 132 133 /// 134 @nogc 135 @system unittest 136 { 137 Functor v; 138 Action!(Leaf!Ternary, process) a; 139 assert(v == 0); 140 auto res = a(v); 141 assert(v == 0); 142 assert(res == Ternary.no); 143 v = 5; 144 res = a(v, 5); 145 assert(v == 10); 146 assert(res == Ternary.no); 147 res = a(v, 20, 20, 20); 148 assert(v == 70); 149 assert(res == Ternary.yes); 150 151 v = 10; 152 res = a(v, 40); 153 assert(v == 500); 154 assert(res == Ternary.unknown); 155 } 156 157 /** 158 The condition node. Executes T with provided arguments, reports the result. The result follows the principle of 159 excluded middle. 160 */ 161 struct Condition(T) 162 { 163 T member; 164 165 auto opCall(U...)(auto ref U args) 166 { 167 bool res = member(forward!args); 168 return Ternary(res); 169 } 170 } 171 172 /// 173 @nogc 174 @system unittest 175 { 176 177 Condition!(Leaf!bool) c; 178 179 assert(c(42) == Ternary.no); 180 assert(c(73) == Ternary.yes); 181 } 182 183 /// The selector node. Tries to tick all of its children until one delivers an answer inequal to false. 184 struct Selector(T...) 185 { 186 T members; 187 this(T...)(auto ref T m) 188 { 189 foreach(i, t; T) 190 { 191 members[i] = m[i]; 192 } 193 } 194 auto opCall(U...)(auto ref U args) 195 { 196 foreach(t; members) 197 { 198 auto res = t(forward!args); 199 if(res != Ternary.no) 200 return res; 201 } 202 return Ternary.no; 203 } 204 } 205 206 /// 207 @nogc 208 @system unittest 209 { 210 Selector!( 211 Condition!(Leaf!bool), 212 Action!(Leaf!Ternary, process) 213 ) sel; 214 215 Functor v; 216 v = 10; 217 auto res = sel(v, 30, 40); 218 assert(v == 80); 219 assert(res == Ternary.yes); 220 221 v = 10; 222 res = sel(v, 20); 223 assert(v == 500); 224 assert(res == Ternary.unknown); 225 226 227 v = 10; 228 res = sel(v, 10); 229 assert(v == 30); 230 assert(res == Ternary.no); 231 } 232 233 /// The sequence node. Tries to tick all of its children until one delivers an answer equal to false. 234 struct Sequence(T...) 235 { 236 T members; 237 this(T...)(auto ref T m) 238 { 239 foreach(i, t; T) 240 { 241 members[i] = m[i]; 242 } 243 } 244 auto opCall(U...)(auto ref U args) 245 { 246 foreach(t; members) 247 { 248 auto res = t(forward!args); 249 if(res != Ternary.yes) 250 return res; 251 } 252 return Ternary.yes; 253 } 254 } 255 256 /// 257 @nogc 258 @system unittest 259 { 260 Sequence!( 261 Condition!(Leaf!bool), 262 Action!(Leaf!Ternary, process) 263 ) sel; 264 265 Functor v; 266 v = 10; 267 auto res = sel(v, 30, 40); 268 assert(v == 150); 269 assert(res == Ternary.yes); 270 271 v = 10; 272 res = sel(v, 20); 273 assert(v == 30); 274 assert(res == Ternary.no); 275 276 v = 50; 277 res = sel(v); 278 assert(v == 500); 279 assert(res == Ternary.unknown); 280 } 281 282 /** 283 The parallel node. Tries to tick all of its children in parallel. Returns true if and only if there were more then 284 Y successful ticks. If there were less successful ticks, returns false, if there were more then N failure ticks. 285 Otherwise returns running. 286 */ 287 struct Parallel(T...) 288 { 289 import std.parallelism : parallel; 290 import std.algorithm : filter, count; 291 292 T members; 293 size_t S; 294 size_t F; 295 296 Ternary[T.length] states; 297 298 this(size_t s, size_t f) 299 { 300 S = s; 301 F = f; 302 } 303 this(T...)(size_t s, size_t f, auto ref T m) 304 { 305 S = s; 306 F = f; 307 foreach(i, t; T) 308 { 309 members[i] = m[i]; 310 } 311 } 312 auto opCall(U...)(auto ref U args) 313 { 314 foreach(i, t; parallel([members])) 315 states[i] = t(forward!args); 316 if(states[].filter!(a => a == Ternary.yes).count >= S) 317 return Ternary.yes; 318 if(states[].filter!(a => a == Ternary.no).count >= F) 319 return Ternary.no; 320 return Ternary.unknown; 321 } 322 } 323 324 /// 325 //@nogc //no nogc for parallel 326 @system unittest 327 { 328 Functor v; 329 330 size_t successes = 1; 331 size_t failures = 4; 332 333 auto p = Parallel!( 334 Action!(Leaf!Ternary, process), 335 Action!(Leaf!Ternary, process), 336 Action!(Leaf!Ternary, process), 337 Action!(Leaf!Ternary, process) 338 )(successes,failures); 339 340 assert(p.S == successes); 341 assert(p.F == failures); 342 343 v = 10; 344 auto res = p(v, 0); 345 assert(v == 10); 346 assert(res == Ternary.no); 347 348 v = 10; 349 res = p(v, 10); 350 assert(v == 500); 351 assert(res == Ternary.unknown); 352 353 failures = 3; 354 p = Parallel!( 355 Action!(Leaf!Ternary, process), 356 Action!(Leaf!Ternary, process), 357 Action!(Leaf!Ternary, process), 358 Action!(Leaf!Ternary, process) 359 )(successes,failures); 360 assert(p.S == successes); 361 assert(p.F == failures); 362 v = 10; 363 res = p(v, 10); 364 assert(v == 500); 365 assert(res == Ternary.no); 366 367 v = 10; 368 res = p(v, 15); 369 assert(v == 70); 370 assert(res == Ternary.yes); 371 } 372 373 /// Decorator node. Reseives the child and its args for fine granular adjustments. 374 struct Decorator(T, alias dec) 375 { 376 T member; 377 this(T)(auto ref T t) 378 { 379 member = t; 380 } 381 auto opCall(U...)(auto ref U args) 382 { 383 return Ternary(dec(member(forward!args))); //dec(res); 384 } 385 } 386 387 /// 388 @nogc 389 @system unittest 390 { 391 Action!(Leaf!Ternary, process) a; 392 Decorator!(Action!(Leaf!Ternary, process), Not) d1; 393 394 Functor v; 395 v = 0; 396 auto res = a(v, 10); 397 assert(v == 10); 398 assert(res == Ternary.no); 399 v = 0; 400 res = d1(v, 10); 401 assert(v == 10); 402 assert(res == Ternary.yes); 403 404 v = 50; 405 res = a(v); 406 assert(v == 500); 407 assert(res == Ternary.unknown); 408 v = 50; 409 res = d1(v); 410 assert(v == 500); 411 assert(res == Ternary.unknown); 412 413 v = 5; 414 res = a(v, 10, 10, 10, 10, 10); 415 assert(v == 55); 416 assert(res == Ternary.yes); 417 v = 5; 418 res = d1(v, 10, 10, 10, 10, 10); 419 assert(v == 55); 420 assert(res == Ternary.no); 421 422 Condition!(Leaf!bool) c; 423 Decorator!(Condition!(Leaf!bool), Not) d2; 424 v = 0; 425 res = c(v, 10); 426 assert(v == 10); 427 assert(res == Ternary.no); 428 v = 0; 429 res = d2(v, 10); 430 assert(v == 10); 431 assert(res == Ternary.yes); 432 433 v = 5; 434 res = c(v, 10, 10, 10, 10, 10); 435 assert(v == 55); 436 assert(res == Ternary.yes); 437 v = 5; 438 res = d2(v, 10, 10, 10, 10, 10); 439 assert(v == 55); 440 assert(res == Ternary.no); 441 442 } 443 444 /// The root node. 445 struct Root(T) 446 { 447 T member; 448 this(T)(auto ref T t) 449 { 450 member = t; 451 } 452 auto opCall(U...)(auto ref U args) 453 { 454 return member(forward!args); 455 } 456 } 457 458 /// 459 @nogc 460 @system unittest 461 { 462 static assert( 463 __traits( 464 compiles, Root!( 465 Sequence!( 466 Action!((Leaf!Ternary), process), 467 Condition!(Leaf!bool), 468 Selector!( 469 Decorator!(Condition!(Leaf!bool), Not), 470 Action!((Leaf!Ternary), process) 471 ) 472 ) 473 ) 474 ) 475 ); 476 }