(just hoping for a chat, working alone looking to the wall for too long this week!)

I'm building my own game engine (for personal development/studding) in C/C++, the Character class (the player for simplicity sake) is working great and I can make unitary actions to different states with little effort now.

But when it comes to chaining actions, I'm stuck at this bit for a wile and can´t decide on a good way to attack the problem.

I'm thinking about each state having it's own set of chains.

Using a tree of trees would be the most reasonable thing to do to store the chains, but each state would have so little potential chains (if any) that I feel it would be a wast of infra structure.

The rate at which new actions are accepted and time out to receive a new actions can be defined at the Character level or on each action link bases. I tend to prefer having this values decided at the Character as I can have some “Character Sheet” somewhere that auto generates this values and creates a consistent behavior for the player afterwards.

When a chain fails, it will execute the last action received.

When it succeeds, It will trigger a new predefined state.

How do you people prefer to implement this kind of solution?

Usually they're nested behavior trees. A behavior can trigger sub-behaviors. Generally there are also ways to tell characters the current sub-tree isn't working for some reason and to end their sub-tree.

Perhaps an example. A character gets a “meet another character at this location” behavior. This triggers a sub-behavior “travel to location” that doesn't specify a mode of travel. That might decide the best way to get there is by vehicle, so it triggers a “walk to location” to the vehicle's door, then “enter vehicle”, then “drive to lot" in the vehicle, then “exit vehicle”, then “walk to location” to get to the final target location. Each of those might trigger smaller sub-state machines of character behaviors and animations. When that finally finishes, the “meet with another character at this location” can verify the placement is still valid, then trigger an idle loop if the other character isn't there yet. That idle loop might include thinking, using a cell phone or radio, looking around, or whatever else. Eventually either the other character doesn't arrive so this behavior exits due to timeout, or the other character does arrive and they advance to the next state. The state may be both synchronize and play an animation (e.g. a handshake or salute), followed by both playing their talk animation loop for a short time.

I am trying to find a nice way for NPCs to interact with each other in a room for some time. For several rooms, there are a few NPCs together in a room, and each has a pattern of behavior in the room. Sometimes they act together (synchronized).

There are many animations with one or several NPCs, and these must be “played” for the user in the correct order at the correct location in the room. The room is aware of what NPCs are in the room, and tracks them (in particular, their state, see below).

In my current attempt I code for each single NPC different points in behavior as states in the room. (The points also somewhat relate to positions in the room in my case.)

A state is actually a function, which ultimately should start an animation and return from the call. The animation has a callback, and at the end of the animation the callback then jumps to the then-current state for the next animation to be started. Since a state executes code, it can also do computations, or decide something. As all states ultimately will start an animation, it can also jump to another state to continue computing there instead of starting an animation by itself. (At least in theory.)

To play animations with multiple NPCs, all participating NPCs must be at a certain state in their set of states. The room tracks the state of all NPCs, and thus can provide information a multi-NPC animation can be started. I haven't really decided yet, but it could even start the animation as well I think. It would need to update the state of all participating NPCs. Some NPCs here may not have an animation of their own, so they would need an external trigger for their callback. There are some options (use a timer, use an animation of 0x0 pixels, call their state from an NPC with animation), but not really decided about that yet.

Can you implement this structure in c++

#include <unordered_map>
#include <set>
#include <memory>

class Action;
class State;

using ActionPtr = std::shared_ptr<Action>;
using StatePtr = std::shared_ptr<State>;

class Character {
public:
    // ... other character methods ...

    void performAction(const ActionPtr& action);
    void setState(const StatePtr& state);

private:
    StatePtr currentState;
    std::unordered_map<StatePtr, std::unordered_map<ActionPtr, std::set<ActionPtr>>> chainMap;
    
    // timing system
    float actionAcceptanceRate;
    float actionTimeout;
};

class State {
public:
    virtual void enter(Character& character) = 0;
    virtual void exit(Character& character) = 0;
    virtual void update(Character& character, float deltaTime) = 0;
};

class Action {
public:
    virtual void execute(Character& character) = 0;
};

Actually this structure allows you to easily define new states and actions, and to configure complex chain relationships between them. The Character class manages the current state and the chain map, while also handling the timing system for action acceptance and timeouts.

But to use this system you would:

1. define specific State and Action subclasses for your game.
2. configure chainMap for each state with its possible action chains.
3. implement performAction method to handle chain execution, timing, and state transitions.

frob said:

Usually they're nested behavior trees. A behavior can trigger sub-behaviors. Generally there are also ways to tell characters the current sub-tree isn't working for some reason and to end their sub-tree.

My case is MUCH simpler, I just need to keep track of input keys, for things like combo attacks.

So yea, trees all the way down, it would be a simple choice (but hard to implement) if I was centralizing ALL the possible chains or using the same to every single character. But since this is an engine and I need to offer flexibility, there must be a way to auto map these things (like processing the output of a script) and implement behavior with little effort just with some interfaces.

I guess this will be the smart move anyway, a little effort now to make the tree work and I have a VERY flexible solution afterwards.

Alberth said:

There are many animations with one or several NPCs, and these must be “played” for the user in the correct order at the correct location in the room. The room is aware of what NPCs are in the room, and tracks them (in particular, their state, see below).

It doesn't seam we are working with the same usecase, environment triggers and such are handled by a different routine I think. Wouldn't be easier to work with events for that?

Like just send a event to all the NPC in the room when the trigger happens and each can check independently if they should react or not.

Bighossss said:

Can you implement this structure in c++?

Well… yes….

https://gameprogrammingpatterns.com/state.html

https://gameprogrammingpatterns.com/command.html

It is quite boring to create a new state and a little too much effort to create new commands, but in the end it is a breeze to change an existing behavior or debug.

Ha!

An N-ary Tree is just a list of lists!

The questions now is, should I encapsulate the implementation in a NTree class?

Hummmm there are some use cases for that, like optimizing search and remove later on in the far away future……….

TooOld2rock-nRoll said:
It doesn't seam we are working with the same usecase, environment triggers and such are handled by a different routine I think. Wouldn't be easier to work with events for that?

I don't have much environment, and everything is quite fixed. The main differences are in different position/orientation of devices that the NPCs use in the room.

Who does what is also fixed, there is very little to decide at runtime except for a little random thrown in for variation.

There are a few more global events, but either there is nothing left to decide (they are all dead instantly), or it is very limited (the NPC that is more tired leaves the room when a replacement arrives).

It's very possible my problem is too different from yours. I wasn't sure, and thought it might be interesting.

@Alberth Yes, it is interesting! You were not wrong to jump in.

Simple is better! When you have very well defined limits to what is expected and how to handle those, implementing things the way you describe is a good idea.

Besides, game architecture is always a difficult/interesting subject, different developers with slightly different problems will have different needs and come to different solutions.

Going by the book all the time with state of the art algorithms is not a good general suggestion.