Structuring a utility AI- recommended reading and best practices?

I’m taking a second pass at my thus-far glitchy and pretty unimpressive AI, and since I have a large number of environmentally-determined actions available to NPCs, the most appealing solution seems to be implementing an object-based AI like The Sims, where NPCs are essentially empty shells and Interactables (fridges, bathtubs, other people) hold all of the actual behavior, animations, stat adjustments, and so forth.

It seems like the cleanest, most beginner-friendly way to approach this is to view Interactable objects in-scene as Resources, and NPCs as Consumers: every interactable reports to a central Manager class and tells it a) what it can give NPCs (food, health), and b) where in the level it’s located (so NPCs don’t cross the entire map to get food when there’s a sandwich three feet from their origin point). The manager keeps track of remembering which objects are already in use by another NPC (and thus out of bounds), and which one are sitting vacant and ready to use.

So first of all, does that all sound reasonable? I’ve looked at a lot of incredibly complicated AI implementations, and concluded that I need something simple and beginner-friendly but reasonably efficient.

Assuming there aren’t any gaping holes in my logic, I imagine each NPC will go through a very basic loop for most of their life:
a) Ask for an object to use
b) Pathfinding to that object
c) Activate that object and execute whatever logic it contains,
d) Ask for another object to use

However, there are a two things that I can’t quite wrap my head around. First off, would the design I’m proposing be more suited to asynchronous AI (where each NPC manages their own logic), or synchronous AI, where a central manager iterates through a list of every NPC one by one and steps them through the logic of their current object?

The bigger question, which I’m having a lot of trouble answering for myself is structurally, how would you handle chaining actions together? I can say that making a sandwich has three discreet steps (gather ingredients, assemble ingredients into sandwich, eat sandwich), and I know roughly what each step will involve (subtract ingredients from fridge inventory, instantiate new sandwich item with stats based on cooking skill, delete sandwich and apply stat modifications to NPC), but I have no idea how to translate that into code. One general, clumsy idea would be to create a Step class that holds a list and an Activate() function that just reads

delegateList[0]();

Then each unique Action (sandwich-making, bathing, running from rabid dogs) would contain customized functions for each step of that action: AssembleIngredients(), MakeSandwich(), EatSandwich(), and the like. Presumably the last line of each step would be a call to the next function in the step, with the final function in the chain of Steps handing control back and asking for a new object. The obvious problem this raises, however, is managing cpu cycles: this would be running on 30-40 NPCs at once, and I don’t know how I would make each Action regularly cede control back to the main thread while remembering where it was. Using a coroutine is one option, but again I don’t want to have forty coroutines running at once, as that feels like extremely inefficient design.

I know this is an absurdly broad question with a greater scope than a single forum thread, but I’d love any feedback or references more experienced developers may have. ^^

Queues may help here

This is a new concept for me, reading up on it now- I see how I’d form one by just running Step.Enqueue for each step in a process, but how are queues processed? What I’m trying to avoid is hanging the entire system while waiting for NPC 1 of 50 to finish running his animation and hand control back to the manager.

Use a coroutine owned by the NPC.

Something like the following pseudo code

while (queue is not empty) {
grab first item in queue
yield until first item is complete
}

What’s the overhead like on coroutines? Is it acceptable and/or advisable to have 40-50 of them running simultaneously, one per NPC?

You probably won’t notice the impact of fifty coroutines. They are no more expensive then Update, and considerably better if there are long yields in them.

Hmm, okay… if I wanted to run AI through a single manager whose job was to iterate through a list of NPCs and update their state machines one by one, but I don’t need the whole chunk processed at once, would a single coroutine with a yield equal to my AI tickrate pull that off effectively?

Hey,

You’re along the right track with the interactables approach. This is also called smart objects. Let me break down roughly how the sims works:

Each sim runs a behaviour tree. A behaviour tree is conceptually similar to a state machine, but is much easier to manage when you have lots of possible state transitions. You can learn roughly how it works here: http://aigamedev.com/open/article/bt-overview/. There are various free and paid solutions for this in the asset store. The behaviour tree would handle the specifics of the animation as well as the results - eg it would have steps for walking to the fridge, making a sandwich, and decreasing Hunger afterwards.

When trying to choose between behaviour tree branches, the Sim uses a utility system to evaluate different options. A utility system is a tool for scoring multiple considerations for each possible action. So for instance, the Sim might assign a score of 0.7 to Eat because it has a high Hunger, and a score of 0.3 to Sleep because they’re well-rested. Except there’s normally many more considerations than that - a Sim might score less for Eat if they’ve eaten recently, even if it was just a snack, or if they’re far from their own kitchen. This free lecture http://www.gdcvault.com/play/1012410/Improving-AI-Decision-Modeling-Through is a good introduction to the subject.

shameless plug if you don’t want to implement utility yourself, or would like a very editor-focused approach, consider my utility package DecisionFlex DecisionFlex | Behavior AI | Unity Asset Store It even has a Sims demo on the website http://www.tenpn.com/DecisionFlex.html end shamless plug

The smart objects come into it by injecting themselves into the behaviour trees of local Sims. Eg a TV might inject into a Sim to give it a Watch TV top-level behaviour. This way you can easily expand and iterate your AI without having comprehensive behaviour trees. BTs also offer themselves to this kind of injection, which finite state machines do not. If you don’t think you’ll have that many top-level behaviours, then maybe smart objects are overkill or for version 2.0.

So to break it down:

  • a Sim is in the room with a TV
  • the TV injects its behaviour tree into the Sim
  • the Sim decides what to do next, using utility to score the top-level behaviours, comparing Eat, Sleep and the injected Watch TV
  • Watch TV scores highly because of high Boredom and because the sim isn’t Hungry or Tired.
  • The Watch TV behaviour tree runs, finding a sofa to sit on and turning on the TV set, watching a bit and decreasing Boredom
1 Like

@Sendatsu_Yoshimitsu - I’ve worked extensively with utility-based AI – the kind of technique used in The Sims’ smart objects – so I can’t help but post some details here. Robert Zubek’s Needs-Based AI in GPG8 is an excellent overview. (You can also read Will Wright’s notes, but they’re not as useful.) This kind of AI is elegant and simple to implement. You don’t need the complexity a behavior tree, although nothing’s stopping you from piling it on top if you want more complexity. As you described in your original post, just select a smart object, navigate to it, and trigger its action.

With smart objects, action chaining is automatic. The NPC doesn’t have to do any planning.

Your NPC will have two pieces of data, basically the empty shells you described:

  • Motivations: Hunger, Thirst, etc. Each motivation usually has two floats: its current value, which usually just increases over time (use Time.deltaTime), and an urgency. You can use an AnimationCurve to translate value into urgency – so, for example, as the thirst value increases, the urgency could curve up gradually at first (low thirst isn’t very urgent) but then increase gradually as the value gets high (dying of thirst). The sum of all urgencies is the NPC’s happiness value.

  • Attributes: This is often just a list of inventory items, such as Raw Food, Cooked Food, and Plate of Food.

Your smart object script will have three pieces of data:

  • Advertisement: The changes promised to the NPC’s motivation values.
    Example: Stove might promise to reduce Hunger by 10.

  • Requirements: The attributes that the NPC must have to use the object.
    Example: NPC needs Raw Food to use the Stove.

  • Actions: The actual changes to the NPC’s motivations and attributes when used. This part usually also includes animations and sound effects to play.
    Example: Stove actually removes Raw Food and adds Cooked Food. It doesn’t modify Hunger directly. Play the “cooking food” animation.

The process to select a smart object is simple. Loop through all smart objects in the scene (or whatever list the Manager provides). Reject objects whose requirements are false. Compute the effect that the object’s advertisement will have on the NPC’s happiness value (attentuated by distance). Choose the object that has the best effect on happiness. (If necessary you can optimize later to not loop through all objects in the scene, but it’s often not a necessary optimization.)

Here’s your sandwich example with very rough code meant to convey the idea simply if not robustly. In practice, you won’t want to hard code “hunger” as a variable, for example, but instead make it user-definable.

NPC:

  • Motivation: Hunger
  • Attributes: none
public class Consumer : MonoBehaviour {
    public float hunger; // current hunger value
    public AnimationCurve hungerUrgency; // how hunger value translates to urgency
    public List<string> attributes; // list of items the NPC has
}

Fridge:

  • Advertisement: Hunger -10
  • Requirements: none
  • Actions: Add SandwichIngredients

Counter:

  • Advertisement: Hunger -10
  • Requirements: SandwichIngredients
  • Actions: Remove SandwichIngredients, Add Sandwich

Table:

  • Advertisement: Hunger -10
  • Requirements: Sandwich
  • Actions: Remove Sandwich, Adjust Hunger -10
public class Resource : MonoBehaviour {
    public float advertisedHungerAdjustment; // promises to adjust hunger by this amount
    public string requiredItem; // NPC must have this item to use the object
    public string actionRemoveItem; // when used, remove this item from the NPC
    public string actionAddItem; // when used, add this item to the NPC
    public float action hungerAdjustment; // when used, adjust hunger by this value
    public string actionAnimation; // when used, play this animation

    public void Start() {
        // register with the manager you described
    }

    public void Use(Consumer consumer) {
        consumer.attributes.Remove(actionRemoveItem);
        consumer.attributes.Add(actionAddItem);
        consumer.hunger += actionHungerAdjustment;
        consumer.animation.Play(actionAnimation);
    }
}

If you want to get fancy, you can put “Use” in a separate component. This way, you can add different components for different objects, and they could do drastically different things.

Say the NPC starts hungry and with no items:

  • The only object with valid requirements is Fridge, which promises to reduce hunger by 10. So the NPC navigates to the fridge and uses it. He receives SandwichIngredients.
  • His hunger is still there. At this point, the only object with valid requirements is Counter, which promises to reduce hunger by 10. He uses it, loses SandwichIngredients, and receives Sandwich.
  • The poor guy is still hungry. The only valid object is Table. He uses it, loses Sandwich, and finally reduces hunger.

So, finally getting to your questions (sorry for the long ramble above), this was all done without any kind of runtime planning. The NPC doesn’t need to worry about what event happens next in the chain. All he cares about is his current state, and the advertisements and requirements of the objects in the scene. This makes the AI really fast. There are no decision trees to follow, and no decisions to make except for a single action-selection choice that’s based on very simple math.

Each NPC can act asynchronously on its own, and I’m going to argue that using 40 coroutines is probably the most efficient approach. You don’t want your manager spinning through all 40 NPCs every update. If an NPC is busy playing an animation for 5 seconds, you might as well let his coroutine WaitForSeconds(5) and not eat CPU.

You mentioned locking objects in use by an NPC. If one NPC is using the Fridge, just set it so the requirement check returns false until the NPC is done. This way, other NPCs won’t try to use it.

I haven’t had the opportunity to use andrew fray’s DecisionFlex. Read through Zubek’s article and then check out DecisionFlex. If it provides what you’re looking for, it could be nice timesaver.

4 Likes

Holy cow Tony and andrew, that’s immensely helpful… I’m, going to have to reread this several times to digest it, but I really appreciate the help- this is exactly the clarification I was hoping for :slight_smile:

1 Like