aido
stands for "AI do" and is a behaviour tree library suitable
for implementing AI behaviours into games or applications. It could be
used to model the behaviour of a game character or for a chabot to
control the different responses it might employ.
I won't introduce behaviour trees here (see Google) beyond the basics. A behaviour tree is a tree-like data structure that specifies conditions we are interested in, actions that might be taken in responsento a given set of conditions, and some control flow mechanisms hat govern how the tree "makes decisions".
The heart of the control flow are behaviours such as sequence
and selector
and the notion that any element of the behaviour tree either results in
success or failure. In particular, a sequence considers each of its
children until one of them fails while a selector selects among its children
until one succeeds. From such a simple premise quite complex behaviours can
emerge.
- 15.07.20 - v0.4.0 - introduces the
:choose-each
node, implements 'node memory' for stateful node types, some expansion and tidying of documentation
aido
behaviour trees are implemented as Clojure data structures much in the style of Hiccup markup. As such they can be implemented in EDN notation.
The structure of a behaviour is
[:ns/keyword {options}* children*]
The core aido
behaviours do not have a namespace prefix. I recommend namespacing domain specific behaviours.
The author has developed a convention that behaviours that form conditions should
have a ?
suffix, e.g. :time/after?
while behaviours that represent actions
with side-effects should have a !
suffix, e.g. :beverage/drink!
.
A behaviour can have zero or more child behaviours. For example the [:selector]
and [:sequence]
behaviour expect at least one child although, in practice, both
only make sense with multiple children.
[:selector
[:sequence
[:time/after? {:t :teatime}]
[:beverage/drink! {:beverage :tea}]
[:actor/say! {:message "Oh, how I wish it was time for tea!"}]
In this example the :selector
runs and ticks its first child, the :sequence
.
The :sequence
ticks each of its children in turn. If :time/after?
fails then
the :sequence
fails and the :selector
goes on to tick :actor/say!
. On the
other hand if it succeeds then the :beverage/drink!
child is ticked and, we
assume, succeeds leading to the :sequence
succeeding and the :selector
succeeding without ticking the :actor/say!
child.
In the example above we see that :time/after?
, :beverage/drink!
, and :actor/say!
all specify a map of options. These are assumed to be understood by the implementation
of the behaviour in question. The :selector
and :sequence
do not have options although
some of the built-in behaviours, e.g. loop
do. In the case of :loop
it has a count
option to specify how many times the loop should iterate.
Sometimes it is advantageous to be able to specify options that are dynamic. aido offers two approaches:
-
Specify a function value, the syntax for which is:
[:aido/fn function-id arg1 ... argN]
e.g.
[:loop {:count [:aido/fn rand 5]} ...]
The function-id
should correspond to a function registered with the compiler (see below).
These functions are stand-alone and executed each time the beheaviour is ticked with the return value of the function being passed into the options maps.
-
Specify a database key-path
[:aido/db path1 ... pathN]
e.g.
[:loop {:count [:aido/db :settings :loop-count]]}]
When the behaviour is ticked the appropriate value in the database will be passed in instead, this example would be conceptually equivalent to:
[:loop {:count (get-in db [:settings :loop-count])}]
Functions are specified by passing an optional map to compile
for example to satisfy the
trees above you might use:
(aido.compile/compile tree {:rand rand-int})
Any behaviour is expected to return one of four values:
SUCCESS
FAILURE
RUNNING
ERROR
Most commonly behaviours are going to return SUCCESS
or FAILURE
.
ERROR
is intended to be a severe form of FAILURE
indicating a problem processing the behaviour tree.
In the current version of aido
the two are interchangable and ERROR
is essentially unused.
RUNNING
is intended to be an alternative to SUCCESS
that indicates that a behaviour has neither succeeded
nor failed but is in-progress. The main difference between SUCCESS
and RUNNING
is that a sequence will
terminate with the RUNNING
status if any of its children returns RUNNING
.
Flow control is primilarily implemented in terms of :selector
and :sequence
behaviours.
In basic usage you must compile a behaviour tree using aido.compile/compile
and then to run it
use the aido.core/run-tick
function. It is not recommend to call the tick
function directly.
(ns 'aido.example
(:require
[aido.core :as ai]
[aido.compile :as ac]))
(let [tree-fns {:coin-toss #(< (rand) 0.5)}
tree (ac/compile [:selector
[:sequence
[:true? {:expr [:aido/fn coin-toss]}]
[:heads!]
[:tails!]]]
tree-fns)
db {:foo :bar}]
(let [{:keys [db* status]} (ai/run-tick db tree)]
(if (= ai/SUCCESS status)
; extract from or use db*
; otherwise...))
Some nodes use a working memory that is reset between invocations of run-tick
. Some stateful nodes
such as :choose-each
use storage that is persisted in the database between invocations of run-tick
using a namespaced key. It is important to preserve this key if the database is modified between
invocations of run-tick
.
The :selector
node executes its children in turn until one of them succeeds at
which point execution stops and the :selector
succeeds. If none of the children
suceeds the :selector
fails.
The :sequence
node executes its children in turn. If a child fails execution
stops and the :sequence
fails. If all of the children succeed the :sequence
succeeds.
The :selector-p
node iterates over its children in turn. For each child it does a probability
check which, if it passes, selects that child to be ticked. The :selector-p
succeeds or fails
based on whether the child succeeds or fails. If the probability test does not pass for any
child :selector-p
fails.
:p
- probability of ticking any child (0โฆ1)
The :loop
node executes a single child a specified number of times. It is
successful if it completes the specified iterations. If the child fails
then the :loop
fails.
:count
- number of times the loop should execute
The :loop-until-success
node executes a child up to a specified number of times.
If the child succeeds then the :loop-until-success
succeeds. Otherwise, after
the specified number of iterations the :loop-until-success
fails.
:count
- number of times the loop should execute
The :parallel
node executes all of its children.
:mode
- When :mode
is :success
the :how-many
parameter refers to how many children must succeed. When :mode
is :failure
the parameter refers to how many children must fail.
:how-many
- Number of children that must succeed or fail for the node to return success or failure
The :randomly
node operates in one of two modes depending on whether it has
one or two children.
With one child :randomly
evaluates the child if the p test passes and succeeds
or fails if the child succeeds or fails. If the p
test fails :randomly
fails.
With two children :randomly
evaluates the first child if the p test passes or
the second child if it fails. :randomly
succeeds or fails based on the selected
child succeeding or failing.
:p
- probability
The :choose
node takes one or more children and, when evaluated, randomly
selects one child and ticks it. :choose
succeeds or fails if the child
succeeds or fails.
The :choose-each
node takes one or more children and, when evaluated, randomly
selects one child, ticks, and then marks it. Once a node has been marked it will
not be choosen again. :choose-each
succeeeds or fails if the child
succeeds or fails. Subsequent ticks will always select from unmarked children.
:repeat
- if repeat is true
, after all children have been ticked the node "refills" its
children. If repeat is false
after all children have been ticked the node will thereafter
fail.
The :invert
node takes a single child. When :invert
is ticked it ticks its child and inverts
the success or failure of the child. So if the child returns failure, invert returns success
and vice verca.
The :always
node expects one child that it ticks and then suceeds regardless of
whether the child succeeds.
The :never
node expects one child that it ticks and then fails regardless of
whether the child fails.
The following are extensions of the choice idea that provide for non-uniform behaviour. They are given
as separate nodes but, in practice, could be implemented by extending the existing :choice
node type
with additional options.
The :weighted-choice
node randomly selects a child to tick based on some weighting algorithm.
Behaviours in AIDO are defined by creating new tick node types. A node type is defined by implementing 3
multimethods: tick
, options
, and children
. Implementing tick
is required, options
and children
offer default behaviour ('no options' and 'no children' respectively).
Let's define a new node type that is a variation on a selector but has a probability check to determine whether to try and tick child nodes. If the probability check fails it moves on to the next child. It succeeds if a child succeeds, otherwise fails.
It would look something like:
[:selector-p {:p 0.15} [child1] [child2] [child3]]
Here is how the node type would be defined:
(defmethod options :selector-p [& _] [:p])
(defmethod children :selector-p [& _] :some)
(defmethod tick :selector-p [db [node-type {:keys [p]} & children]
...)
See aido.core
source for definitions of the built in node-types.
(require '[aido.core :as aido]
[aido.compile :as ac])
(let [tree (ac/compile ...)]
(aido/run-tick {} tree))
Copyright 2017-2018 Matthew Mower [email protected]