Finite-state machines in Herculeum – part 3

Now that I have fully functional finite-state machine system, I can get started writing AI routines for the game, right? Apparently not yet. When inspecting the code, I realized that the finite-state machine system lacked a very important feature: ability to have values entered with –init– method. So that needed to be taken care of before starting to work with the AI.

Current implementation of rat AI is as follows:

(defclass RatAI []
  [[__doc__ "AI routine for rats"]
   [character None]
   [mode ["transit" None]]
   [--init-- (fn [self character]
           "default constructor"
           (.--init-- (super RatAI self))
           (setv self.character character) None)]
   [act (fn [self model action-factory rng]
      "check the situation and act accordingly"
      (rat-act self model action-factory))]])

–init– is used to give AI reference to the character it’s in charge of operating. act is called every time it’s characters turn to act. I could have changed the system to pass character reference as a parameter of act, but I wanted to keep interface unchanged for now, so chose to add –init– method for finite-state machine system instead.

–init– form of defstatemachine mirrors closely what –init– does for a regular class (in fact, it’s injected to be part of –init– method of final class). It takes a list of parameters and body of code. With this it was simple to define correct parameter list and rest of the game was happily ignorant that it was interacting with finite-state machine instead of plain old class (although, that finite-state machine is still a plain old class in the end of course).

Next design challenge I encountered was related with splitting common functionality into smaller pieces. I spent couple evening prototyping this with state monad from Hymn, but couldn’t come up with a system that I liked. With Hymn passing the state back and forth would have been taken care of automatically and behind the scenes, which was one of the attractive reasons for trying to use it. In the end (or should I say, for now?), I abandoned the idea and went with regular functions. This of course meant that I had to pass the state around manually and modifying it took a bit more coding. The end goal is to have some sort of library for AI routines that can be combined easily for new creatures. Getting a simple rat AI done was lots more work than what I anticipated, but I’m hopeful that next ones will be easier.

Final wart needing solving was the need for deactivation code. When a rat notices an enemy, it switches to a different state and a little exclamation mark is shown in UI to signal player that the rat is now in alert state. When rat loses the sight of the enemy, old AI used to raise a question mark to signal that the rat wasn’t sure about location of its target (they have lousy memory). I couldn’t raise the question mark in finding home state, since then it would be shown every time the rat decides to head home. Instead of that, there was need for codeblock that gets execute when state deactivates, but before next state is activated. Adding the state was almost identical on how on-activated is handled.

Now that I had all the major parts of the code ready, I could assemble whole thing and ended up with the following code:

(defstatemachine RatAI [model action-factory rng]
  "AI routine for rats"
  (--init-- [character] (state character character))

  "find a place to call a home"
  (finding-home initial-state
                (on-activate (when (not (home-location character))
                               (select-home character wallside?)))
                (active (travel-home (a-star (whole-level)) character))
                (transitions [(arrived-destination? character) patrolling]
                             [(detected-enemies character) fighting]))
  "patrol alongside the walls"
  (patrolling (on-activate (when (not (home-area character))
                             (map-home-area character
                                            (fill-along-walls (. character level)))) 
                           (clear-current-destination character))
              (active (one-of (patrol-home-area (a-star (along-walls)) character)
                              (wait character)))
              (transitions [(detected-enemies character) fighting]))
  "fight enemy"
  (fighting (on-activate (clear-current-destination character)
                         (select-current-enemy character closest-enemy)
                         (show-alert-icon character (current-enemy character)))
            (active (if (in-area area-4-around (. character location) 
                                 (. (current-enemy character) location))
                      (melee character (current-enemy character))
                      (close-in (a-star (whole-level)) 
                                (. (current-enemy character) location))))
            (on-deactivate (show-confusion-icon character))
            (transitions [(not (detected-enemies character)) finding-home])))

It’s pretty clear I think and should be easier to fine tune and adjust in the future. It certainly is much more reusable than the previous patrol AI code.

Here and there I used functions as parameters facilitate fine tuning algorithms. For example, when the rat is finding its way to home area, whole level is considered as valid ground for traveling. A* algorithm will try and find the shortest possible route. However, as soon as the rat arrives to home area, it switches to different mode and completely ignores anything but edges of rooms (and areas in front of doorframes, so it can pass those too). It’s still the same A* routine, but slightly differently configured.

Another example is shown below. It’s a function that maps character’s home area and assigns it to AI data:

(defn map-home-area [character neighbours]
  "build map of home area for character"
  (let [[state (ai-state character)]
        [to-check [(home-location character)]]
        [result []]]
    (while to-check
      (let [[it (.pop to-check)]]
        (when (not (in it result))
          (.append result it)
          (.extend to-check (neighbours it)))))
    (assoc state :home-area result)))

It basically does a flood fill from home location of character. Function that provides coordinates for neighbouring cells is provided from outside and its implementation or internal behaviour isn’t any concern of this function. As a consequence, this function (couple with the neighbours function) can be used to flood fill whole level, edges of room, center of room or any other continuous area. It could even be completely random random area that gets filled.

Most of the AI functions manipulate shared state in a way or another. I’m basing this on a convention, rather than contract. Any function can read, write and otherwise manipulate the state. This allows them to be combined in a way that I didn’t anticipate at the time of writing them. Problem of course is that if I’m not careful, unexpected interactions between those functions might arise and manifest as bugs.

This was also pretty tricky code to test. While coding, I kept thinkig that I should have some sort of automated system for testing the code, but it would be pain to write and maintain. I would have to set up whole level with creatures, items and worst of all, specific internal state of the AI. These tests would break all the time if even the slightest change was made in the internal representation of AI. In the end I decided that it wouldn’t be worth the gain to go through all that pain and just resolved testing the AI by playing the game. It’s slow process that will miss errors, but it’s still better than nothing (just not by that much).

Leave a Reply

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

You are commenting using your 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 )

Connecting to %s