`LimboState` and multiple dispatch (aka flexible dispatch)

[hsoler]

Hey, I'm using the latest test build of the LimboAI project and I believe I've found a bug.

According to the official LimboAI documentation, a LimboStates's dispatch method

"Recursively dispatches a state machine event named p_event with an optional argument p_cargo. Returns true if the event was consumed."

The example below showcases that the dispatch method is not being recursively applied to parent LimboStates:

test.tscn.tar.gz

I've also inspected the source code, and I'm pretty sure that the dispatch method eagerly returns false if the event is not a key in its handler HashMap.

If this is not a bug but rather expected behavior, sorry for the inconvenience.

Thanks in advance.

[hsoler]

I've forked this repo and just pulled a request correcting this "bug"

[limbonaut]

Documentation could use some improvement here. The method should be called top-down rather than bottom up. From inside a state, it's get_root().dispatch(). And LimboHSM has an overridden implementation to support this. IIRC it's done this way because HSM.dispatch is also intended to be used from outside. For example, you may want to call hsm.dispatch("damaged") when an agent receives damage. In retrospect, I think it could be implemented or communicated better. I'll take a look at it next week.

EDIT: I can see that documentation is misleading here. While it's true that events propagate recursively from bottom to the root, the dispatch () method should always be started at the root. This can be improved (the requirement to call it at the root can be removed). And the return value needs to be documented, it indicates whether the event is consumed.

[hsoler]

Oh, now I see.

Then, my pull request actually breaks it.

By the way, do you intend to implement double dispatch (states and events are objects) in addition to mere dispatch (only states are objects)?

[limbonaut]

Are you talking in the context of add_event_handler? Technically, it is a multiple dispatch since the method called depends on both the current leaf state and the event string. Could you describe your use case in more detail?

[hsoler]

Suppose I want to implement the behavior of my PlatformCharacter2D using a State Machine with the following States and Events

states: resting moving-forward ____moving-forward-slow ____moving-forward-fast

events: command ____command-speed-up ____command-slow-down interruption ____interruption-left-floor ____interruption-hit-wall

Using the current form of method dispatch implemented in LimboHSM (which I called "single dispatch"), I can map specific pairings of (States; Events) to specific methods, such as

(moving-forward; command-speed-up) --[transition]--> moving-forward-fast,

while using the structure of containerized states for defining broad mapping behavior which specializes to the leaf states according to class inheritance rules:

(moving-forward; command-slow-down) --[transition]--> moving-forward-slow,

// specializes into

(moving-forward-slow; command-slow-down) --[transition]--> moving-forward-slow, (moving-forward-fast; command-slow-down) --[transition]--> moving-forward-slow,

// applicable only because more specific mappings were not declared in these contained states

The same specialization rules currently do not apply to Events, such that

(moving-forward; interruption) --[transition]--> resting

// does not specialize into

(moving-forward-slow; interruption-left-floor) --[transition]--> resting (moving-forward-fast; interruption-left-floor) --[transition]--> resting (moving-forward-slow; interruption-hit-wall) --[transition]--> resting (moving-forward-fast; interruption-hit-wall) --[transition]--> resting

The behavior in which both specialization arguments have the same "level" of inheritance or whatever other specialization rules implemented is what I call "double dispatch".

Multiple dispatch in its most complete form as I know it would require that I be able to dispatch based on as many specialization arguments as I'd like, and all of them would be subject to the same specialization rules.

I am asking this because I was looking forward to implementing more robust multiple dispatch techniques in LimboAI, similar to those I've had experience with in Julia. I am currently very displeased with all approaches to state machines I've seen in the Godot community so far. But I'm not sure if that type of functionality would be welcomed in the project as well, as it would certainly increase code complexity and likewise maintainability efforts over time, and it may just be out of its scope.

Also, just to be sure, it is the case that the intended behavior for the HSM dispatch method is to issue the dispatched event to the leaf state, and then the leaf state propagates the dispatched event from bottom to top until it finds a container state which handles the dispatched event or until it reaches the root state which dispatched it in the first place, right?

[limbonaut]

The reason why I opted for strings as events is not just simplicity, but also the potential to implement GUI editor for state machines in the future without breaking compatibility. Having events as strings will allow the user to create transitions in the GUI and can be implemented with relative ease. The events-as-objects approach would make things much, much harder for the GUI editor code. I can see the appeal for sophisticated HSM setups, though.

[hsoler]

Another possibility I've been tinkering with is the usage of a more feature-full Dispatcher class, which can map from any Array[Node] to any Variant.

If necessary, I could adapt it to accept Array[Variant] instead and specialize Nodes but not Strings from it, for compatibility. That should be already a great improvement over the dispatch method as is, since it would make the HSM able to handle concurrent states, including history-based machines, while not breaking any aforementioned GUI compatibility.

My proposal: let me implement a general-purpose Dispatcher and a naive Event class (just for having parents and children Events, holding a String name and being recognized as a type by the Godot engine). The Dispatcher can even be repurposed by users for non-state-machine contexts if they want to.

I have written a sketch of this functionality in GDScript (not tested it yet), in case I'm not precising my thoughts well enough:

features.tar.gz

Also, below I am pasting my sketch code of the Dispatcher, for ease of reference:

extends Node
class_name Dispatcher

# TypedNode is a Node with methods for miopycally accessing parents
# and children in regards to type (typeof(self) == typeof(x))

var handled_combinations: Array[Array] # Array[Array[TypedNode]]
var handlers: Array[Variant]

func insert_relation(combination: Array[TypedNode], handler) -> void:
    handled_combinations.push_back(combination)
    handlers.push_back(handler)

func find_handler(combination: Array[TypedNode]) -> Variant:
    for i in range(handled_combinations.size()):
        if handled_combinations[i] == combination:
            return handlers[i]
    return null

func dispatch(requested: Array[TypedNode]) -> Variant:
    if requested.is_empty():
        return null
    var res = find_handler(requested)
    if !res:
        return res
    var nodes: Array[TypedNode] = requested.slice(0)
    var i := -1
    while true:
        var j := -1
        while j > i:
            while nodes[j].get_typed_parent():
                nodes[j] = nodes[j].get_typed_parent()
                res = find_handler(nodes)
                if res:
                    return res
            if i == - requested.size():
                return null
            nodes[j] = requested[j]
            j -= 1
        i -= 1
    return null # never actually triggered

[limbonaut]

LimboAI is currently on the 1.0 release track with RC2 out, and I'm unwilling to take risky changes like these at this point, sorry. This is likely a 2.0 material, if it can get simple and understandable enough to be used by beginners. One of my main goals for LimboAI is for it to be newbie-friendly. And for that, I need to keep the API as simple as possible, so that there would be no reason not to use this plugin during game jams (if you need HSMs or BTs, of course). And that also means using simpler concepts and abstractions. Such cool things like flexible dispatch and parallelism need to be explained and taught, which would increase the learning curve, and I'm afraid it might turn away some users. I may be wrong here, and some things could certainly change in the future (including my opinion on the subject), but that's a 2.0 material (meaning compatibility-breaking changes, of course).

[hsoler]

Ok. Thanks for your patience and responsiveness.

I've decided thus to implement my functionalities as a separate module, which I will probably open the source code of, once it is mature enough. Since I am not interested in providing any GUI functionality nor am I targetting a more novice audience, it should serve as a complement rather than as an alternative to your project. If you ever happen to change your mind, feel free to contact me and I will surely be glad to port what I can.

[limbonaut]

Thanks for opening this issue. I wasn't aware of the dispatch problem, and it's improved now. And your ideas gave me plenty of food for thought. Curious to see your future SM implementation, and perhaps we can collaborate to bring LimboAI BT integration for it.