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.

Archimedes

I decided to split off macros used for Hypothesis into their own library called Archimedes. The package isn’t in PyPi yet and might never be there, since it’s not particularly useful as a Python library. One major thing that is still lacking is support for settings, but I don’t foresee that to be too difficult to implement. After that I’ll probably do a little bit cleaning up and call the library finished for now.

Hy, Nose and Hypothesis

I recently came across a tool called Hypothesis that immediately sparked my interest. Their documentation describe it as:

Hypothesis is a Python library for creating unit tests which are simpler to write and more powerful when run, finding edge cases in your code you wouldn’t have thought to look for. It is stable, powerful and easy to add to any existing test suite.

Stable, powerful and easy to add are all words that I like. And if you know me, you quickly guessed that I wanted a Hy interface for this new shiny tool.

Continue reading

Testing with Hy and Nose

I have been using Nose for the longest time and it’s my go-to tool for running tests. Nose is very no-nonsense and has very sensible defaults (to me at least).

Writing a test in Hy that gets discovered and executed with Nose is pretty straightforward. One just needs a correct naming convention and everything happens more or less automatically. However, by applying some standard lisp practices, one can cut down amount of the code needed quite a bit. In this post, I’ll present how my style of writing tests have evolved over time and what kind of measures I took in order to write minimum amount of code.

Continue reading

Little level dsl tricks

I have been tinkering with how levels are configured and made some minor changes. I’m trying to keep things relatively simple, but at the same time I want to have configuration code to look more like a configuration file than a function definition.

Below is shown a configuration for area called “first gate”. This is the area where the game starts. Two requires at the top are used to signal that I want to use certain macros. (level-config-dsl) is just a cute way to have pile of imports without cluttering the code. After that follows a list of levels, with just single entry. That entry first contains name and description of the level and rest is just configuring how it connects to other levels and how it is going to be generated. I made a post earlier explaining how the level generation works.

Continue reading

Writing macros with Hy

I have recently been working with some macros with Hy and wanted to write down some of things I have noticed or learned.

In lisp, code is essentially just a large tree (or bunch of lists inside of other lists). These lists are called s-expressions or sexprs for short. Following simple example demonstrates this:

=> (- (+ 2 (* 3 4)) (+ 1 1))
12

Functions work the same way, first element is the function being called and rest of the elements are parameters for that function:

=> (cut [0 1 2 3 4 5] 2 5)
[2 3 4]

One of the advantages of this system is that lists are generally pretty easy to manipulate. One can insert, remove and modify elements easily. If we consider a regular hy program, it’s just a collection of lists that define the code of the program. And this is where macros start to come into play.

A list macro is small snippet of code that can produce code or data (they’re essentially a same thing anyway). This lets programmer to automate writing some parts of the code. Instead of typing similar snippet of code over and over again, programmer writes a macro that does this for them. Since macro is an actual executable piece of code, it can inspect the parameters given to it and use them in its internal logic. They’re really great tool if you want to add new features to the language and extend it in ways that help you to write your programs more elegantly with less effort.

Continue reading

Cleaning up level generation

So, after a 5 month break, I got a feeling that I want to write some Hy code. First step was to fix level generation that was a bit broken, but that took only one evening. After that, I wanted to clean up the code a bit.

So, at that point I had a LevelGenerator class with a following method:

def generate_level(self, portal):
    level = new_level(self.model)
    partitioner = self.rng.choice(self.partitioners)
    connector = RandomConnector(self.rng)
    sections = connector.connect_sections(partitioner(level))
    for section in sections:
        generator = self.rng.choice(self.room_generators)
        generator(section)
    for adder in self.portal_adders:
        adder.add_portal(level)

    if portal is not None:
        rooms = list(get_locations_by_tag(level, 'room'))
        if len(rooms) > 0:
            new_portal = Portal(icons=(portal.other_end_icon, None),
                                level_generator_name=None)
            location = self.rng.choice(rooms)
            add_portal(level, location, new_portal, portal)

    for adder in self.creature_adder:
        adder.add_creatures(level)
    for adder in self.item_adder:
        adder.add_items(level)
    for decorator in self.decorator:
        decorator.decorate_level(level)
    return level

Nothing too complicated here. Create a new Level, chop it into partitions, connect them, draw some rooms and sprinkle with details.

The same code translated into Hy looked like this:

(defn new-level-generator [model partitioners room-generators decorators
                           portal-adders item-adders creature-adders
                           rng level-context]
  "create a new level generator function"
  (fn [portal]
    (let [[level (new-level model)]
          [partitioner (.choice rng partitioners)]
          [connector (RandomConnector rng)]
          [sections (.connect-sections connector (partitioner level))]]
      (ap-each sections ((.choice rng room-generators) it))
      (ap-each portal-adders (.add-portal it level))
      (when portal (let [[rooms (list (get-location-by-tag level "room"))]]
        (when rooms (let [[new-portal (Portal #t(portal.other-end-icon nil)
                                      nil)]]
          (add-portal level (.choice rng rooms) new-portal portal)))))
      (ap-each creature-adders (.add-creatures it level))
      (ap-each item-adders (.add-items it level))
      (ap-each decorators (.decorate-level it level))
      level)))

Again, nothing too fancy and a pretty straight forward conversion. There’s some repetition there though: multiple (ap-each foo (.bar it level) calls that loop through a list of builder objects and call a method to build level. I wanted to clean this up and flex my macro-writing skills.

First step was to unify their interface. Easiest way was to add new method:

def __call__(self, level):
    self.add_creatures(level)

This turns the builder object into callable, so I can call it like a function:

(ap-each creature-adders (it level))
(ap-each item-adders (it level))
(ap-each decorators (it level))

Next step was to get rid of the repeating (ap-each foo (it level)) for every type of builder:

(defmacro run-generators-for [level &rest generators]
  `(do ~@(map (fn [x] `(ap-each ~x (it ~level))) generators)))

run-generators-for macro needs two or more parameters. First parameter is the level being generated, rest of the parameters are lists of level builder objects (or functions). It will then create that ap-each code for each and every of them:

(run-generators-for level foo bar baz)
-->
(do
  (ap-each foo (it level))
  (ap-each bar (it level))
  (ap-each baz (it level)))

I reordered some of the code a bit and the end result was following:

(defn new-level-generator [model partitioners room-generators decorators
                           portal-adders item-adders creature-adders
                           rng level-context]
  "create a new level generator function"
  (fn [portal]
    (let [[level (new-level model)]
          [partitioner (.choice rng partitioners)]
          [connector (RandomConnector rng)]
          [sections (.connect-sections connector (partitioner level))]]
      (ap-each sections ((.choice rng room-generators) it))
      (run-generators-for level
                          portal-adders
                          creature-adders
                          item-adders
                          decorators)
      (when portal
        (let [[rooms (list (get-locations-by-tag level "room"))]]
          (when rooms (add-portal level
                                  (.choice rng rooms)
                                  (Portal #t(portal.other-end-icon nil) nil)
                                  portal))))
      level)))

Later on I will probably turn those level builder objects into functions, but this piece of code doesn’t need to know anything about it.

Macros are nifty

I have been trying to wrap my head around Hy macros and have made just a little bit progress. The concept is really powerful, but since it is so new to me, it is hard to find out where to actually use them. It seems that they are well suited on extending the language by building constructs that would be tedious to type or which would reflect on the problem domain better. In any case, I tinkered with them again and came up with not-so-useful infix macro. It allows the user to write code using infix notation, where the operator is in the middle, instead of in the beginning:

(defmacro infix [code]
  (quasiquote (
    (unquote (get code 1))
    (unquote (get code 0))
    (unquote (get code 2)))))

With this macro, one can write code like:

=> (infix (1 + 1))
2

Not very useful, but still nice little exercise in macro writing.

Hy and macros

Couple last evenings I have been working on macros and spend my time trying to wrap my head around them. Unlike in some other languages, macros in Lisp are actually executable code and can be used to generate more code. Macros are handled in macro expansion time. During this time the macros are executed and the code they generate is placed in the program. After the macro expansion the program can start running.

I wrote a very simple macro, that is not really even useful, other than to try out things:

(defmacro counter [x &optional y] (if y (quasiquote (+ (unquote x) (unquote y))) x))

The macro takes one or two parameters. If one parameter is given, the macro does not do anything. With two parameters, it calculates their sum.

If the macro is called with a single parameter like:

(counter 5)

the generated program code will be simply:

5

However, if the macro is called with two parameters:

(counter 5 5)

the generated program will be:

10

x and y don’t have to be simple values, they can be function calls:

(counter (+ 2 2) (- 6 4))

which results:

6

How does the macro work then?

(defmacro counter [x &optional y] (if y (quasiquote (+ (unquote x) (unquote y))) x))

When the macro is executed, first it checks is the y defined. If it is not defined, the x is returned and macro finishes. This causes the first parameter to be placed in the program code as it is.

If the y is defined, the macro starts generating code. Quasiquote is used to mark that the code after it should not be executed, but rather returned to the program. Unquote on the other hand makes sure that the value of parameter x is placed there, instead of letter x.