Finite-state machines in Herculeum – part 1

Pyherc/Herculeum has bunch of finite-state machines, mostly in AI code. While working on adding bats into game (along all the required features like flying and lunges), I thought that I would be nice to clean up old AI code too and write basis for future finite-state machines. So I sat down and drafted first imaginary example:

(statemachine :initial-state find-home
              (find-home :active (find-patrol-area pit-selector)
                         (transitions [arrived-home? patrol]
                                      [enemy-detected? fight]))
              (patrol :active (patrol-area pit-selector)
                      (transitions [enemy-detected? fight]))
              (fight :active (fight-in-melee)
                     (transitions [enemy-killed? find-home]
                                  [enemy-not-visible? search]))
              (search :on-activate (set-search-timer)
                      :active (search-enemies)
                      (transitions [enemy-detected? fight]
                                   [search-timer-expired? find-home])))

This imaginary code would create a finite-state machine for AI that is mostly staying put on a given area, but after detecting player would pursue them. There are four states: find-home, patrol, fight and search. Transitions between states are specified in a declarative manner and triggered when associated function returns true. Following diagram shows relation of states and transitions between them. Every state can have two sets of code attached to it: on-activate is run when the finite-state machine enters the given state and active is run for the active state when finite-state machine executes.

finite-state machine

While pretty decent start (at least in my own opinion), the example needed some work. For example, it didn’t really answer to questions like: “How do I use this?” and “What kind of data structure will this be?”. So I created (a contrived) example of imaginary REPL session:

=> (statemachine Transmogrifier
...              :initial-state start
...              :interface [message]
...              (start (on-activate (print "values will be doubled"))
...                     (active (if (numeric? message)
...                                 (* 2 message)
...                                 ("this will never execute"))))
...                     (transitions [(fn [message] (not (numeric? message))) stage-2]))
...              (stage-2 (on-activate (print "values will be quadrupled"))
...                       (active (if (numeric? message)
...                                   (* 4 message)
...                                   (.format "{0} is not a number!" message))))
=> (setv transmogrify (Transmogrifier))
values will be doubled
=> (transmogrify 2)
4
=> (transmogrify 4)
8
=> (transmogrify "max power!")
values will be quadrupled
"max power! is not a number!"
=> (transmogrify 2)
8

Clearly, finite-state machine would be a class, with a __call__ magic method that makes it to behave like a function (one of the features I like about Python). This example also uses :interface keyword to specify names of parameters the finite-state machine accepts. In addition to these changes, there’s some minor syntax clean-up. Macro expansion looks relatively simple still. For example:

(on-activate (print "values will be doubled"))
->
(fn [message] (print "values will be doubled"))

Example REPL session shows also execution order or semantics of the finite-state machine. When it is created, initial-state is activated and on-activate will run. After that, every time finite-state machine receives a message, transition checks are evaluated and state changed accordingly. After state check evaluation has completed, message is routed to currently selected active function.

There are still some noise in the syntax, that I wanted to trim down. The next iteration of the imaginary REPL session produced following code:

=> (statemachine TwistedAccumulator
...              :initial-state addition
...              :interface [message]
...              (addition (on-activate (state bonus 0))
...                        (active (when (odd? message)
...                                      (state bonus message))
...                                (+ message (state bonus)))
...                        (transitions [(= message 0) subtraction]))
...              (subtraction (active (when (odd? message) 
...                                         (state bonus message))
...                                   (- message (state bonus)))
...                           (transitions [(= message 0) addition]])))
=> (setv twister (TwistedAccumulator))
=> (twister 2)
2
=> (twister 3)
6
=> (twister 2)
5
=> (twister 0)
-3
=> (twister 9)
6

Since the interface is specified anyway, why not use it in transition checks too? Transition check will have automatic access to all parameters passed into the finite-state machine. I was a bit torn between making transition check-transition – pairs two element lists or not. From coding point of view, it’s equally easy and if code is broken to multiple lines sensibly, it doesn’t make much of a difference. In the end I chose to make them two element lists, just for the sake of little readability. I entertained idea of using parentheses instead of brackets, but that would go against the general style of Hy:

(transitions [(= message 0) subtraction]
             [(= message -1) multiplication])
vs.
(transitions (= message 0) subtraction
             (= message -1) multiplication)
vs.
(transitions ((= message 0) subtraction)
             ((= message -1) multiplication))

In addition, new symbol state is introduced. It can be used to assign or read a value of some symbol, that is stored into finite-state machine (these will probably be just plain attributes of the object).

This lead me back to thinking AI routines and the interface required. Currently I’m passing in model and random-number-generator and those would have to be present on each and every AI system the game has. My first thought was to eliminate them from statemachine and implicitly pass them. This has two drawbacks I can immediately think of: programmer has to remember that they are there, in case they want to access the symbols and statemachine wouldn’t be a general purpose anymore. The second one is easily solved by building a dedicated AI macro on top of the statemachine. The first one is bad, because it requires programmer to remember that they are there and recalling facts is always harder than recognizing them.

This concludes the drafting part of the language. Next step is to actually bust out Hy and start writing some code and trying out how these things really work in real world. But that I’ll save for a future post.

Advertisements

One thought on “Finite-state machines in Herculeum – part 1

  1. Pingback: Finite-state machines in Herculeum – part 2 | Engineer's Journey

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s