alter-ego - A Reactive AI Library
29 Jun 2010
alter-ego is a reactive AI library based on the concept of behavior trees. Behavior trees combines a number of AI techniques such as Hierarchical State Machines, Scheduling, Planning, and Action Execution. Their strength comes from the fact that it is very easy to see logic, they are fast to execute and easy to maintain.
Behavior trees allow programmers to piece together reusable blocks of code which can be as simple as looking up a variable in game state to running an animation, then the behavior tree is used to control the flow and execution of these blocks of code.
As its name implies a behavior tree is a tree structure, made up of three types of nodes, action, decorator, composite. Composite and decorator nodes are used to control the flow within the three and action nodes are where we execute code they return success or failure and their return value is then used to decide where to navigate next in the tree.
In alter-ego actions are functions, if you are using the built in editor for composing trees an action is function that takes a single variable called blackboard this is what the behavior tree uses to communicate with the outside world, if you are programmatically building your tree, you can pass arbitrary number of variables. Actions are used to change state such as calculating a new path or shooting at the player.
Selector and sequence nodes are workhorse internal nodes. Selector node will try to execute its first child, if it returns success it will also return success if it fails it will try executing its next child until one of its children returns success or it runs out of children at which point it will return failure. This property allows us to choose which behavior to run next,
On the other hand a sequence represents a series of behaviors that we need to accomplish. A sequence will try to execute all its children from left to right, if all of its children succeeds sequence will also succeed, if one of its children fails sequence will stop and return failure.
With the above tree, root selector first checks attack sequence, attack in return executes action Player In Range? if it succeeds we pick a weapon, face the player and fire. If Player In Range? fails we stop execution and it causes attack sequence to fail and selector tries to execute Taunt sequence.
Thats enough theory to put together something that works,
This represents a very simple AI logic for a robocode bot, every time we execute the tree, we scan for others bots in the arena, pick one to attack, then we execute Move selector, if we are not too close we move forward, if we are too close forward sequence will fail and we fall back to back action. We want our robot to be always ready to fire so the first thing we do in Fire sequence is to turn the turret towards the target then we check if we are within gun range, if we are we fire, if we are not we bail out which takes us back to scan, whether we fire or not we always keep the gun locked on the target.
On the Clojure side, we only need to implement actions (green leaf nodes), rest is handled in the bundled behavior tree editor this is what makes behavior trees powerful, you can reorganize, cut, copy, paste nodes without changing a single line of code,
(defn fire [blackboard]
(from-blackboard blackboard [robot]
(.fire robot 3) true))
Actions are Clojure functions, they take one variable blackboard which is a reference holding a map. Blackboard is what nodes use to communicate with each other such as when an action picks a target it is written to the blackboard then another action reads that value and acts on it. When working with Java methods you need to keep in mind that return value of the action will be coerced to boolean that is what determines success or failure of the action when methods return null even when they succeed such as fire above you need to return true explicitly. from-blackboard is a convenience macro that will lookup the values of its bindings in the blackboard,
(from-blackboard blackboard [robot])
will expand to,
(let [robot (:robot @blackboard)])
After we define all our actions, all we need to do is load the behavior tree and execute it,
(defn -run [robot]
(setup robot)
(let [tree (load-tree "/Users/nakkaya/Desktop/robocode/tank.bt"
(.blackboard robot))]
(forever (exec tree))))
Note that when loading the tree you can provide your own blackboard or one will be automatically provided for your nodes even if you don't plan on using it.
Files,
Finite State Machine Implementation in Clojure
22 Jun 2010
A finite state machine is set of states, one being the start state, each state has a list of transitions, transitions in turn has conditions and actions whenever a condition for a transition is met FSM performs the action and enters the new state. FSM are widely used for game and robotic AI. Most games are just a bunch of FSMs running little chunks of code reacting to state changes. An NPC for example when instantiated can be in patrol state and as soon as the player approaches, it might cause it to transition into attack state which might cause it to run towards you.
(defn state-machine [transition-table initial-state]
(ref initial-state :meta transition-table))
A state machine is a ref holding the current state, transition table containing the list of states and transition rules are attached as meta data.
(def traffic-light
{:green [{:conditions [] :transition :yellow}]
:yellow [{:conditions [] :transition :red}]
:red [{:conditions [] :transition :green}]})
Transition table is represented as a map containing states as keys and vector of maps containing condition, action and transition information.
(defn- switch-state? [conds]
(if (empty? conds)
true
(not (some false? (reduce #(conj %1 (if (fn? %2) (%2) %2)) [] conds)))))
(defn- first-valid-transition [ts]
(find-first #(= (second %) true)
(map #(let [{conds :conditions
transition :transition
on-success :on-success} %]
[transition (switch-state? conds) on-success]) ts)))
(defn update-state [state]
(let [transition-list ((meta state) @state)
[transition _ on-success] (first-valid-transition transition-list)]
(if-not (nil? transition)
(do
(if-not (nil? on-success)
(on-success))
(dosync (ref-set state transition))))))
Every time we try to update state machines state, first we get the list of transition rules for the current state, then we start checking conditions for transition in the order they appear in the vector first transition that returns true for all its conditions is picked, if it has a on-success function it will be executed and reference will be set to the new state.
(let [sm (state-machine traffic-light :green)]
(dotimes [_ 4]
(println @sm)
(update-state sm)))
state-machine.core=> :green
:yellow
:red
:green
Above example shows how traffic light state machine iterates through its states. A more complicated and famous example is a find-lisp state machine that would search for the word lisp in a character sequence,
(defn find-lisp [char-seq]
(let [start-trans {:conditions []
:on-success #(pop-char char-seq)
:transition :start}
found-l-trans {:conditions [#(= (first @char-seq) \l)]
:on-success #(pop-char char-seq)
:transition :found-l}]
{:start [found-l-trans
start-trans]
:found-l [found-l-trans
{:conditions [#(= (first @char-seq) \i)]
:on-success #(pop-char char-seq)
:transition :found-i}
start-trans]
:found-i [found-l-trans
{:conditions [#(= (first @char-seq) \s)]
:on-success #(pop-char char-seq)
:transition :found-s}
start-trans]
:found-s [found-l-trans
{:conditions [#(= (first @char-seq) \p)]
:on-success #(do (println "Found Lisp")
(pop-char char-seq))
:transition :start}
start-trans]}))
When we run it, it will print Found Lisp every time we find the sequence of characters l,i,s,p in this particular order,
(let [char-seq (ref "ablislasllllispsslis")
sm (state-machine (find-lisp char-seq) :start)]
(dotimes [_ (count @char-seq)]
(update-state sm)))
state-machine.core=> Found Lisp
Even though it is not designed for this but Vijual works for quick and dirty visualization of state machines,
(use 'vijual)
(do (println )
(draw-graph (prepare-nodes (state-machine traffic-light :start))))
state-machine.core=>
+--------+ +-------+
| | | |
| yellow |---| |
| | | green |
+--------+ | |
| | |
| +-------+
| |
| +--------+
| |
+-----+
| red |
+-----+