The Mud Connector

Author Topic: events and state machines  (Read 5576 times)

Maeglin - RealmsMUD

  • New to TMC
  • *
  • Posts: 21
    • View Profile
    • Realmsmud
events and state machines
« on: December 13, 2017, 1:52 PM »
In order to accomplish some of the more intricate aspects of what I wanted to do with my new mudlib, two constructs immediately came to the forefront: events and state machines.

For those who already know this (or those who suffer from ADD and/or don't like reading a page and a half long description about arched eyebrows and blushed cheeks), no need to read further - you're not the audience. For everyone else:

First, I'll cover events.

In its simplest implementation, an event handling system needs to allow an object to emit an event (or message) and allow a series of other objects to register such that when that event/message is emitted, they will be asynchronously* notified. Typically, this is done such that when the event occurs, a function is triggered. Littered throughout my lib, I have around 50 "canned events" - such as onMove, onAttack, onQuestStarted, and so on - and the additional support to allow creators to create their own custom events. (* In this context, asynchronous means that the event triggers calls to other objects in an "independent" way. Whether or not they truly happen in that way depends on how your game's driver deals with threads)

For example, you want a quest to be triggered if the NPC Ralph gets murdered by a player, you could register a quest object, an environment, whatever with the Ralph object and when his onDeath event happens, the onDeath method would then get called on all of those objects with info about the caller (Ralph's object) and any of the other data that's getting passed.

As with all of my stuff, examples are written in LPC, but going to any other language should be fairly straightforward. The implementation of this type of thing is really trivial:

- You need a method to tie objects you want to have "listen" for an event. The below code sets up objects that are registered to only get notified if they contain an implementation of the callback function being called.
Code: [Select]
public nomask int registerEventHandler(object subscriber)
{
    int ret = 0;
    if(subscriber && objectp(subscriber) && !member(eventList, subscriber))
    {
        string *eventsToAdd = ({ });
        foreach(string method in functionlist(subscriber, 0x01))
        {
    // validEvents is a list of all canned events in this lib plus
// any custom events that this object can emit.
            if(method && stringp(method) &&
              (member(validEvents, method) > -1))
            {
                eventsToAdd += ({ method });
                ret = 1;
            }
        }
        if(ret)
        {
        // eventList is simply a lookup table mapping the list of found
// event handler methods in the subscriber
            eventList[subscriber] = eventsToAdd;
        }
    }
    return ret;
}

- You need a method that allows an object to emit the event/perform a callback on all the subscribers.
Code: [Select]
public varargs nomask int notify(string event, mixed message)
{
    int ret = 0;
   
    if(event && stringp(event) && (member(validEvents, event) > -1))
    {
        // delete all null handlers
        m_delete(eventList, 0);
       
        // May want/need to limit calls of this method
        foreach(object handler in m_indices(eventList))
        {
            if(handler && objectp(handler) &&
              (member(eventList[handler], event) > -1) &&
              function_exists(event, handler))
            {
                if(message)
                {
                    call_other(handler, event, this_object(), message);
                }
                else
                {
                    call_other(handler, event, this_object());
                }
                ret = 1;
            }
            else if(handler && objectp(handler) &&
                function_exists("receiveEvent", handler))
            {
                call_other(handler, "receiveEvent", this_object(),
                    event, message);
            }
        }
    }
    return ret;
}

- You should also have methods for unregistering event handlers as well as registering/unregistering events.

I wrapped all of these methods in an LPC class (object/program/whatever) that could be inherited by anything that needs to broadcast events to various subscribers. For the subscribers themselves, nothing special needs to be done apart from having the proper callback methods.

Maeglin - RealmsMUD

  • New to TMC
  • *
  • Posts: 21
    • View Profile
    • Realmsmud
Re: events and state machines
« Reply #1 on: December 13, 2017, 1:55 PM »
Once an event handling framework is in place, it's time to move on to state machines. In simplest terms, any time you have a branch in execution (if statements, switch, etc), you've got some manner of state machine in action. However, branching very quickly becomes unwieldy. Enter finite state machines (or my preference, the UML state machine - https://en.wikipedia.org/wiki/UML_state_machine.) Using this pattern, you can make difficult problems get broken down into trivial, easy to follow steps. Driving a vehicle from space, beaming protons into cancer cells, and creating protocol stacks for disparate devices are just a few uses I've had professionally. In the software industry - especially for controls in the automotive/aerospace world, model-based software design is a big thing. That model? It's just a state machine. An engineer will make a state diagram and code will then be auto-generated for that design. My point? It's a good tool to know how to use and it really does make daunting tasks much easier to accomplish.

It turns out that rolling your own framework for this is pretty easy.

Before I get to that, let's come up with a quest: King Tantor the Unclean of Thisplace recently was told by Gorlak the Seer to not make any plans for Yule because, well, he'd be made dead in the coming days. As luck would have it, you have recently come to town and are unlikely to be the one who wants to murderize him. He solicits your help. If you choose not to help, there's still a window of opportunity to change your mind before he meets his untimely end. If you choose to help, you uncover a plot and encounter Earl the Grey, the assassin and slay him - that is, if you take the job seriously instead of reveling in the debauchery of the local scene.

Given that, I'll diagram the quests's state machine in the attached image.

Maeglin - RealmsMUD

  • New to TMC
  • *
  • Posts: 21
    • View Profile
    • Realmsmud
Re: events and state machines
« Reply #2 on: December 13, 2017, 1:56 PM »
This then gets translated into code:
Code: [Select]
/////////////////////////////////////////////////////////////////////////////
void Setup()
{
setName("Hail to the king, baby!");
setDescription("This is the description for this quest.");
addState("meet the king", "I've been asked to meet the king!");
addEntryAction("meet the king", "talkToKing");

addState("met the king",
"I met King Tantor the Unclean of Thisplace. He seems to like me.");
addTransition("meet the king", "met the king", "meetTheKing");

addState("serve the king",
"The king asked me - ME - to be his personal manservant. Yay me!");
addTransition("met the king", "serve the king", "serveTheKing");
addEntryAction("serve the king", "attackTheKing");

addState("ignore the king",
"I told the king to piss off. I have socks to fold.");
addTransition("met the king", "ignore the king", "ignoreTheKing");
addTransition("ignore the king", "meet the king", "converseWithKing");

addState("save the king",
"Earl the Grey tried to kill the king but I gutted him like a fish.");
addTransition("serve the king", "save the king", "hailToTheKing");
addFinalState("save the king", "success");

addState("king is dead",
"I must lay off the sauce - and the wenches. King Tantor is dead because of my night of debauchery.");
addTransition("serve the king", "king is dead", "maybeNobodyWillNotice");
addTransition("ignore the king", "king is dead", "killTheKing");
addFinalState("king is dead", "failure");

setInitialState("meet the king");
}

It's important to note that if an event comes and you're not in the proper state, nothing will happen. So, if you decide to talkToKing when you're in the "serve the king" state, you won't go through the meet/met the king stuff. Again, events are only acted on if the state machine dictates they should be.

So what does a state machine's framework code look like? As with the event stuff, it's pretty trivial to implement. This deviates slightly from the UML model in that transitions and guards are handled through the use of events:
Code: [Select]
//*****************************************************************************
// Copyright (c) 2017 - Allen Cummings, RealmsMUD, All rights reserved. See
//                      the accompanying LICENSE file for details.
//*****************************************************************************
virtual inherit "/lib/core/events.c";

protected string InitialState = "";
protected string CurrentState = "default";
protected object *stateActors = ({});
protected mapping stateTree = ([]);

/////////////////////////////////////////////////////////////////////////////
public void reset(int arg)
{
    if (!arg)
    {
        InitialState = "";
        CurrentState = "default";
        stateActors = ({});
        stateTree = ([]);
    }
}

/////////////////////////////////////////////////////////////////////////////
protected nomask void onEnter(string state)
{
    if (member(stateTree[state], "entry action"))
    {
        call_other(this_object(), stateTree[state]["entry action"]);
    }
    if (member(stateTree[state], "event"))
    {
        filter_objects(stateActors, "notify", stateTree[state]["event"]);
    }
}

/////////////////////////////////////////////////////////////////////////////
protected nomask void onExit(string state)
{
    if (member(stateTree[state], "exit action"))
    {
        call_other(this_object(), stateTree[state]["exit action"]);
    }
}

/////////////////////////////////////////////////////////////////////////////
protected nomask varargs void startStateMachine()
{
    if (sizeof(stateTree))
    {
        string *states = m_indices(stateTree);
        foreach(string state in states)
        {
            if (member(stateTree[state], "event"))
            {
                filter_objects(stateActors, "registerEventHandler",
                    stateTree[state]["event"]);
            }
        }
    }
    CurrentState = InitialState;
    onEnter(InitialState);
    notify("onStateChanged", InitialState);
}

/////////////////////////////////////////////////////////////////////////////
protected varargs string getCurrentState(object caller)
{
    return CurrentState;
}

/////////////////////////////////////////////////////////////////////////////
protected void advanceState(object caller, string newState)
{
    CurrentState = newState;
    notify("onStateChanged", newState);
}

/////////////////////////////////////////////////////////////////////////////
public nomask varargs int receiveEvent(object caller, string eventName, object initiator)
{
    int ret = 0;

    if (caller && objectp(caller) && eventName && stringp(eventName))
    {
        string currentState = getCurrentState(caller);

        if (currentState && member(stateTree, currentState) &&
            member(stateTree[currentState], "transitions") &&
            member(stateTree[currentState]["transitions"], eventName))
        {
            mapping transition = stateTree[currentState]["transitions"][eventName];
            ret = initiator && objectp(initiator) && member(transition, initiator) ?
                (transition["initiator"] == program_name(initiator)) : 1;

            if (ret)
            {
                onExit(currentState);
                currentState = transition["transition"];
                notify("onStateChanged", currentState);
                advanceState(caller, currentState);
                onEnter(currentState);
            }
        }
    }
    return ret;
}

/////////////////////////////////////////////////////////////////////////////
protected nomask varargs string setInitialState(string state)
{
    if (state && stringp(state) && (state != ""))
    {
        if (!member(stateTree, state))
        {
            raise_error("ERROR - stateMachine: the initial state must have been added first.");
        }
        InitialState = state;
    }
    return InitialState;
}

/////////////////////////////////////////////////////////////////////////////
public nomask string initialState()
{
    return InitialState;
}

/////////////////////////////////////////////////////////////////////////////
private nomask void addAction(string state, string action, string type)
{
    if (state && stringp(state) && action && stringp(action) &&
        member(stateTree, state) && function_exists(action))
    {
        stateTree[state][type] = action;
    }
    else
    {
        raise_error(sprintf("ERROR - stateMachine: an %s can only be added "
            "if both the state exists and the method to call has "
            "been implemented on this object.", type));
    }
}

/////////////////////////////////////////////////////////////////////////////
protected nomask void addEntryAction(string state, string action)
{
    addAction(state, action, "entry action");
}

/////////////////////////////////////////////////////////////////////////////
protected nomask void addExitAction(string state, string action)
{
    addAction(state, action, "exit action");
}

/////////////////////////////////////////////////////////////////////////////
protected nomask void addFinalState(string state, string result)
{
    if (result && state && stringp(state) && member(stateTree, state))
    {
        if (stringp(result) &&
            (member(({ "success", "failure" }), result) > -1))
        {
            stateTree[state]["is final state"] = result;
        }
        else
        {
            raise_error("ERROR - stateMachine: the final state result must be 'success' or 'failure'.");
        }
    }
    else
    {
        raise_error("ERROR - stateMachine: the state must exist for it to be set as a final state.");
    }
}

/////////////////////////////////////////////////////////////////////////////
protected nomask varargs void addState(string state, string description, string entryEvent, string isFinalState)
{
    if (state && stringp(state) && description && stringp(description) &&
        !member(stateTree, state))
    {
        stateTree[state] = (["description":description]);
        if (entryEvent)
        {
            if (stringp(entryEvent))
            {
                stateTree[state]["event"] = entryEvent;
            }
            else
            {
                raise_error("ERROR - stateMachine: the entry event must be a string.");
            }
        }
        if (isFinalState)
        {
            addFinalState(state, isFinalState);
        }
    }
    else if (member(stateTree, state))
    {
        raise_error(sprintf("ERROR - stateMachine: the '%s' state has already been added.", state));
    }
    else
    {
        raise_error("ERROR - stateMachine: the state could not be added.");
    }
}

/////////////////////////////////////////////////////////////////////////////
public nomask varargs void registerStateActor(object actor)
{
    if (actor && objectp(actor))
    {
        registerEvent(actor);
        stateActors += ({ actor });
    }
}

/////////////////////////////////////////////////////////////////////////////
public nomask varargs void unregisterStateActor(object actor)
{
    if (actor && objectp(actor))
    {
        unregisterEvent(actor);
        stateActors -= ({ actor });
    }
}

/////////////////////////////////////////////////////////////////////////////
protected nomask varargs void addTransition(string state, string newState, string eventName, string initiator)
{
    if (state && stringp(state) && eventName && stringp(eventName) &&
        newState && stringp(newState) && member(stateTree, state) &&
        member(stateTree, newState))
    {
        if (!member(stateTree[state], "transitions"))
        {
            stateTree[state]["transitions"] = ([]);
        }

        // This is a way around guards - send a different event to transition
        // to a different state.
        if (!member(stateTree[state]["transitions"], eventName))
        {
            stateTree[state]["transitions"][eventName] = ([
                "transition":newState
            ]);
        }
        else
        {
            raise_error("ERROR - stateMachine: a transition for that event already exists.");
        }

        if (initiator && stringp(initiator))
        {
            if ((file_size(initiator) > -1) && !catch (load_object(initiator)))
            {
                stateTree[state]["transitions"][eventName]["initiator"] = initiator;
            }
            else
            {
                raise_error("ERROR - stateMachine: the transition initiator must be a valid program name.");
            }
        }
    }
    else
    {
        raise_error("ERROR - stateMachine: the transition could not be added.");
    }
}

/////////////////////////////////////////////////////////////////////////////
public nomask string getStateDescription(string state)
{
    return member(stateTree, state) ? stateTree[state]["description"] : 0;
}
« Last Edit: December 13, 2017, 2:07 PM by Maeglin - RealmsMUD »

Maeglin - RealmsMUD

  • New to TMC
  • *
  • Posts: 21
    • View Profile
    • Realmsmud
Re: events and state machines
« Reply #3 on: December 13, 2017, 2:00 PM »
I should probably also add that in the entry actions, you would set up the various objects (king, user, king's castle/various rooms, Earl the Grey) and would also add event callbacks to make these objects do their various "things". If this level of detail's desired, I can certainly add to this example. I (for my quest usage of SMs) created a wrapper for the generic state machine specifically to add quest actors and whatnot and ease in the setup/coordination of these "outside the state machine" objects.
« Last Edit: December 13, 2017, 2:02 PM by Maeglin - RealmsMUD »

Epilogy

  • TMC Member
  • ***
  • Posts: 242
    • View Profile
Re: events and state machines
« Reply #4 on: January 27, 2018, 2:54 AM »
I would do it kinda like this with mprogs:

Code: [Select]
TALK trigger mprog1 -
if var $n kingtimeisoveh == 1
say Ahh, loyal servant! You did just save me, so I will allow you a brief moment to bask in my majesty.
break
endif
if var $n kingtimeisovah == 2
say I get the feeling you just killed me... but I can't honestly prove it.
mutter
say That crumpled doppleganger of me over there on the floor really should get cleaned up. Unsightly.
break
endif
if var $n kingtimebaby == 0
say Ohai, dudes. I'm the king. Haaai.
var $n kingtimebaby = 1
break
endif
if var $n kingtimebaby == 1
say You save me from badits, yes?
var $n kingtimebaby = 2
break
endif
if mob here banditguy
say Why are you talking when you should be saving?!
else
if var $n kingtimebaby == 3
say hmm... looks like you lost the fight, but I hear him coming again!
var $n kingtimebaby = 2
mob call mprog2 $n
endif
break
endif

RESPONSE POSITIVE mprog2 -
if var $n kingtimebaby == 2
var $n kingtimebaby = 3
say Oh, good. I was so worried, darl.. er.. loyal subject. I think I hear them now!
mob load banditguy
mob echo Bandit guy barges in, and makes a beeline for the king with their weapon drawn!
say HAAAAP!
mob force banditguy kill king
endif

RESPONSE NEGATIVE mprog3 -
if var $n kingtimebaby == 2
say Whatever, bai.
var $n kingtimebaby = 0
endif

DEATH trigger mprog4 -
if var $n kingtimebaby == 3
mob echo As the bandit dies, the king waddles over to you, proclaiming you lord of the blings.
mob force king say That was really showing them what for, old chap. Here, take my royal chain.
mob echo The king lifts his chain up over his head, and hands it to you.
mob voload dabling $n inventory
var $n kingtimebaby = 0
var $n kingtimeisovah = 1
mob echo The bandit guy dying on the floor weakly reaches for the chain, but you easily slap his hands away, and he ded.
endif

DEATH trigger mprog5 -
if var $n kingtimebaby == 3
mob echo The king's flabby little sausage fingers lose grasp of his scepter as he crumples.
say Oh woe, my kingdome... jah couldn't pay the biiiills!
mob voload $i evilbling inventory
mob force bandit say Was there anything good on him? Oh, the guards are coming, I'd better run!
mob echo The bandit snatches up his weapon, and scoots out of the chamber!
mob force bandit goto 8
var $n kingtimebaby = 0
var $n kingtimeisovah = 2
« Last Edit: January 27, 2018, 2:58 AM by Epilogy »

Maeglin - RealmsMUD

  • New to TMC
  • *
  • Posts: 21
    • View Profile
    • Realmsmud
Re: events and state machines
« Reply #5 on: January 27, 2018, 2:30 PM »
I'm glad you brought up branching constructs - technically, they're the most simplistic version of a state machine.

Branching (be it if/else, switch, etc) works adequately for more simplistic scenarios like the one I used as an example - and it can sometimes be the (greatly) preferred approach. However, it quickly becomes unwieldy. What if another external event might subtly change the behavior of all the actors? What if you have a dozen variables in play? That could feasibly lead to 479001600 (12 factorial) combinations of variables with billions of permutations that need to be sifted through. What if you need to have a few dozen objects interacting depending on how those variables are set? The state machine is still trivial to set up whereas the branching becomes extremely complex (especially when threading comes into play). And brittle. Add another variable or do another thing and you may need to refactor a bunch of script/code - code you wouldn't need to touch with a different design.

In a lot of automotive/aerospace applications, model-based designs like the state machine framework I wrote are heavily used as they save significant time to develop, are much more easily testable, and are much less complex to follow. To boot, there are tools in place that can turn a diagram you make into source code.

On an autonomous vehicle project I worked on I needed to drive the vehicle over a circle's arc long enough to figure out its center point so that the vehicle could then automatically track on (somewhat) concentric circles. Location inputs could come from GPS and/or a radio, speed and a bunch of vehicle-related data would come from vehicle controls... On a previous version of the control software going the "brute force branching method", the implementation was a bit over 15,000 lines of code. Using a state machine framework, I was able to accomplish the same with about 1/10 of the code.