bonsai_bt/state.rs
1use crate::event::UpdateEvent;
2use crate::sequence::{memoryless_sequence, sequence, MemorylessSequenceArgs, SequenceArgs};
3use crate::state::State::*;
4use crate::status::Status::*;
5use crate::tracer::{first_child_id, next_sibling_id, NodeMeta, Tracer};
6use crate::when_all::{when_all, WhenAllArgs};
7use crate::{Behavior, Float, Status};
8use std::fmt::Debug;
9
10#[cfg(feature = "serde")]
11use serde::{Deserialize, Serialize};
12
13/// The action is still running, and thus the action consumes
14/// all the remaining delta time for the tick
15pub const RUNNING: (Status, Float) = (Running, 0.0);
16
17/// The arguments in the action callback.
18pub struct ActionArgs<'a, E: 'a, A: 'a> {
19 /// The event.
20 pub event: &'a E,
21 /// The remaining delta time. When one action terminates,
22 /// it can consume some of dt and the remaining is passed
23 /// onto the next action.
24 pub dt: Float,
25 /// The action running.
26 pub action: &'a A,
27}
28
29/// Keeps track of a behavior.
30#[derive(Clone, Debug, PartialEq)]
31#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
32pub(crate) enum State<A> {
33 /// Executes an action.
34 Action(A),
35 /// Converts `Success` into `Failure` and vice versa.
36 Invert(Box<State<A>>),
37 /// Ignores failures and always return `Success`.
38 AlwaysSucceed(Box<State<A>>),
39 /// Keeps track of waiting for a period of time before continuing.
40 Wait { time_to_wait: Float, elapsed_time: Float },
41 /// Waits forever.
42 WaitForever,
43 /// Keeps track of an `If` behavior.
44 If {
45 /// The behavior to run if the status is a success.
46 on_success: Box<Behavior<A>>,
47 /// The behavior to run if the status is a failure.
48 on_failure: Box<Behavior<A>>,
49 /// The status of the condition. The `If` behavior will resolve to one
50 /// of `on_success` or `on_failure` once the status is not `Running`.
51 status: Status,
52 /// The current state to execute.
53 current_state: Box<State<A>>,
54 },
55 /// Keeps track of a `Select` behavior.
56 Select {
57 /// The behaviors that will be selected across in order.
58 behaviors: Vec<Behavior<A>>,
59 /// The index of the behavior currently being executed.
60 current_index: usize,
61 /// The state of the behavior currently being executed.
62 current_state: Box<State<A>>,
63 },
64 /// Keeps track of an `Sequence` behavior.
65 Sequence {
66 /// The behaviors that will be executed in order.
67 behaviors: Vec<Behavior<A>>,
68 /// The index of the behavior currently being executed.
69 current_index: usize,
70 /// The state of the behavior currently being executed.
71 current_state: Box<State<A>>,
72 },
73 /// A memoryless `Sequence` (`memory = false`). Re-walks children from 0 each
74 /// tick, so there is no index. `cursor` is reused in place for each child.
75 MemorylessSequence {
76 /// Children, re-walked in order each tick.
77 behaviors: Vec<Behavior<A>>,
78 /// Scratch slot for the child being ticked. Reused, never re-allocated.
79 cursor: Box<State<A>>,
80 },
81 /// A memoryless `Select` (`memory = false`). Same shape as
82 /// [`State::MemorylessSequence`]; success short-circuits, all-fail is `Failure`.
83 MemorylessSelector {
84 /// Children, re-walked in order each tick.
85 behaviors: Vec<Behavior<A>>,
86 /// Scratch slot for the child being ticked. Reused, never re-allocated.
87 cursor: Box<State<A>>,
88 },
89 /// Keeps track of a `While` behavior.
90 While {
91 /// The state of the condition of the loop. The loop continues to run
92 /// while this state is running.
93 condition_state: Box<State<A>>,
94 /// The behaviors that compose the loop body in order.
95 loop_body: Vec<Behavior<A>>,
96 /// The index of the behavior in the loop body currently being executed.
97 loop_body_index: usize,
98 /// The state of the behavior in the loop body currently being executed.
99 loop_body_state: Box<State<A>>,
100 },
101 /// Keeps track of a `WhileAll` behavior.
102 WhileAll {
103 /// The state of the condition of the loop. The loop continues to run
104 /// while this state is running, though this is only checked once at the
105 /// start of each loop.
106 condition_state: Box<State<A>>,
107 /// Whether to check the condition on the next tick.
108 check_condition: bool,
109 /// The behaviors that compose the loop body in order.
110 loop_body: Vec<Behavior<A>>,
111 /// The index of the behavior in the loop body currently being executed.
112 loop_body_index: usize,
113 /// The state of the behavior in the loop body currently being executed.
114 loop_body_state: Box<State<A>>,
115 },
116 /// Keeps track of a `WhenAll` behavior. As the states finish, they are set
117 /// to [`None`].
118 WhenAll(Vec<Option<State<A>>>),
119 /// Keeps track of a `WhenAny` behavior. As the states finish, they are set
120 /// to [`None`].
121 WhenAny(Vec<Option<State<A>>>),
122 /// Keeps track of a `Race` behavior.
123 Race(Vec<Option<State<A>>>),
124 /// Keeps track of an `After` behavior.
125 After {
126 /// The index of the next state that must succeed.
127 next_success_index: usize,
128 /// The states for the behaviors currently executing. All the states
129 /// before `next_success_index` must have finished with success.
130 states: Vec<State<A>>,
131 },
132}
133
134impl<A: Clone> State<A> {
135 /// Creates a state from a behavior.
136 ///
137 /// For each behavior there is a `State` that keeps track of current running process.
138 /// When you declare a behavior, this state is not included, resulting in a compact
139 /// representation that can be copied or shared between objects having same behavior.
140 /// Behavior means the declarative representation of the behavior, and State represents
141 /// the executing instance of that behavior.
142 pub fn new(behavior: Behavior<A>) -> Self {
143 match behavior {
144 Behavior::Action(action) => State::Action(action),
145 Behavior::Invert(ev) => State::Invert(Box::new(State::new(*ev))),
146 Behavior::AlwaysSucceed(ev) => State::AlwaysSucceed(Box::new(State::new(*ev))),
147 Behavior::Wait(dt) => State::Wait {
148 time_to_wait: dt,
149 elapsed_time: 0.0,
150 },
151 Behavior::WaitForever => State::WaitForever,
152 Behavior::If(condition, on_success, on_failure) => {
153 let state = State::new(*condition);
154 State::If {
155 on_success,
156 on_failure,
157 status: Status::Running,
158 current_state: Box::new(state),
159 }
160 }
161 Behavior::Select(behaviors) => {
162 let state = State::new(behaviors[0].clone());
163 State::Select {
164 behaviors,
165 current_index: 0,
166 current_state: Box::new(state),
167 }
168 }
169 Behavior::MemorylessSelector(behaviors) => State::MemorylessSelector {
170 behaviors,
171 // Placeholder; overwritten on the first tick.
172 cursor: Box::new(State::WaitForever),
173 },
174 Behavior::Sequence(behaviors) => {
175 let state = State::new(behaviors[0].clone());
176 State::Sequence {
177 behaviors,
178 current_index: 0,
179 current_state: Box::new(state),
180 }
181 }
182 Behavior::MemorylessSequence(behaviors) => State::MemorylessSequence {
183 behaviors,
184 cursor: Box::new(State::WaitForever),
185 },
186 Behavior::While(condition, loop_body) => {
187 let state = State::new(loop_body[0].clone());
188 State::While {
189 condition_state: Box::new(State::new(*condition)),
190 loop_body,
191 loop_body_index: 0,
192 loop_body_state: Box::new(state),
193 }
194 }
195 Behavior::WhenAll(all) => State::WhenAll(all.into_iter().map(|ev| Some(State::new(ev))).collect()),
196 Behavior::WhenAny(any) => State::WhenAny(any.into_iter().map(|ev| Some(State::new(ev))).collect()),
197 Behavior::Race(behaviors) => State::Race(behaviors.into_iter().map(|ev| Some(State::new(ev))).collect()),
198 Behavior::After(after_all) => State::After {
199 next_success_index: 0,
200 states: after_all.into_iter().map(State::new).collect(),
201 },
202 Behavior::WhileAll(condition, loop_body) => {
203 let state = State::new(
204 loop_body
205 .first()
206 .expect("WhileAll's sequence of behaviors to run cannot be empty!")
207 .clone(),
208 );
209 State::WhileAll {
210 condition_state: Box::new(State::new(*condition)),
211 check_condition: true,
212 loop_body,
213 loop_body_index: 0,
214 loop_body_state: Box::new(state),
215 }
216 }
217 }
218 }
219
220 /// Updates the cursor that tracks an event.
221 ///
222 /// The action need to return status and remaining delta time.
223 /// Returns status and the remaining delta time.
224 ///
225 /// Passes event, delta time in seconds, action and state to closure.
226 /// The closure should return a status and remaining delta time.
227 ///
228 /// return: (Status, Float)
229 /// function returns the result of the tree traversal, and how long
230 /// it actually took to complete the traversal and propagate the
231 /// results back up to the root node
232 pub(crate) fn tick<E, F, B, T>(
233 &mut self,
234 self_id: usize,
235 metas: &[NodeMeta],
236 e: &E,
237 blackboard: &mut B,
238 f: &mut F,
239 tracer: &mut T,
240 ) -> (Status, Float)
241 where
242 E: UpdateEvent,
243 F: FnMut(ActionArgs<E, A>, &mut B) -> (Status, Float),
244 T: Tracer,
245 {
246 let upd = e.update(|args| Some(args.dt)).unwrap_or(None);
247
248 // double match statements
249 match (upd, self) {
250 (_, &mut Action(ref action)) => {
251 let result = f(
252 ActionArgs {
253 event: e,
254 dt: upd.unwrap_or(0.0),
255 action,
256 },
257 blackboard,
258 );
259 tracer.record(self_id, result.0);
260 result
261 }
262 (_, &mut Invert(ref mut cur)) => {
263 let child_id = first_child_id::<T>(self_id);
264 let result = match cur.tick(child_id, metas, e, blackboard, f, tracer) {
265 (Running, dt) => (Running, dt),
266 (Failure, dt) => (Success, dt),
267 (Success, dt) => (Failure, dt),
268 };
269 tracer.record(self_id, result.0);
270 result
271 }
272 (_, &mut AlwaysSucceed(ref mut cur)) => {
273 let child_id = first_child_id::<T>(self_id);
274 let result = match cur.tick(child_id, metas, e, blackboard, f, tracer) {
275 (Running, dt) => (Running, dt),
276 (_, dt) => (Success, dt),
277 };
278 tracer.record(self_id, result.0);
279 result
280 }
281 (
282 Some(dt),
283 &mut Wait {
284 time_to_wait,
285 ref mut elapsed_time,
286 },
287 ) => {
288 *elapsed_time += dt;
289 let result = if *elapsed_time >= time_to_wait {
290 let time_overdue = *elapsed_time - time_to_wait;
291 *elapsed_time = time_to_wait;
292 (Success, time_overdue)
293 } else {
294 RUNNING
295 };
296 tracer.record(self_id, result.0);
297 result
298 }
299 (
300 _,
301 &mut If {
302 ref on_success,
303 ref on_failure,
304 ref mut status,
305 ref mut current_state,
306 },
307 ) => {
308 let cond_id = first_child_id::<T>(self_id);
309 let on_success_id = next_sibling_id::<T>(metas, cond_id);
310 let on_failure_id = next_sibling_id::<T>(metas, on_success_id);
311 let mut remaining_dt = upd.unwrap_or(0.0);
312 let remaining_e;
313 // Run in a loop to evaluate success or failure with
314 // remaining delta time after condition.
315 let result = loop {
316 *status = match *status {
317 Running => match current_state.tick(cond_id, metas, e, blackboard, f, tracer) {
318 (Running, dt) => break (Running, dt),
319 (Success, dt) => {
320 **current_state = State::new((**on_success).clone());
321 remaining_dt = dt;
322 Success
323 }
324 (Failure, dt) => {
325 **current_state = State::new((**on_failure).clone());
326 remaining_dt = dt;
327 Failure
328 }
329 },
330 s => {
331 let branch_id = if s == Success { on_success_id } else { on_failure_id };
332 let ev = match upd {
333 Some(_) => {
334 remaining_e = UpdateEvent::from_dt(remaining_dt, e).unwrap();
335 &remaining_e
336 }
337 _ => e,
338 };
339 break current_state.tick(branch_id, metas, ev, blackboard, f, tracer);
340 }
341 }
342 };
343 tracer.record(self_id, result.0);
344 result
345 }
346 (
347 _,
348 &mut Select {
349 behaviors: ref seq,
350 current_index: ref mut i,
351 current_state: ref mut cursor,
352 },
353 ) => {
354 let select = true;
355 let result = sequence(SequenceArgs {
356 select,
357 upd,
358 seq,
359 i,
360 cursor,
361 e,
362 f,
363 blackboard,
364 parent_id: self_id,
365 metas,
366 tracer,
367 });
368 tracer.record(self_id, result.0);
369 result
370 }
371 (
372 _,
373 &mut Sequence {
374 behaviors: ref seq,
375 current_index: ref mut i,
376 current_state: ref mut cursor,
377 },
378 ) => {
379 let select = false;
380 let result = sequence(SequenceArgs {
381 select,
382 upd,
383 seq,
384 i,
385 cursor,
386 e,
387 f,
388 blackboard,
389 parent_id: self_id,
390 metas,
391 tracer,
392 });
393 tracer.record(self_id, result.0);
394 result
395 }
396 (
397 _,
398 &mut MemorylessSequence {
399 behaviors: ref seq,
400 ref mut cursor,
401 },
402 ) => {
403 let result = memoryless_sequence(MemorylessSequenceArgs {
404 select: false,
405 upd,
406 seq,
407 cursor,
408 e,
409 f,
410 blackboard,
411 parent_id: self_id,
412 metas,
413 tracer,
414 });
415 tracer.record(self_id, result.0);
416 result
417 }
418 (
419 _,
420 &mut MemorylessSelector {
421 behaviors: ref seq,
422 ref mut cursor,
423 },
424 ) => {
425 let result = memoryless_sequence(MemorylessSequenceArgs {
426 select: true,
427 upd,
428 seq,
429 cursor,
430 e,
431 f,
432 blackboard,
433 parent_id: self_id,
434 metas,
435 tracer,
436 });
437 tracer.record(self_id, result.0);
438 result
439 }
440 (
441 _,
442 &mut While {
443 ref mut condition_state,
444 ref loop_body,
445 ref mut loop_body_index,
446 ref mut loop_body_state,
447 },
448 ) => {
449 let cond_id = first_child_id::<T>(self_id);
450 let body_0_id = next_sibling_id::<T>(metas, cond_id);
451 let mut current_body_id = if T::IS_RECORDING {
452 let mut id = body_0_id;
453 for _ in 0..*loop_body_index {
454 id = next_sibling_id::<T>(metas, id);
455 }
456 id
457 } else {
458 usize::MAX
459 };
460 // If the condition behavior terminates, do not execute the loop.
461 match condition_state.tick(cond_id, metas, e, blackboard, f, tracer) {
462 (Running, _) => {}
463 x => {
464 tracer.record(self_id, x.0);
465 return x;
466 }
467 };
468 let cur = loop_body_state;
469 let mut remaining_dt = upd.unwrap_or(0.0);
470 let mut remaining_e;
471 let result = loop {
472 let ev = match upd {
473 Some(_) => {
474 remaining_e = UpdateEvent::from_dt(remaining_dt, e).unwrap();
475 &remaining_e
476 }
477 _ => e,
478 };
479 match cur.tick(current_body_id, metas, ev, blackboard, f, tracer) {
480 (Failure, x) => break (Failure, x),
481 (Running, _) => break RUNNING,
482 (Success, new_dt) => {
483 remaining_dt = match upd {
484 // Change update event with remaining delta time.
485 Some(_) => new_dt,
486 // Other events are 'consumed' and not passed to next.
487 _ => break RUNNING,
488 };
489 }
490 };
491 *loop_body_index += 1;
492 if T::IS_RECORDING {
493 current_body_id = next_sibling_id::<T>(metas, current_body_id);
494 }
495 // If end of repeated events,
496 // start over from the first one.
497 if *loop_body_index >= loop_body.len() {
498 *loop_body_index = 0;
499 if T::IS_RECORDING {
500 current_body_id = body_0_id;
501 }
502 }
503 // Create a new cursor for next event.
504 // Use the same pointer to avoid allocation.
505 **cur = State::new(loop_body[*loop_body_index].clone());
506 };
507 tracer.record(self_id, result.0);
508 result
509 }
510 (_, &mut WhenAll(ref mut cursors)) => {
511 let result = when_all(WhenAllArgs {
512 any: false,
513 upd,
514 cursors,
515 e,
516 blackboard,
517 f,
518 parent_id: self_id,
519 metas,
520 tracer,
521 });
522 tracer.record(self_id, result.0);
523 result
524 }
525 (_, &mut WhenAny(ref mut cursors)) => {
526 let result = when_all(WhenAllArgs {
527 any: true,
528 upd,
529 cursors,
530 e,
531 blackboard,
532 f,
533 parent_id: self_id,
534 metas,
535 tracer,
536 });
537 tracer.record(self_id, result.0);
538 result
539 }
540 (_, &mut Race(ref mut cursors)) => {
541 // return the result of the first child to complete,
542 // regardless of whether it succeeds or fails.
543 let mut child_id = first_child_id::<T>(self_id);
544 for cur in cursors.iter_mut() {
545 let this_id = child_id;
546 child_id = next_sibling_id::<T>(metas, this_id);
547 match *cur {
548 None => {}
549 Some(ref mut state) => match state.tick(this_id, metas, e, blackboard, f, tracer) {
550 (Running, _) => continue,
551 (status, dt) => {
552 tracer.record(self_id, status);
553 return (status, dt);
554 }
555 },
556 }
557 }
558 tracer.record(self_id, Running);
559 RUNNING
560 }
561 (
562 _,
563 &mut After {
564 ref mut next_success_index,
565 ref mut states,
566 },
567 ) => {
568 // Get the least delta time left over.
569 let mut min_dt = Float::MAX;
570 let mut child_id = first_child_id::<T>(self_id);
571 if T::IS_RECORDING {
572 for _ in 0..*next_success_index {
573 child_id = next_sibling_id::<T>(metas, child_id);
574 }
575 }
576 for (j, item) in states.iter_mut().enumerate().skip(*next_success_index) {
577 let this_id = child_id;
578 child_id = next_sibling_id::<T>(metas, this_id);
579 match item.tick(this_id, metas, e, blackboard, f, tracer) {
580 (Running, _) => {
581 min_dt = 0.0;
582 }
583 (Success, new_dt) => {
584 // Remaining delta time must be less to succeed.
585 if *next_success_index == j && new_dt < min_dt {
586 *next_success_index += 1;
587 min_dt = new_dt;
588 } else {
589 // Return least delta time because
590 // that is when failure is detected.
591 tracer.record(self_id, Failure);
592 return (Failure, min_dt.min(new_dt));
593 }
594 }
595 (Failure, new_dt) => {
596 tracer.record(self_id, Failure);
597 return (Failure, new_dt);
598 }
599 };
600 }
601 let result = if *next_success_index == states.len() {
602 (Success, min_dt)
603 } else {
604 RUNNING
605 };
606 tracer.record(self_id, result.0);
607 result
608 }
609 (
610 _,
611 &mut WhileAll {
612 ref mut condition_state,
613 ref mut check_condition,
614 ref loop_body,
615 ref mut loop_body_index,
616 ref mut loop_body_state,
617 },
618 ) => {
619 let cond_id = first_child_id::<T>(self_id);
620 let body_0_id = next_sibling_id::<T>(metas, cond_id);
621 let mut current_body_id = if T::IS_RECORDING {
622 let mut id = body_0_id;
623 for _ in 0..*loop_body_index {
624 id = next_sibling_id::<T>(metas, id);
625 }
626 id
627 } else {
628 usize::MAX
629 };
630 let mut remaining_dt = upd.unwrap_or(0.0);
631 let mut remaining_e;
632 let result = loop {
633 // check run condition only if allowed at this time:
634 if *check_condition {
635 *check_condition = false;
636 debug_assert!(
637 *loop_body_index == 0,
638 "sequence index should always be 0 when condition is checked!"
639 );
640 match condition_state.tick(cond_id, metas, e, blackboard, f, tracer) {
641 // if running, move to sequence:
642 (Running, _) => {}
643 // if success or failure, get out:
644 x => break x,
645 };
646 }
647
648 let ev = match upd {
649 Some(_) => {
650 remaining_e = UpdateEvent::from_dt(remaining_dt, e).unwrap();
651 &remaining_e
652 }
653 _ => e,
654 };
655
656 match loop_body_state.tick(current_body_id, metas, ev, blackboard, f, tracer) {
657 (Failure, x) => break (Failure, x),
658 (Running, _) => break RUNNING,
659 (Success, new_dt) => {
660 // only success moves the sequence cursor forward:
661 *loop_body_index += 1;
662 if T::IS_RECORDING {
663 current_body_id = next_sibling_id::<T>(metas, current_body_id);
664 }
665
666 // If end of repeated events,
667 // start over from the first one
668 // and allow run condition check to happen:
669 if *loop_body_index >= loop_body.len() {
670 *check_condition = true;
671 *loop_body_index = 0;
672 if T::IS_RECORDING {
673 current_body_id = body_0_id;
674 }
675 }
676
677 // Create a new cursor for next event.
678 // Use the same pointer to avoid allocation.
679 **loop_body_state = State::new(loop_body[*loop_body_index].clone());
680 remaining_dt = new_dt;
681 }
682 };
683 };
684 tracer.record(self_id, result.0);
685 result
686 }
687
688 // WaitForeverState, WaitState
689 _ => {
690 tracer.record(self_id, Running);
691 RUNNING
692 }
693 }
694 }
695}