I want to create a an ai with finely customizable character. The ai should be able to handle generic behavior shared across all character, but have specific override for group of character called persona, and override for unique character behavior, in that order: generic -> persona -> unique character. It allows a mix of simulation and scripting (ie story, unique situation, unique interaction and behavior).

I thought about using an "if tree" (KISS principle) with behavior tree pattern. Basically imagine it's a bunch of cards. Cards have a check, then a body of actions when the check is passed, cards can be nested as actions of other card, return; (or break() if I implement as class) is a specific action that terminate the execution of the whole tree. But I'm stumbling on some issue.

Override for specific, could happen at any branches of the if tree, and it makes it harder to write code that separate generic and unique code, because a top level card can be specific to a character, but lower behavior be a mix of generic and specific, making it hard to untangle the two. It makes it hard to propagate change during dev, because number of behavior card can reach up to tens of thousands. That makes it that a lot of card would be identical variants save for a few actions, and updating them all would be a nightmare.

On top of that, breaking the ai code into multiple files makes it harder to track the logic (KILL principle, folding IF is just more efficient) and debug specific vs generic behavior, especially when the tree becomes deep. my problem is highly localized to the behavior variants problem.

After staring at the problem for a while, I realize there is mostly 4 cases:
- Insertion: I insert behavior with card in the form of "isaX()" check, it append new behaviors in the action list.
- Inhibition: basically I prevent a card from firing off for certain character and is in the form of "& !isaX()" so when identifier X is detected, the card return false and the behavior is not started.
- Substitution: basically I need to replace actions and maybe checks, but keep subtree intact. Right now it's a bunch of inhibition checks for action in the list.
- Replacement: basically it's a whole new tree that bypass the behavior for another one. Typically implemented as inhibition, of the old tree and append of a new tree, with an "else" structure.

The key things seems that, if I put everything in an actual list, I can at least insert stuff to generic behavior without having the generic BT and the specific BT having to KNOW each other, like through a linking object... That's an idea, but that mean implementing the card idea properly as class and not a metaphor, but I don't see it the direct benefit for the problem. I haven't figured out how to abstract them yet. And I also have a lot of hardcoded interactions for multiple character interactions, I haven't figured out how to formalize that part yet BUT I leave that for later, one problem at a time.

For informations:
The whole architecture so far is: a world manager that manage entities, a utility like tree (UT) for perception (match concepts instead of actions) that query the world and internal state, a behavior tree like (BT) that sets "state variables", and a state machine that actually implement actions based on those vars.

BT is great because it's an abstraction between a planner, a script and a state machine, but I use a separated state machine to handle actions, it's simpler to handle temporal aspects (wait the action to finish) and makes transitions more explicit. Same for separating UT and BT, it's convenience to follow the character logic better.

Only missing is inheritance, I couldn't figure out how to add it without exploding the maintenance cost (KISS & KILL) and the solve the exposed problem. Inheritance works great when the structure are quite atomic, but what if the you want to patch a tree? I'm not sur how using it would help.

I'm not sure building a tools for edition will help, it will just translate the problem to a new structure and have a cost to build and maintain for no advantage for a solo dev.

What architecture or programming design pattern you would recommend to cope with these difficulties? Specifically how to manage the explosion of card variants? Have you ever been in such situation? How did you manage it?

Good question!

Let me restate and slightly generalize your setting. It looks like you want to work with a large number of rules, which you represent via trees/nodes (here, “work” = “define”, “view” and “edit”; all these operations must be easy). Final (effective) behavior for each actor is assembled from these parts by editing/combining them somehow into a larger tree.

Note that:

• the rules themselves are simple; the complexity arises from managing them
• from a certain philosophical angle, you want to define two “languages": one to define behavior rules (conditions and actions), and the other one to operate over these rules (combine/edit)
• On one hand, you do not want to repeat definitions in the code, so you will try to define everything in classes and reuse ("inherit") large chunks of logic. On the other hand, if you do so, it will be hard to quickly build a mental model of the final trees (which specific rules are associated with the actor), because it is assembled from parts scattered across many files

If I got everything right, then this should help:

• Let's try to think about actors' behavior not as code, but as a configuration. Why don't you define generic usable parts (specific checks and actions generic logic) in the code; but build rules in a separate configuration file, like XML/JSON/ad-hoc text (by importing/instantiating/preprocessing code-defined parts)? This explicitly puts definitions in different “languages” into separate files, splitting generic and unique.
• When you have large trees, they become hard to comprehend at a glance. I find complex behavior expressed with decision tables is easier to read. (Very opinionated) Take this recipe: each row is a rule; each column is a check/variable name, and cells contain conditions (">1", "=true"). Empty cell means "not used/ignore"; and last column contains 'action'. During runtime, first row with all conditions satisfied gets selected, and corresponding action is chosen. If you also assign names to rows/groups of rows, you get a neat way to reference rows in operations over these rules (ex: one group may define a "persona", as in your example; ).
  In my opinion, thinking in terms of ‘editing’ cells and adding/removing rows is easier than thinking in terms of trees and some ‘tree patching’. So, I recommend tables, they are cool.
• It looks inevitable that you have to write at least some infrastructure code for your problem. You need a preprocessor for the configuration files (to parse files and perform an operation over rules/resolve inheritance) that will ultimately transform configs into importable .cpp files (or whatever target you choose). No need to write a config editor! Use CSV files to store configurations (=decision tables), and Excel to edit them. So so convinient!
• A final touch: at the end of the preprocessing, you get effective rules for each actor (an expanded tree with all 'inherited'/'imported' rules pulled down). Export it somewhere as documentation. Now, you can edit the rules in a compact form with inheritances and reuses, but also you can view what's the end result looks like.

I am aware that ~half of the suggestions are overkill in your situation; but had to mention them for completeness anyways. Btw,

inheritance

“composition over inheritance”! : )

I may have gotten something wrong; but it looks like I stumbled on a similar problem in my project too. If all this is of relevance, feel free to PM me.

I want to provide further context:

• i'm a solo dev (so far)
• I'm a designer, programming is scary, especially maintenance of complex tools
• the game (currently) is yandere simulator meet buffy the vampire slayer (to avoid the seedy and shady part of the yandere simulator's concept)

@rampeer I'm gonna say your analysis is pretty spot on! I had a relief reading it :D

Your linear idea is probably a solution I was looking for, but not in the way you think, it's easy to turn a tree a tree (depth first order), then to "mask" with insertion and inhibition nodes for specifics. BUT I have no idea how to do that yet, in clear code. That is how keep them clean for each character and execute. There is 3 things to handle that: An ID for each node, to find matching node, an address within the tree for insertion, a versioning number in case the tree change and we need to detect possible conflict.

BUT

rampeer said:
the rules themselves are simple; the complexity arises from managing them

rampeer said:
When you have large trees, they become hard to comprehend at a glance.

About those point: YES and NO:

• YES: the issue is exactly as I say, it's becoming hard to untangle variants, if I have a character that I want to remove, the issue is dispersion, ID check for that character are everywhere at all level, and a character is an exception, so there is no real pattern to find where the unique case could happen.
  
• NO: the way the tree is organized is from the state machine, each branches do exactly one idea, so a branch is like a rule, and there is sub rules. Because of that organization, it is extremely fast to comprehend, you only unroll the tree to get more precision about the behavior, for example if(SCHEDULE) is where you handle the scheduling, obviously, and if(INVESTIGATION) will contain each everything about investigation, both will have persona/character specific override.

ALSO Modern IDE have block folding, so you only see the scope of what you want, the SCHEDULE state have like 10 000 lines, it looks scary but that's an illusion, most are contained in variant in INVESTIGATIONS and CLUB ACTIVITY, there is lots of clubs x characters and investigation method x persona (x scariness level), each are small and contained. It's easy to append and move tree, by collapsing a block, then cut and paste, but you rarely do anything with cut and paste, you generally just append.

It's like navigating a folder, and originally I was cutting those sub tree into their file, BUT I end up having to navigate the folder the same way as code folding, and the shuffling of file was painful, so I left them in a single file. And there is mostly 3 big states: SCHEDULES that handle daily routine according to a time table, EVENTS that manage everything that breaks from routine, handle story “scripts” (they are sub simulation), REACTIONS which is the interruption to immediate actions like witnessing something. They are interlink through simulations because what happen in character and events can affect schedule for example, because a character can shift persona after an event or reaction (like becoming depressed or distrustful).

@frob

frob said:
We used that in The Sims

OMG, I pour so much time studying the sims before making my system! I pour over everything Kevin Mill and Dave Mark wrote too! In the end their ideas was too rigid to work as is for the complexity of my project. I pick apart the system and build by my own from the lesson I learn from it. It worked in the sims, because the simulation in the sims is simplistic, most behavior are abstract in the presentation and story. I end up going for a model like in Yandere Simulator which mixed some old game model (Tokimeki memorial on SNES or GB) but with modern sensibilities, it has a sensible simulation system that is allow to blend multiple level of specificity.

frob said:
Behavior trees still work for what you described.

Technically I still use BT, but as a pattern. I probably need to clarify something:

• it's not a decision tree, decision tree have action on leaf, I'm not just selecting actions, I run as many of them as necessary.
• It's not a plain BT, BT run only one action at a time, I'm technically a BT where you have a lots of concurrency between actions.
• It's not a utility tree, same problem as the two above, only one actions at a time, they are good for reactive, combat character, but not for complex character simulations.
• It's not just a state machine, state are kinda blended into each other, it's also hierarchical.
• It's not an expert system, I'm not just matching rules.
• It's probably close to an ad hoc HTN planner.
• It's close to scripting, with sequence of command, but without a specific scripting language.

Basically I learned from all the basic model, and use their pattern to organize an if tree, where actions can happen at any point of the hierarchy, in someway it can be seen as nested shallow BT with lots of concurrency. A BT pattern in plain if code look like this:

• if(action()) or if(x > action()) where action() or the test return a bool and is a co routine or an async. This encode the fail/success part of the BT and allow to manage the flow.
• {return;} as a body of the if action encode the priority pattern, it mean you exit as soon as true is reach
• {}else{return;} as the body encode the sequence pattern, that is exit as soon as false is reach, equivalent to using a not in the if test like if(!action())
• IN MY CODE, I do it like if(checks){action(); return}, because the actions doesn't manage the running state, I use the state machine for persistence and mostly encode state transition.

In someway it's a synthesis of all the paradigm. If anything in AI, actions tend to closely match animation, HERE animation is strongly decouple, I manage state, and state call animation. The one thing animator use, is a blend tree to make animation flow into each other instead of being atomic, well it's close to to an animation blend tree but adapted to behavior state instead.

frob said:
Your weighting functions for determining utility can also use that structure, a certain action can have different weights based on the results of a query to the structure. If they have the unique character attribute that matches any for the behavior then that weight is used, if not if they have a persona that matches any then that weight is used, otherwise the generic weighting is used. Inhibition is just a negative weight. It might be a small thing, maybe -30 points, or maybe a bigger issue of -9000 points, or maybe maximum negative points.

I'm gonna be frank, the weighting is almost non existent (so far), it wasn't needed, the current UT is a stub for when stuff will become more complex, but mostly to separate perception from decision, the BT separate decision from actions, I distributed the various paradigm with the cybernetic structure of sensing, deciding, acting. the UT DOES NOT select actions, just perception concepts to be fed to the BT (for checks). and the BT DOES NOT select actions, only set internal states for another system to fire actions. It makes reading code much clearer by separating concern (the photoshop of ai in some way).

frob said:
Details will depend on your tools and your implementation, but basically you need your behaviors to allow for attachment points. You will also need to provide a structure you can test for the specific type.

That's the problem I have though, this mean adding attachment almost at every line and actions. The idea is to come on a strategy for that. Maybe if I make a class “actions” that can detect it's own variant in some way, I don't know, I have no idea how it would be like and useful.

Thanks for those insight, that's some food for thought.

A representation as planning, apart from being a good fit for rather complex behaviours and agent states, would address customization neatly: at any stage of the planning hierarchy, adding a custom rule like “if game state state satisfies predicate W, agent X can do Y by doing Z” (in addition to, or instead of, other ways to do Y) is extremely unlikely to cause complications or duplications.

To be frank the issue IS NOT duplication, the issues is to follow the logic in a story kind of way.

Flat logic obfuscate the context, a tree structure allow to retain context, so if there is a STORY logic bug, the context tell me on a per "topic" like base where I missed things.

The important part is that it's not SIMULATIONIST ai like the sims, but a NARRATIVIST ai.

The problem isn't the logic either, it's working perfectly. The issue is organization, I want to break the ai from a monolithic to a per character variants sharing the redundant part. Which would allow to add or remove character to the dynamic story scripts more easily. The logic being a glorified dialog tree, where text is replaced by character behavior, and options replaced by flags triggered by gameplay events.

ÁtilaFernandes said:
This is GTA V proportion, with AI ready to take whatever crazy idea the player does, like throwing a car on its head. It's better to shut this thing down.

YES

Really the number are spectacular, but it's really a bunch of small module accross multiple characters, The part that take the most are all the club activity then the investigations routine which have a different behavior per character (because they all react differently). Like I said, it's not and cannot be a generic ai, it's a bunch of named character that act in a story. Basically the Behavior are similar to text in a dialogue tree, all text in the dialogue tree is gonna be unique because it reflects character at one point in the story.

What I need is a way to break the "global dialog tree" per character and hooked it up to the global dialog tree later. The dialog tree taking different routes based on who is present (not dead or incapacited) at a certain moment. The issues is that, this being a story driven behavior, generic way of doing ai don't handle well coordination of multiple agents with unique reaction per scene, I don't have a framework to handle this, except making it flat, but then either I have to make a expensive tools being a whole project on its own on the scale of the game, or keep it as nested foldable blocks that aren't that bad, but feel dirty.

ÁtilaFernandes said:
Then you can OR those enums, combining flags. This way, you don't need a if/else tree, but rather mask of bits, providing a combination of flags. So each if is independent from the others, not nested. This will make the code much more readable/maintainable.

Like I said, I tried that method before (keeping everything separated) but that didn't worked and it quickly turned into a file spaghetti because explicit relation are gone, I can't reason about the state and behavior of the story, bugs start sips in because rules interact in way you can't predict.

A tree by definition is exclusionary, you cut half of behavior just choosing a branch, so while for example the club activity has 2000 lines, they are mutually exclusive, and by the way you come to their vicinity, all the global behavior has been taken into accounts and they are precision on top. There is a dozen of them, that mean they are roughly 100 lines long on average, and that's for multiple characters with their own implementation. They used to be in their own subtree file, but shuffling was actually harming development, because it's not the activity that need separation, it's the character, following a single character logic across multiple file was bothersome.

In actual practice from doing the game, I hadn't been able to move away from it, because I never see more than 10 lines at a time because everything fold nicely.

Such an idea would be great if I figure out a longitudinal separation (logic cascaded along the tree depth) rather than a transversal way (rules by rules). My problem is that I have multiple superposed tree, I'm trying to separate them. Going rules based kill that.

Basically rules based lead to this:

The main reason it is considered “harmful”, is because as complexity of a program increases, unstructured jumps can lead to an inability to understand what is happening in a program, even in small programs.

From "goto considered harmful"

EDIT:

I can't share the code, but I can share my pseudo code brainstorm early in teh project about a rule based system inspired by Emily Short's versu's QUIP system, Valve Elan Ruskin's conversation rules system and Failbetter's Storylet system. To show good faith I tried this:

//class quip(-actions?)->generalized to storylets?
    //prerequisites/criterion (list of "quality/facts/context" ranges to unlock it) -> match world state (aka query)
        //topic (group)
        //subjects (multiple possible)
        //opener (if for starting conversation)
        //used (removed from pool once seen or trigger varients)
        //prerequisite (condition: flags, stats, mood...)
        //priority (order of surfacing in limited view windows)
        //rarity weight: chance of surfacing
        //slotting: match type of objects or pattern to be used inside, treat the world state as database to query, These queries search for characters, inventory items, and so on that meet certain criteria and “bind” them to named parameters.
    //contents (display to player)
        //name of the node 
        //ID
        //title (seen if selection ui)
        //nested tree, storylets, quips, system, game, level, affordances, cinematic
        //slots: match elements are used inside
        //audiovisuals
        //behavior? (quip):(gesture)
        //options: what you cab do
        //string (text content, can used generator to be modified by stats)
        //varients (if used once, to avoid repeats)
        //-> consolidation, when a group of quip on a subject has been used up, offer a summuary
    //results ("quality" changes)
        //follow up (high priority after specific quip)
        //conveyance metadata: character mood, type of evaluation, factual data (flag or other) ...
        //action?: (modify stats of world or character)
        //goal?: (switch to a goal)
        //effects: spawn something that live in teh world state

//storylets:
    //This could be rewritten as “the world state determines what the player is currently allowed to do; everything the player does then updates the world state again.”
    //-> apply teh concept of quip graph search conversation to storylet, adversaries pushing stories to desired storylets with player countering the move by selecting other storylets.
    //quality base-> player selection.
    //salience base-> system selection
    //drama manager that search through storylets to get an ideal story up to (possibly random) specs

Basically my if tree is just a fancy control flow on top of a rule system, so I don't naively traverse it linearly (O(n²) vs O(nLogn) access)

Note, to be sure:

The tree don't implement the behavior themselves, those are functions call, the tree is merely implement the flow, and nothing else.

1. The perception UT write to the character perception's “blackboard” and the character read from a global AI black board.
2. THEN the tree sorts out which branch to go using the black board, eventually calling function at a given node (ie actions) or going deeper in the tree for a most complex actions selection. Action merely sets variables and flags for the state machine, these are functions call.
3. THEN once the sets are done, a state machine fire the state that handle the proper behavior, another sets of specifics actions.

2 is where I'm trying to refactor per characters, since it's a cascading logic.

The code pretty much looks like

//Black board:

//(reference to global ai sets on initialization, hold world state)
AiManager Manager; 

//hold all var and flags relative to interaction in the immediate sensing radius
Struct PerceptionBoard;

//character data such as persona, stats and other that can be modified, managed by  the 3 decisions layer and consumed by the action state machine.
Struct CharacterState;

void Update(){
    if (isActive & isLiving)
    
    	updatePerception();
    	
    	//Kind of a Subsumption architecture
    	//select the proper behavior with 3 "layers" of if tree
    	//Idea proposed was to get the most complex one and find way to break it further in layers. By finding pattern to generalize.
        updateSchedule();
		updateEvents();
        updateReaction();
        
        //Actually do the behavior
        performActions()
        
    else if (!isLiving)
    	updateDeath();
}

void updatePerception(){
		
		//Fallthrough pattern (concurrency: just DO don't exit, all node execute in order, generally order don't matter)
        GetPlayerDistance();
        UpdateDetection();
        //...
}

void updateReaction(){

		//priority pattern (exit on success)
        if( gotPushed() ) return;
        if( gotHit() ) return;
		if( gotAlarmed() ) return;
        //...
}

void updateSchedule(){

	//Complex tree of functions with various ALTERNATING ai pattern as "actions", really should be renamed to "decision units", will clear some confusion
	
	//behavior tree pattern (generally wrapped into function to resume to the proper node after exit, if it helps legibility or same type of decision is repeated accross node)
	
	//sequence pattern (exit on fail)
	if(!function1()) return;
	if(!function2()) return;
	if(!function3()) return;
	//priority pattern (see updateReaction above) 
	//fallthrough pattern ("concurrency": see updatePerception)
	
	//Preprocess units (Order matter, do stuff for nodes and units further down, generally before a nested node tree)
	
	//Nested node, precise a specific steps into a sub selections, node CAN follow behavior tree pattern too with return on fail or success or breaking the whole tree traversal.
	if(PerceptionBoard.check1){//prefix node indicating the task
		//interleaving pattern implementing logic, in any necessary order
		//->decisions units as sequence units
		//->decisions units as priority units
		//->decisions units as fallthrough units
		//->decisions units as preprocess units
		//->decisions units as nested node units
	}//suffix comments telling how much line there is, should add number of units and nodes instead, now thinkig about it...
	
	//more interleaved units and nested node
	
	//Observation there is a lot of "preprocess units" in the actual code.
	
    //problematic and specific node/units (happen at all hierarchy level)
    if (functionOrCheck() && isNAMEcharacter) ...
    if (functionOrCheck() && !isNAMEcharacter) ...
    if (functionOrCheck() && isPersona) ...
    if (functionOrCheck() && !isPersona) ...
}

I have been aggravated by calling it a behavior tree when a “behavior tree” is a will known pattern, decision tree is taken, so I'm gonna disambiguate into “selection tree”, I don't think the name is taken for a design pattern. Maybe I need more works formalizing it too, maybe if I can generalized it further, by breaking behavior into new sub abstraction, I could more easily split the tree.

It's legible because you read it top to down, and ONLY open nested if you NEED more precision, node have short prefix comments to replace the name and short suffix comment to indicate the line numbers. Node have a cascaded logic that is readable as if they were on a grammar like (high level pseudo structure):

hear[negative assessment] → selectEmotion[angry at father]→selectExpression[throws hands up]→SelectPathfindingTarget[storm toward the door]

With more than one path in a single evaluation, because character can do many things and be a complex state. And also it allow to write complex scenes by focusing only on a behavior from a single scene at a time, not try to write a uber turing passing behavior for all scenes that will never be (it's a story game, not a simulation, there is not an infinite number of funeral scene, and each will go differently based on AUTHORSHIP).

EDIT: writing this made me realized I can have my cake and eat it too, I always wanted "breakable if", and now I figure out I can encapsulate node into lambdas!

//Breakable node
() => {if (check){
        //code
        if(condition) return; //break from the node
        //code
}}

The joy of not having to implement a whole verbose node class to maintained!