NPC Scripting and Reasoning about the NPC behaviour
by Sami Mäkelä
Introduction
In this note I'll first present a simple language for writing scripts to control NPC behaviour. To make the NPCs capable of symbolic reasoning, a framework for knowledge and reasoning about NPC behaviour is needed. Then NPCs can use symbolic reasoning to program themselves.
Simple Scripting Language
In an NPC scripting language there needs to be predefined operations that for example make the NPC move around, pick up or drop objects.
- move loc makes the NPC move to a location loc.
- pickup obj makes the NPC to pick up an object.
- drop obj makes the NPC to drop an object.
- has_object obj returns true if the NPC has an object, false otherwise.
- see_objects returns a list of objects that the NPC can see.
To make these operators useful, there needs to be ways to combine the operations and define functions.
The '>>>=' operator implements sequential composition for operations. The operation *a >>>= fun x --> b first does the operation a. a might return a value which is bound to x. Then operation b is run. b might use the value x*. The '>>>' operator is same as '>>>=' but the value is ignored. ret x is an operation that has value x but does nothing.
move_item it loc is an operation that moves the item it to a new location loc and leaves it there.
let move_item it loc =
has_object it >>>= fun b -->
( if b then ret ()
else pickup it ) >>>
move loc >>>
drop it
Often an NPC has several goals that it is trying to accomplish, and they do not have to be done in a sequential order. The NPC can switch between operations (tasks) after it has worked on one task for a while or when a task becomes important for some reason.
Parallel operators do_all and do_some can be used to combine operations to operations where different tasks can be run in any order--switching between tasks. do_all lst runs all the operations in the list lst to the end, while do_some lst runs only some of the operations to the end.
move_items loc lst moves all items in the list lst to location loc and move_something loc moves some of the available objects to location loc.
let move_items loc lst =
do_all (List.map (fun it --> move_item it loc) lst)
let move_something loc =
see_objects >>>= fun lst -->
do_some (List.map (fun it --> move_item it loc) lst)
Recursion can be used to write more complex operations.
Some Extensions
Sometimes it is needed to know when to do an action. For this, the at operator can be used. at x task makes the NPC start doing the operation task at time x. Priority can be used to control what task is ran. priority func task makes an operation that has priority func.
work_day makes an NPC to wake up at 6 o'clock, go to work at 8 o'clock for a time that depends on the do_work task. At noon, the NPC will go to eat unless work has larger priority, in which case the eating is delayed.
let work_day =
do_all [
at "6:00" wake_up;
at "8:00" (go_work >>> do_work >>> go_home);
at "12:00" (priority 10.0 (go_eat >>> eat >>> go_work));
at "22:00" (priority 20.0 go_sleep) ]
For handling failures, several programming languages have exception handling. Exception handling can be added to the scripting language too. It is very useful because most of the operations can fail in unexpected ways. fail exn raises an exception exn. *try_task task ~handle:(function exn_1 ® handler_1 | ... | exn_n ® handler_n) tries to run an operation task* and in the case of failure, runs an appropriate handler.
Define new exception PickupFailure. exception PickupFailure
Operation pick_up_all lst tries to pick up all the objects in lst. If picking up fails with CannotSeeObject or CannotLiftObject then PickupFailure is raised. Other failures are just re-raised.
let pick_up_all lst =
try_task (do_all (List.map (fun it --> pickup it) lst))
~handle:(function
| CannotSeeObject --> fail PickupFailure
| CannotLiftObject --> fail PickupFailure
| a --> fail a )
NPCs can interact with other NPCs and the world using events. Event handlers can be associated to tasks using reaction operation. reaction h task returns the task with event handler h. The event handler is a function that gets an event and the continuation of the current task as an argument. An NPC can send events using send operation.
say_hello is an event handler that says "Hello" to everyone that is seen.let say_hello cont = function | See x --> send x (Say "Hello") >>> cont | _ --> cont
get_event returns the next event the NPC receives.let get_event = reaction (fun _ ev --> pass ev) wait_forever
There can be special events that are sent to a task when it is delayed.
Reasoning
In the scripting system above, the programmer needs to specify the behaviour of the NPCs fully with an imperative language. The system has no support for knowledge or reasoning, the programmer needs to implement all that on top of the system. For generic knowledge representation and reasoning, logic is needed.
The most well-known logic usable for knowledge representation is first-order predicate logic (FOL). Here is a syntax for a typed version of it:
- ~a: a is not true. (Negation.)
- a /\ b: a and b are true. (Conjunction.)
- a \/ b: a or b is true. (Disjunction.)
- a --> b: if a is true then b is true. (Implication.)
- *a <-> b: a and b are equivalent. This is abbreviation of (a --> b) /\ (b --> a)*. (Equivalence.)
- (ALL a:t)p: for all a with type t, p is true. (Universal quantification.)
- (EX a:t)p: there is some a with type t for which p is true. (Existential quantification.)
There are two different versions of first order logic, classical and intuitionistic. The difference is that the proposition a \/ ~a is trivially true in classical logic, but in intuitionistic logic that proposition means that proposition a is decidable ie. we can tell whether a is true or not. To have features of both versions we can have two different types (universes) of propositions. More about this later.
First order logic is useless if we do not have some additional predicates for domain-specific knowledge. Some atomic predicates for our logical theory:
- possess x: the NPC possesses item x.
- current_location x: the NPC is at location x.
- at_ground x: the item is at ground.
- at i loc: the item i is at location loc.
This logic can then be used to represent many useful facts about the game world, like (ALL x:item)possess item --> (ALL x:loc)current_location x --> at item x which tells that every item that the NPC possesses is at same location as the NPC.
It is however not clear how to express what the NPC can so. For example if we wanted to express that the NPC can drop items that it possesses, we could try (ALL a:item)possess a --> at_ground a. However, this means that every item that is possessed is dropped. Some other problems with FOL are that there are no support for time, location or uncertainty.
To overcome these problems, modal logics have been developed. In modal logics, the propositions can have different kinds of modes. For example in traditional modal logic, there are two modalities, possibility and necessity. In temporal logics there can be modalities for past and future or different kinds of time periods. In spatial logic, the truth of predicates can vary depending on the location. in BDI-logic for intelligent agents, there are different modalities for beliefs (knowledge), desires (goals) and intentions (plans).
For our purposes, we can define modality P a, which means that it is possible to act so that a becomes true. With this intuitive understanding of P we can derive some axioms for it. If a is already true, we can act so that it becomes true (do nothing): a --> P a. If we can act so that a becomes true and if a is a precondition so that we can make b true if a is true, then we can make b become true: P a --> (a --> P b) --> P b. Now we can use these axioms to determine if we can make something become true.
Now we can specify dropping by (ALL a:item)possess a --> P (at_ground a). As another example, (ALL x:item)see x --> P (possess x) means that if we see an item, it is possible to acquire it as a possession (by picking it up).
We can add temporal and spatial aspects to the logic to reason about time and space. For example <at 20.00 - 4.00>night /\ <at 4.00 - 20.0>~night tells us when it is night. Note that <at 20.00 - 4.00>night doesn't work because if the clock would for example be 12.00 we wouldn't know if it was day or night.
Relating scripting language and logic.
With the scripting language, we can describe what the NPCs do. With logic, we can express knowledge about what NPCs do. Now we can relate these two systems so that the scripting language describes how to do what the logic claims that the NPCs can do.
Every proposition that the NPC knows will be associated with a proof of that knowledge. For example, a proof of possess Item might be an observation that the NPCs possesses Item. The proof of an implication or universal quantification is a function. The operators '>>>=' and ret implement the two axioms for my logic:
val >>>= : P x --> (x --> P y) --> P y
val ret : x --> P x
'a ||| b' finishes operation a or b. 'a &&& b' finishes both a and b. do_all and do_some can be implemented using these more primitive operations. Another possible type for '|||' is P x --> P x --> P x.
val ||| : P x --> P y --> P (x \/ y)
val &&& : P x --> P y --> P (x /\ y)
Atomic operation can be described in a natural way:
val move : (ALL x:loc)P (current_location x)
val pickup : (ALL item:item)P (possess item)
val drop : (ALL item:item)P ~(possess item /\ at_ground item)
val get_location : (ALL i:item)(EX loc:loc)(at item loc)
Because we use intuitionistic logic, we can express the decidability of a predicate.
'<font color=purple>val</font> has_possession : (ALL item:item) P (possess item \/ ~possess item)'
Some additional facts.
val possessions_at_same_location :
(ALL item:item)possess item --> (ALL x:loc)current_location x ® at item x
val possessions_not_at_ground : possess item --> ~(at_ground item)
Consider we have an object and we want to move it somewhere: (ALL i:item)possess i --> (ALL x:loc)P (at i x). Now we can use the axioms and atomic predicates to prove this. The proof term is an executable script, move_poss.
let move_poss (i:item) (pos: possess i) (x:loc) : P (at i x) =
move x >>>= fun c_x -->
ret (possessions_at_same_location i pos x c_x)
If we don't know whether we have an object or not, we can use case analysis.
let>>= fun p -->
match p with
| Left proof ® moveposs i proof x
| Right --> ( pickup i >>>= fun proof --> move_poss i proof x )
The generated programs can have a lot of content that is only useful for reasoning. This content amounts to a correctness proof of the program. All of the non-computational content can be removed from the program before the task is ran. This is easy if we have different universes for computational and non-computational predicates. For example move_poss and move_item become:
let move_poss x = move x
let move_item i x =
has_possession i >>>= fun p -->
if p then move_poss x else
( pickup i >>> move_poss x )
The proof p of possess item \/ ~(possess item) is just converted to a boolean because the predicate possess has no computational meaning.
Some Problems with Logic
Logic was originally meant to express "eternal" mathematical facts. Unlike in maths, the knowledge of NPCs is constantly changing. In some logic programming languages like Prolog, this problem is "solved" by using completely ad-hoc and undeclarative methods (assert, retract). I'll demonstrate these problems with a simple example.
Imagine that an NPC knows how to get an amulet from a temple and a crown from a pyramid:
val get_amulet :
at Temple Sword --> at_ground Sword -->
P (possess Amulet)
val get_crown :
at Pyramid Sword --> at_ground Sword -->
P (possess Crown)
Now the reasoning system could write the following program to acquire the crown and the amulet:
let get_artifacts : P (possess Crown /\ possess Amulet) =
let use_sword poss =
move Temple >>>= fun at_temple -->
move Pyramid >>>= fun at_pyramid -->
drop Sword >>>= fun (_, sword_at_ground) -->
let sword_at_temple =
possessions_at_same_location Sword poss Temple at_temple in
let sword_at_pyramid =
possessions_at_same_location Sword poss Pyramid at_pyramid in
get_amulet sword_at_temple sword_at_ground >>>= fun have_amulet -->
get_crown sword_at_pyramid sword_at_ground >>>= fun have_crown -->
ret (have_crown, have_amulet) in
match has_possession Sword with
| Left proof --> use_sword proof
| Right dis_proof --> ( pickup Sword --> fun proof --> use_sword proof )
The program is obviously wrong but our logic accepts it. This means that our logic can only be used to reason in a frozen step of time, where the knowledge doesn't change.
Different logic
We might be able use temporal logic to express the changes of truths of over time. Instead we use linear logic which has more direct support for knowledge evolution. In linear logic, the propositions do not represent eternal facts. They are resources that can be consumed. This means that a proposition can only be used once by default.
- a --> b, where --> is now the linear implication (often written -o), means that we can consume a to achieve b.
- *a × b means that we have resources a and b*.
- a & b means that we can select from a and b.
- a + b means that we have resource a or b.
- !a means that we can have as many a's as we want.
'>>>=' and ret are now just application of a rule and identity axiom.
val (>>>=) : (ALL a,b:prop) a --> (a --> b) --> b
val ret : (ALL a:prop) a --> a
The tasks drop, pickup and move can be used as many times as needed. We have to be careful that the rules can't produce extra copies of the facts. Otherwise, we could for example have the NPC think that it is on several locations at once, like in the previous example.
val move : (ALL x,y:loc)current_location y --> current_location x
val pickup : (ALL i:item; y:loc)at_ground i × at y i --> possess i
val drop : (ALL i:item;x:loc)
possess i × current_location x -->
at_ground i × at x i × current_location x
Some actions can anylyze knowledge. The knowledge that the NPC possesses an item includes the knowledge that the item is at the same location as the NPC. We can therefore split a possess predicate to the fact about it's location and to the rest of the knowledge included in the possess predicate. These two pieces of knowledge can then be combined to the possess predicate again.
val possessions_at_current_location : (ALL i:item; x:loc)
current_location x × possession i <->
current_location x × at x i × possession_tag i
We know where we are. (Actually it might be enough to know that we are somewhere).
val our_loc : loc
val at_our_loc : current_location out_loc
We know how to get the amulet and the crown. These methods can only be used once, otherwise we could get as many amulets and crowns as we want.
val get_amulet :
at Temple Sword × at_ground Sword -->
possess Amulet × at Temple Sword × at_ground Sword
val get_crown :
at Pyramid Sword × at_ground Sword -->
possess Crown × at Pyramid Sword × at_ground Sword
We have some information about the sword. But it might soon become outdated!
val sword_info : (possess Sword) + (EX l:loc)(at l Sword × at_ground Sword)
A correct script for acquiring the amulet and the crown.
let get_artifacts : possess Crown × possess Amulet × current_location Pyramid × possess Sword =
('*' Use our knowledge about the sword to find out if we own it or not. Then use that knowledge to find out where it is. '*')sword_info >>>= fun k --> match k with | Left proof --> use_sword proof | Right (loc, at_loc, sword_at_ground) --> ( pickup Sword loc at_loc >>>= fun proof --> use_sword proof )
Use the sword to acquire the crown and the amulet.
let use_sword possess_sword =
('*' Move to temple ... '*')move Temple our_loc at_our_loc >>>= fun at_temple -->
('*' Drop the sword, it is at the temple now. '*')drop Sword Temple possess_sword at_temple >>>= fun sword_at_ground, sword_at_temple, at_temple -->
('*' Now we can get the amulet. '*')get_amulet sword_at_temple sword_at_ground >>>= fun have_amulet, sword_at_temple, sword_at_ground -->
('*' Pickup the sword, it's still needed. '*')pickup Sword Temple sword_at_ground sword_at_temple >>>= fun possess_sword -->
('*' Then repeat with the pyramid. '*')move Pyramid Temple at_temple >>>= fun at_pyramid --> drop Sword Pyramid possess_sword at_pyramid >>>= fun sword_at_ground, sword_at_pyramid, at_pyramid --> get_amulet sword_at_pyramid sword_at_ground >>>= fun have_amulet, sword_at_pyramid, sword_at_ground --> pickup Sword Pyramid sword_at_ground sword_at_pyramid >>>= fun possess_sword --> ret (have_crown, have_amulet, at_pyramid, possess_sword)
Actually, all the knowledge (at_our_loc, get_amulet, get_crown, sword_info) should be passed as an argument to the function.
A problem in NPC scripting is that an operation can be interrupted at any moment. Because of this the knowledge might change. In our current framework, we now have several possibilities for handling that problem. Most simple and reliable possibility is to make a new plan to accomplish the goal, but this might be very time consuming if complex reasoning was needed for the original task. We can also check if the related facts are still correct, and continue where we left. If some of the needed conditions do not hold, we can try to make them true again. We can also try if the current situtiation satisfies the conditions in some stage of the original plan.
Summary
This note shows how to implement the behaviour of NPCs using a simple programming language. An expressive logic is then developed for representing the knowledge of NPCs and reasoning about that knowledge. Finally the scripting language and the logic are combined into a linear type theory. Now it is possible to use the knowledge to build new scripts.
There is still lots of work with integrating all the task combinators with the logic. Even larger piece of work is actually implementing the knowledge handling and reasoning. The logic can be restricted to some subset, which still works for most cases. Even if the implementation doesn't use logic directly, it might still useful in designing the system.
Links
- A paper about planning in linear logic
- Coq proof system and type theory
- HOL theorem prover
- Lygon logic programming language
A (274.8 KB) and a (315.1 KB) are available.
Current Issue: February 2003, Recent Issues: January 2003, November 2002, October 2002 |