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".
Those 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.
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. Domain specific
behaviours are recommended to be namespaced.
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 (ac/compile [:selector
[:sequence
[:even? {:fn/coin}]
[:heads!]
[:tails!]]]) {:coin #(< (rand) 0.5)})
db* {:foo :bar}]
(let [{:keys [db status]} (ai/run-tick db* tree)]
(if (= ai/SUCCESS status)
; extract from or use db
; otherwise...))
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 :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.
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.
The :parallel
node executes all of its children.
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.
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 :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.
The :choice-without-repetition
node randomly selects a child to tick excluding children that
have been ticked before. This is then a stateful node that uses the working memory to track which
of its children have already been ticked. We may anticipate that a requirement might exist for
some way to reset the memory.
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 ...)]
(tick {} tree {}))
Copyright 2017-2018 Matthew Mower self@mattmower.com
Can you improve this documentation?Edit on GitHub
cljdoc is a website building & hosting documentation for Clojure/Script libraries
× close