Let’s get some tests directly on the Finite State Machine. Maybe give it a little shot of YAGNI.

Inside the Dungeon program (affectionately called “Dung” in my parlance), the finite state machine class FSM is pretty well tested, because the NPC class tests (or used to test) everything that the direct FSM tests don’t check.However, if we wanted to have FSM as a separate “library” project, we’d want tests for all its aspects.

Plus, I have in mind adding at least one feature that I don’t really need, the ability to attach a callback to a particular event or state transition (I’m not sure which, yet). Yes, that’s YAGNI, since I don’t need it, but I have a few good reasons for doing it: I have an idea for how it can be done and want to document it; if FSM is general utility, it will in fact need the feature; and I want to.

I think that last one may be the main reason. Don’t try this at work. Or do, I’m not the boss of you.

I would also like to allow the FSM user to embed arbitrary data in the FSM. Here’s why. Currently, in NPC, we have a table of messages for the Horn Girl:

function NPC:init(tile)
    Bus:subscribe(self, self.catPersuasion, "catPersuasion")
    tile:moveObject(self)
    self.sprite = asset.builtin.Planet_Cute.Character_Horn_Girl
    self.messages = {
    "I am your friendly neighborhood Horn Girl!\nAnd do I have a super quest for you!",
    "I am looking for my lost Amulet of Cat Persuasion,\nso that I can persuade the Cat Girl to let me pet her kitty.",
    "If you can find it and bring it to me,\nI shall repay you generously.",
    "Thank you!"}
    self.messageNumber = 1
    self.fsm = FSM(self:hornGirlTable())
end

Since NPC is supposedly a general non-player character class, it would be good if it didn’t include specific methods or data for specific NPCs. It’s easy to see that we can store anything at all in the FSM table, so long as we keep away from the things the FSM looks for, so in a sense, the feature is already there.

I’d like to change NPC to do that, and I have a card for it so that I won’t forget.

FSM Now

FSM is small, so we can afford to look at it as a whole here:

FSM = class()

function FSM:init(tab)
    self.tab = tab
    self.fsm_state = tab.initial or "none"
    self.tab.callbacks = self.tab.callbacks or {}
end

function FSM:cannot(event)
    return not self:can(event)
end

function FSM:can(event)
    return self:performAccepted(event)
end

function FSM:event(event)
    local cb = self.tab.callbacks
    return self:performAccepted(event, function(trans)
        if cb.on_leave_state then
            cb.on_leave_state(self, event, trans.from, trans.to)
        end
        if cb.on_enter_state then
            cb.on_enter_state(self, event, trans.from, trans.to)
        end
        self.fsm_state = trans.to
    end)
end

function FSM:performAccepted(event, f)
    for i,trans in ipairs(self.tab.events) do
        if trans.from == self.fsm_state and trans.event == event then
            if f then f(trans) end
            return true
        end
    end
    return false
end

function FSM:state()
    return self.fsm_state
end

Oh, here’s something worth mentioning. It’s quite possible to create the FSM instance with different tables from the original, as we’ve done here. You can build, from the input tables, a couple of auxiliary structures that will be faster than our current scheme of searching the whole table to find out whether we can do a transition.

We have no known need to do this, and the current structure is easy enough to understand and manipulate. If we did ever decide to do that, we should be able to do it under the covers without changing our public interface. But we probably won’t.

Let’s review the FSM tests while we’re here:

function testFSM()
    CodeaUnit.detailed = false
    
    local fsm
    
    _:describe("FSM - Finite State Machine", function()
        
        _:before(function()
            local tab = {
                initial = "s1",
                events = {
                    { event="go", from="s1", to="s2" },
                    { event="back", from="s2", to="s1" },
                }
            }
            fsm = FSM(tab)
        end)
        
        _:after(function()
        end)
        
        _:test("FSM with no initial starts at none", function()
            local tab = {
                events = {
                    { event="go", from="s1", to="s2" },
                    { event="back", from="s2", to="s1" },
                }
            }
            local my_fsm = FSM(tab)
            _:expect(my_fsm:state()).is("none")
        end)
        
        _:test("FSM can and cannot", function()
            _:expect(fsm:state()).is("s1")
            _:expect(fsm:can("go"),"does she go?").is(true)
            _:expect(fsm:cannot("back"), "back").is(true)
        end)
        
        _:test("FSM changes state", function()
            _:expect(fsm:state()).is("s1")
            fsm:event("go")
            _:expect(fsm:state()).is("s2")
            fsm:event("back")
            _:expect(fsm:state()).is("s1")
            fsm:event("unknown")
            _:expect(fsm:state()).is("s1")
        end)
        
    end)
end

Let’s add a test for the callbacks. We actually support two, on_leave_state and on_enter_state. The first is triggered right before we leave any state, and the latter before we enter the new state.

In at last one of the Lua FSM programs, and in the JaveScript version they’re emulating, some of the callbacks can return false, indicating that the transition cannot take place. We have no need of that and I don’t plan to do it until we have. But I do want, at least, to test these two callbacks.

Our standard before FSM doesn’t have callbacks. We could add them in there, or do a separate test that adds them. The former is easier, but I think the latter is more clear.

        _:test("Callbacks", function()
            local entered = false
            local left = false
            local tab = {
                initial = "s1",
                events = {
                    { event="go", from="s1", to="s2" },
                    { event="back", from="s2", to="s1" },
                },
                callbacks = {
                    on_enter_state = function(fsm,event,to,from)
                        entered = true
                    end,
                    on_leave_state = function(fsm,event,to,from)
                        left = true
                    end
                }
            }
            fsm = FSM(tab)
            _:expect(entered).is(false)
            _:expect(left).is(false)
            fsm:event("go")
            _:expect(entered).is(true)
            _:expect(left).is(true)
        end)

The test runs, but it should. I’ll break it to be sure, by setting that last true to false.

4: Callbacks  -- Actual: true, Expected: false

OK, I’m convinced these work.

Now I want to do a specific callback, to document how to do it. I want to implement a callback for on_enter_STATE, where STATE is a specific state in the FSM. Test should be easy to write:

        _:test("on_enter_STATE callback", function()
            local entered = false
            local tab = {
                initial = "s1",
                events = {
                    { event="go", from="s1", to="s2" },
                    { event="back", from="s2", to="s1" },
                },
                callbacks = {
                    on_enter_s2 = function(fsm,event,to,from)
                        entered = true
                    end,
                }
            }
            fsm = FSM(tab)
            _:expect(entered).is(false)
            fsm:event("go")
            _:expect(entered).is(true)
            entered = false
            fsm:event("back")
            _:expect(entered).is(false)
        end)

This should fail expecting true. Sure enough:

5: on_enter_STATE callback  -- Actual: false, Expected: true

Let’s review our callback code:

function FSM:event(event)
    local cb = self.tab.callbacks
    return self:performAccepted(event, function(trans)
        if cb.on_leave_state then
            cb.on_leave_state(self, event, trans.from, trans.to)
        end
        if cb.on_enter_state then
            cb.on_enter_state(self, event, trans.from, trans.to)
        end
        self.fsm_state = trans.to
    end)
end

I see some duplication here. And I propose to add a bit more. I think our specific callback should run before the generic one.

function FSM:event(event)
    local cb = self.tab.callbacks
    return self:performAccepted(event, function(trans)
        if cb.on_leave_state then
            cb.on_leave_state(self, event, trans.from, trans.to)
        end
        local callback = "on_enter_"..trans.to
        if cb[callback] then
            cb[callback](self, event, trans.from, trans.to)
        end
        if cb.on_enter_state then
            cb.on_enter_state(self, event, trans.from, trans.to)
        end
        self.fsm_state = trans.to
    end)
end

We create the callback name dynamically, check to see if it it in our callback table cb and if it is, we fetch the callback function and execute it.

I expect the test to run now. (I admit I’m a bit nervous about it, this is rather tricky.)

It does run. Before we commit, let’s refactor to remove that duplication.

I write this handy method:

function FSM:doCallback(callbackName, event, trans)
    local cb = self.tab.callbacks
    if cb[callbackName] then
        cb[callbackName](self, event, trans.from, trans.to)
    end
end

(I’m doing an Extract Method, but by hand.)

Now I can change the event method to use this handy method:

function FSM:event(event)
    local cb = self.tab.callbacks
    return self:performAccepted(event, function(trans)
        self:doCallback("on_leave_state", event, trans)
        self:doCallback("on_enter_"..trans.to, event, trans)
        self:doCallback("on_enter_state", event, trans)
        self.fsm_state = trans.to
    end)
end

Now that, if I do say it myself, is rather nice.

Commit: improve tests and factoring for FSM. Implement state-specific enter callback.

Data Storage

What about the data storage idea? Let’s have the convention be that you add a table data to the FSM table, and put all your specific data in there. Not much to test in FSM: it’ll never look at data but in NPC we’ll need some changes.

Here’s what we want to write. I’ve moved the messages table out of init and into the FSM table:

function NPC:init(tile)
    Bus:subscribe(self, self.catPersuasion, "catPersuasion")
    tile:moveObject(self)
    self.sprite = asset.builtin.Planet_Cute.Character_Horn_Girl
    self.fsm = FSM(self:hornGirlTable())
end

function NPC:hornGirlTable()
    local tbl = {
        initial="m0",
        events = {
            {event="query", from="m0", to="m1"},
            {event="query", from="m1", to="m2"},
            {event="query", from="m2", to="m3"},
            {event="query", from="m3", to="m1"},
            {event="received", from="m0", to="ty"},
            {event="received", from="m1", to="ty"},
            {event="received", from="m2", to="ty"},
            {event="received", from="m3", to="ty"},
        },
        callbacks = {
            on_enter_state = function(fsm,event,from,to)
                self:setMessage(to)
            end,
        },
        data = {
            messages = {
                "I am your friendly neighborhood Horn Girl!\nAnd do I have a super quest for you!",
                "I am looking for my lost Amulet of Cat Persuasion,\nso that I can persuade the Cat Girl to let me pet her kitty.",
                "If you can find it and bring it to me,\nI shall repay you generously.",
                "Thank you!"
            },
            messageNumber = 1
        }
    }
    return tbl
end

Now the NPC tests should break profoundly.

1: Recognizes cat amulet -- NPC:104: attempt to index a nil value (field 'messages')
2: transitions and messages -- NPC:104: attempt to index a nil value (field 'messages')

Yes. And we get a nice pointer to where to look:

function NPC:setMessage(num)
    local tab = {m1=1, m2=2, m3=3, ty=4}
    self.msg = self.messages[tab[num]]
end

Ah, we need to put that table inside the FSM also. But the convention is, the message to display will be put into self.msg, so we’ll leave that.

First move the table and give it a better name:

        data = {
            messages = {
                "I am your friendly neighborhood Horn Girl!\nAnd do I have a super quest for you!",
                "I am looking for my lost Amulet of Cat Persuasion,\nso that I can persuade the Cat Girl to let me pet her kitty.",
                "If you can find it and bring it to me,\nI shall repay you generously.",
                "Thank you!"
            },
            messageNumber = 1,
            stateToMessage = {m1=1, m2=2, m3=3, ty=4},
        }

And now:

function NPC:setMessage(num)
    local data = self.fsm.tab.data
    local msgIndex = data.stateToMessage[num]
    self.msg = data.messages[msgIndex]
end

And this test needs changing:

        _:test("transitions and messages", function()
            local msg
            local npc = NPC(FakeTile())
            local fsm = npc.fsm
            msg = npc:query()
            _:expect(msg).is(npc.fsm.tab.data.messages[1])
        end)

It needed to look for the message in the data table. We could make it a literal, but we’re currently relying on the Horn Girl data in our tests. Not really a great thing, but we’ll deal with it when it starts to bother us.

I think that the parameter num in setMessage is wrong. I think it is a state name.

function NPC:setMessage(state)
    local data = self.fsm.tab.data
    local msgIndex = data.stateToMessage[state]
    self.msg = data.messages[msgIndex]
end

Commit: NPC now stores character-specific data in the FSM table.

Super. Let’s sum up.

Summary

We set out to improve the FSM tests so that they’re complete when it’s used as a “library” dependency, and accomplished that.

We added an example of how to do state- or event-specific callbacks, including a test to be sure that it worked.

Then we modified NPC so that all the character-specific data is stored in the character’s FSM. Which reminds me: are we even using that messageNumber?

No, it’s a leftover. Remove it, commit: removed redundant and unnecessary messageNumber from NPC FSM table.

Nice.

Everything went very smoothly. Almost seems odd. Looks like we picked slices of the right size this morning.

Now for Sunday brekkers with my honey. See you next time!

D2.zip