A TADS3/adv3 module providing low-level NPC target-seeking behaviors

[jbg]

A TADS3/adv3 module for simple NPC target-seeking behaviors: targetEngine github repo.

This provides agendas for three basic NPC behaviors: move an NPC to a location, have an NPC take an object, and have an NPC examine something.

To have an NPC use the target engine logic, just declare useTargetEngine = true on the NPC:

      alice: Person 'Alice' 'Alice' 
              "She looks like the first person you'd turn to 
              in a problem. "
              isHer = true
              isProperName = true

              useTargetEngine = true
      ;

Now if you want Alice to take the pebble, you could use:

        // Tells alice to >TAKE the pebble. 
        alice.obtain(pebble);

By itself this won’t send Alice off to find the pebble, it just tells the actor to attempt to take the pebble when and where they see it. You can give an NPC multiple targets, so if you want Alice to gather the ingredients for a BLT, you can use something like:

        alice.obtain(bacon);
        alice.obtain(lettuce);
        alice.obtain(tomato);

…assuming all three objects are defined in the game. This will tell Alice to attempt to take each of the listed items when she encounters them.

The target engine currently provides the following behaviors:

• moveTo(loc) Attempts to move the NPC to the given location
• obtain(obj) If the NPC finds themselves in the same location as the object, they will attempt to obtain it
• observe(obj) If the NPC finds themselves in the same location as the object, they will attempt to examine it

Each of these methods accepts a callback function as the optional second argument. The callback will be called when the target is reached/obtained/completed, with the argument boolean true on success or nil on failure.

This is the first part of a system of more general NPC goal-seeking I’m working on. This is intended to hold just the low-level nuts-and-bolts stuff—no decision-making, just the in-game mechanisms for accomplishing individual tasks.

[dsherwood]

You are making me want to switch back to adv3 from adv3lite. Nice work!

[jbg]

Been working on more stock “building block” agends for building more complex, reactive NPC behaviors. This one’s Explore.

Explore

Properties

• agendaOrder = 180

  All the targetEngine agendas have orders between 100 and 199. Explore’s is after all the others except RandomWalk.

  This means that if an NPC is exploring and has been told to .obtain() or .observe() things that will happen automatically during exploration.

• depthFirst = true

  By default exploration will use a depth-first approach. In brief:

  • NPC will look check each exit from their current location and make a note of any they haven’t visited
  • If there are one or more unexplored exits in the current room, one will be selected and the NPC will attempt to move through it. The first unvisited exit, sorted by the order given by Direction.allDirections, will be picked.
  • If there is no unexplored exit in the current location, the agenda will select the most recent room observed (in the first step above) that has unvisited exits. It will then call the Move agenda to attempt to move the NPC to that room.

  These steps will be iterated until there are no known unvisited exits.

  If depthFirst = nil, then a breadth-first approach will be used. It is, briefly:

  • Make a note of unvisited exits as above
  • Pick the oldest noted unvisited exit
  • Path to the room the exit is in
  • Take the exit

  Both approaches should work for non-pathological maps, but in general depth-first will involve less backtracking. Breadth-first probably makes more sense if the goal isn’t to complete the map (that is, to visit every unvisited location) but to look for something that’s believed to be near the starting location.

Basic Usage

In general all that’s needed to use the Explore agenda is to declare useTargetEngine = true on the NPC:

     modify alice useTargetEngine = true;

…and then somewhere in the code trigger the agenda with:

     alice.explore();

Once started the agenda will automatically terminate when it runs out of unexplored exits. To stop it before then you can use:

     alice.clearExplore(true);

Notes

The main “gotcha” is if the NPC starts out knowing of no unvisited exits—like if they’ve explored previously or if they’re initialized with certain locations flagged as seen before they’ve “really” visited them. That means when the agenda starts they’ll look around, have no list of places to start exploring, and immediately give up.

To prevent this, if the agenda is started and there’s nothing in the list of unexplored exits (including any from checking the current location) then:

• We iterate over every Room instance, skipping any that the Actor hasn’t seen
• For each Room the actor has seen, we check it for unvisited exits, and add them to our list to explore
• When we’re done we set a flag that we check when we start this process, so by default we only do this check once per NPC/agenda

This doesn’t give the NPC any unfair psychic knowledge of the environment (it only checks rooms the NPC already knows about) but it prevents the failure-at-startup when there is no other starting list of places to explore.

Ordering

By default the agendaOrder is lower than most of the other targetEngine agendas, so if the actor has also been told to obtain or observe objects they’ll automagically do that while exploring.

Dependencies

Note that the Explore agenda requires the memoryEngine module, as will most additional/more complicated agendas that will (hopefully) follow.

[jbg]

There’s now a devel branch for stuff I’m actively working on (should be better about this for repos that I’ve made pubic). It includes a few new agenda types that’ll end up merged into main, hopefully:

Search

The Search agenda tells the NPC, basically, to toss any room they wander into. That is, they try to identify stuff that might need to be interacted with in order to locate something they might be looking for. Currently, that just involves trying to open closed containers, but the agenda has an isSearchable(obj) method for adding additional logic.

The Search agenda doesn’t directly do anything, it’s basically just meta-logic for managing the Open and Unlock agendas, below.

Specifically, if the search agenda is active and the NPC observes an in-scope openable container that isn’t open, they’ll call the Open agenda on it.

An Actor (that is unsing targetEngine) can be told to start searching by calling actorName.search([something]) where [something] is essentially used as an ID for the task. Just true will work if you want it all-or-nothing, or a string ID could be used if multiple things might want to turn on searching and you don’t want the completion of one to possibly stop searching when it wants to continue for some other reason.

Open

If the Open agenda is active, the actor will attempt to open a targetted openable container if it is in scope. Like Obtain (and most of the other agendas) this will not cause the actor to seek the container, just attempt to interact with it if they encounter it.

If the container is locked, the agenda will:

• remove the container from its target list
• invoke the Unlock agenda with the container as its target.
• invoke the obtainCustom() agenda with a filter function that matches plausible keys for the container

Unlock

When the Unlock agenda the actor will attempt to unlock a container on its target list if:

• it is currently in scope
• the actor is holding a key which is plausible for it (checked using LockableWithKey.keyIsPlausible()
• the actor hasn’t already tried all plausible keys they’re carrying on the container

If the agenda is successful in unlocking the container, it will add the container back to the Open agenda.

ObtainCustom

The ObtainCustom agenda is like the vanilla Obtain agenda, but instead of matching a specific object, it uses a filter function to determine if an object is a target.

For example, the Open agenda calls:

   getActor().obtainCustom(bind(&matchKey, self, t.target));

…where getActor() will return the Actor who owns the agenda, matchKey() is a method on the Open agenda, self is the Open agenda (so the bind fucntion will call matchKey() on the agenda instance), and t.target is the container the agenda just tried and to open and discovered it was locked.

The Open.matchKey() method looks like:

        matchKey(cont, obj) {
                if(!obj.ofKind(Key))
                        return(nil);
                if(obj.getCarryingActor() == getActor())
                        return(nil);
                if(cont.keyIsPlausible(obj))
                        return(true);
                
                return(nil);
        }

…so it returns boolean true for Key instances that are plausible for the container that the actor isn’t already carrying.

In Action

The searchTest demo has a searchable box which is closed and unlocked, a lockable box wich is closed and locked, a key that unlocks the lockable box, and an NPC Alice that has the Search agenda. The >FOOZLE command that starts the agenda:

This demo provides a >FOOZLE command that triggers Alice's searchTest agenda.

Alice's Room
This is Alice's starting room.

You see a searchable box, a lockable box, and a key here.

Alice is here in the conversation ready state.

>foozle
Alice is now searching.

>z
Time passes...

Alice opens the searchable box.

>z
Time passes...

Alice attempts to open the lockable box but it seems to be locked.

>z
Time passes...

Alice takes the key.

>z
Time passes...

Alice unlocks the lockable box.

>z
Time passes...

Alice opens the lockable box.
>z

Time passes...

Alice idles.

>

Still in the devel branch so there’s probably some bugs. And I want to extend this to handle locked doors as well as containers.

But my overall goal for the WIP is to be able to have the player delegate tasks like “go to the library and find their copy of the Necronomicon” and that kind of thing, and this is decdent-sized chunk of it.

[jbg]

Couple of updates.

Actor.find()

Added a pseudo-agenda, find. Basic usage is like most of the “real” agendas:

     // Send Alice off in search of the pebble
     alice.find(pebble);

…and it can be cleared with…

     // Stop Alice's pebble hunt
     alice.clearFind(pebble);

Unlike obtain(), find() does tell the actor to actively seek out the given object (instead of just picking it up if they happen to be in the same scope as the target).

The programming interface, at least on Actor, works the same as the targetEngine agendas. Under the hood they’re just “plain” methods on Actor that handle juggling other “real” agendas.

At present the find() logic just invokes explore(), search(), and obtain(). When invoking the Obtain agenda it passes a callback that will be called on success or failure, and that’s used to clear the other agendas.

Because the only movement is provided by Explore, this is currently a little brittle—it works well the first time an NPC is asked to find something, but if they’ve already explored most of the map they won’t re-check anyplace they’ve already been. I’ve got a bunch of logic for memory-based searching (that is, “intelligently” re-visiting previously explored areas) but that’s currently ugly bespoke code on individual NPCs that needs to be prettified for inclusion in the module.

targetEngineMethods Macros

Previously every time I added a new agenda I was “manually” adding the methods on Actor and TargetEngine that handle invoking the agenda(s). This involved touching four separate bits of code. Which wasn’t a big deal (because I’m not adding that many new agendas). But it was still vaguely bothering me so I implemented the add-the-stuff logic as a macro, targetEngineMethods.

Sample usage:

     // Set up the Explore agenda
     targetEngineMethods(explore, Explore)

This:

• creates TargetEngine.explore() and TargetEngine.clearExplore() with the standard TargetEngine add/remove target usage (calling _setTarget() and _clearTargetObj() under the hood)
• creates Actor.explore() and Actor.clearExplore(), which are wrappers that call the corresponding methods on the actor’s TargetEngine instance if they have one (and failing cleanly if they don’t)
• defines exploreAgendaClass = Explore on TargetEngine, to make it easier to subclass and have per-actor agenda classes
• adds exploreAgendaClass to the list in TargetEngine._agendaList, which enumerates which agendas to create for actors using targetEngine by default

All the existing agendas have been updated to use the macro.

[jbg]

A few more, slightly more sophisticated agendas/pseudo-agendas:

HuntNear

Like the Explore agenda, but tells the NPC to re-explore an area “near” the given room.

Note that this by itself does to cause the NPC to take any other actions in those locations.

Properties

• maxDijkstraDistance = 2

  The agenda will re-explore the Dijkstra neighborhood of depth maxDijkstraDistance around the room. That’s all locations that can be reached from the target room in this number of moves.

Usage

Basic Usage:

     // Tells ``alice`` to re-explore everything within 2
     // steps of the ``storageCloset`` room
     alice.huntNear(storageCloset);

Retrieve

Tells the NPC to attempt to re-visit the location of an object they’ve previously seen. If it isn’t in the location they last saw it in, they’ll automatically use huntNear() to explore the surrounding area.

Note that this by itself doesn’t instruct the NPC to obtain the object, just attempt to re-locate it.

Usage

Basic usage:

     // Tells alice to go back to where she saw the pebble
     // and search the nearby area if it's not there
     alice.retrieve(pebble);

The Find agenda has also been updated to invoke retrieve() automatically.

This means that the Find agenda logic should work for both seen and previously unseen objects. The logic being roughly:

• if the NPC has seen the target object before, they’ll attempt to path to the last known location
• if the object is no longer there they’ll search the surrounding area
• if the NPC has not previously seen the object, they’ll attempt to explore any unvisited rooms they know about in an attempt to locate it
• if at any point they see the object, they’ll attempt to obtain it
• if there are unopend containers or other searchable objects in any rooms they traverse while they’re looking for the object, they’ll attempt to open them (including trying any plausible keys)

This is all still in the devel branch. I think the additional thing I need (apart from additional testing) is logic for re-visiting known locked containers after obtaining plausible keys for them. The current logic will try any plausible keys on locked containers as the NPC encounters them, but there’s currently no provision for backtracking to containers that were ecountered before a key was obtained.

[jbg]

Okay, added RevisitLocked, which moves the NPC back to containers that:

• the Open agenda tried and failed to open
• the actor now has a plausible key for
• the plausible key hasn’t been tried

To summarize the current agendas, in order of precedence (bolded method entries are the ones intended to be called directly, others are generally intended to be called via other agendas):

• observe(object)

  The NPC will >X [object name] when the object is in scope

• obtain(object)

  The NPC will ``>TAKE [object name]" when the object is in scope

• obtainCustom(function)

  Like obtain() bt the object is a function instead of a single object. An in-scope object will be targetted if the function returns true when called with it as an argument.

• unlock(object)

  Attempts to >UNLOCK [object] WITH [key item in inventory] when the object is in scope and the NPC is holding a plausible key for it they haven’t already tried.

• open(object)

  Attempts to >OPEN [object] when the object is in scope and it hasn’t already been tried.

• search(uniqueID)

  Tells the NPC to use the Open and Unlock agendas on any openable but closed containers in scope.

• moveTo(room)

  Tells the NPC to attempt to move to the given room.

• explore(uniqueID)

  Tells the NPC to try any unvisited exits they have previously seen.

• huntNear(room)

  Tells the NPC to visit each room within a certain number of steps of the given room. Default distance is two.

• revisitLocked(uniqueID)

  Tells the NPC to backtrack to re-visit locked containers they previously tried and failed to open. Happens only when they have new keys to try.

• randomWalk(uniqueID)

  Tells the NPC to wander randomly.

In addition, there are two agenda-like methods (whose usage follows the agendas’) but which aren’t actually agendas. That’s because they don’t do anything directly themselves (so there’s nothing to put into an AgendaItem.invokeItem() method). They’re just wrappers around bundles of other agendas, basically.

• find(object)

  Generalized agenda that tells the NPC to actively seek out and obtain the given object, using the various other agendas in the module as necessary.

• retrieve(object)

  Return to the location the object was last scene, visiting nearby rooms (via HuntNear) if it is no longer there.

[jjmcc]

It looks like you are one method away from creating fully a fully algorithmic ParserPC!

• goofOn(obj)

Tells the NPC to find the obj in question, then use it in a variety of random and humorously inappropriate ways. If the object is an Actor, attempt to ask the target increasingly non sequitor and mocking questions.

If you then added

• writeReview(snarkLevel)

You would fully and completely replace me in this community! It wouldn’t even take AI!!!

[jbg]

Hm, my mental model for the level of complexity I was trying to bake into the module was “scripting/automation you could do in a typical MUD client circa the early '90s”. So based on your comments and my own progress, that means in order of increasing complexity it’s:

• writing IF reviews
• writing IF modules
• writing IF
• the level of scripting/automation possible in a typical early '90s MUD client

[blindHunter]

I knew this module reminded me of something, and I was right. Several years ago, I was examining the various early 90s MUD clients, and you basically hit the proverbial nail on the head. This very much reminds me of the scripting capabilities of Tintin or ZMUD.

[jbg]

Yeah, some iteration of tintin is one of the specific clients I have memories of rattling around in my head.

And there’s a lot of overlap in the kinds of in-game behaviors this kind of thing can produce, but that’s not really the motivation. It’s more that both MUD client scripting and “generic” NPC AI tend to favor use of small, more-or-less context-independent snippets of scripting instead of big, monolithic algorithms.

In the case of MUD clients is of necessity: you’re almost always triggering scripts based on string matching output from the MUD—run this script when you see a output matching this regex, and that kind of thing—and so you need to break things into little bite-sized, reactive chunks out of necessity.

Writing library code I have better access to the game’s internal state than a MUD client has, but when I’m scripting NPC behaviors, as much as possible I want to be able to just not have to worry about the low-level details of how things are going to happen. If I want Alice to obtain the ingredients for a BLT, I don’t want to have to script up that specific task in all its details. And I don’t want to have to worry about dealing with situations like: Alice goes to the kitchen, sees there’s no bacon, goes to the store to get bacon, comes back to the kitchen, sees there’s no lettuce, goes to the store to get lettuce, comes back to the kitchen, sees there’s no tomato… And this kind of approach takes care of that more more less for free.

The other major design goal is to allow for what I guess you might call “cross-fading” between NPC behaviors. That is, being able to give an NPC a bunch of different tasks at the same time and they tackle them in according some internal priority-sorting. As opposed to doing a bunch of explicit conditional branching logic or that kind of thing. Like if the player asks NPCs to help them gather wildflowers, you could have one NPC that’ll help if they happen to encounter some in their normal schedule, another than might visit a specific spot where they’ve seen flowers before, and a third might go on a whole expedition just to hunt down all the wildflowers. And all those behaviors are coming out of the same basic underlying logic, with different bits just getting floated to higher or lower priorities. As opposed to methods full of if(player.favorability > 2) kind of logic.